上一篇实现了二叉搜索树，本章对二叉搜索树进行改造使之成为平衡二叉搜索树(Balanced Binary Search Tree)。
不平衡的二叉搜索树在极端情况下很容易退变成链表，与新增/删除/查找时间复杂度为O(logN)的目标又远了一步。
平衡二叉搜索树始终围绕O(logN)这个目标来构建数据结构。
节点类和实现类：
/**
* 二叉搜索树节点&平衡二叉搜索树添加节点时自平衡实现
*/
public class Node
{
private int data;//数据域
private Node left;//左节点（左孩子）
private Node right;//右节点（右孩子） public int getData() {
return data;
}
public void setData(int data) {
this.data = data;
}
public Node getLeft() {
return left;
}
public void setLeft(Node left) {
this.left = left;
}
public Node getRight() {
return right;
}
public void setRight(Node right) {
this.right = right;
} //构造函数
public Node(int data, Node left, Node right){
this.data = data;
this.left = left;
this.right = right;
}
public Node(int data){
this(data,null,null);
}
public Node(){
this(0,null,null);
} //求该结点的高度
public int getHeight(){
return Math.max(this.left==null?0:this.left.getHeight(),this.right==null?0:this.right.getHeight())+1;
} //左节点的高度
public int getLeftHeight(){
if(this.left==null)
return 0;
else
return this.left.getHeight();
}
//右节点的高度
public int getRightHeight(){
if(this.right==null)
return 0;
else
return this.right.getHeight();
} //左旋
public void leftRotate(){
Node node=new Node(this.data);
node.left=this.left;
node.right=this.right.left;
this.data=this.right.data;
this.right=this.right.right;
this.left=node;
} //右旋
public void rightRotate(){
Node node=new Node(this.data);
node.right=this.right;
node.left=this.left.right;
this.data=this.left.data;
this.left=this.left.left;
this.right=node;
} /**
* 向二叉排序树添加结点
* @param node
*/
public void add(Node node){
if(node==null){
return;
}
if(node.data<this.data){
if(this.left==null){
this.setLeft(node);
}
else{
this.left.add(node);
}
}
else{
if(this.right==null){
this.setRight(node);
}
else{
this.right.add(node);
}
} //右子树的高度-左子树的高度）>1，左旋转
if(this.getRightHeight()-this.getLeftHeight()>1){
//如果它的右子树的左子树高度大于它的左子树高度，双旋转
if(this.right!=null&&this.right.getLeftHeight()>this.getLeftHeight()){
//先对这个结点的右节点进行右旋转
this.right.rightRotate();
}
//左旋转
this.leftRotate();
}
//左子树的高度-右子树的高度）>1，右旋转
else if(this.getLeftHeight()-this.getRightHeight()>1){
//如果它的左子树的右子树高度大于它的右子树高度，双旋转
if(this.left!=null&&this.left.getRightHeight()>this.getRightHeight()){
//先对这个结点的左节点进行左旋转
this.left.leftRotate();
}
//右旋转
this.rightRotate();
}
else{
return;
}
} }
测试类：
import java.util.*;
public class Main {
public static void main(String[] args) {
/**
* 平衡二叉搜索树测试
*/
Node root = new Node(25);
root.add(new Node(18));
root.add(new Node(16));
root.add(new Node(19));
root.add(new Node(29));
root.add(new Node(27));
root.add(new Node(30));
root.add(new Node(31));
root.add(new Node(32)); //输出树
System.out.println(Arrays.toString(levelOrder(root)));
root.add(new Node(35));
root.add(new Node(36));
System.out.println(Arrays.toString(levelOrder(root)));
} /**
* 层序遍历
* @param root
* @return
*/
public static int[] levelOrder(Node root) {
if(root == null){
return new int[0];
} Queue<Node> queue = new LinkedList<Node>();
queue.add(root);
ArrayList<Integer> arr = new ArrayList<>();
while( !queue.isEmpty() ){
Node temp = queue.poll();
arr.add(temp.getData());
if(temp.getLeft() != null){
queue.add(temp.getLeft());
}
if(temp.getRight() != null){
queue.add(temp.getRight());
}
}
int[] res = new int[arr.size()];
for(int i = 0;i < arr.size();i++){
res[i] = arr.get(i);
} return res; } }
执行结果：
*重点：
1，平衡二叉搜索树是一种高度平衡的二叉树；
2，由于对平衡的高要求，插入删除时会对树进行频繁的旋转操作。
