平衡二叉搜索树(Self-balancing binary search tree)又被称为AVL树(有别于AVL算法),且具有以下性质:它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。

还是看一个案例,给你一个数列{1,2,3,4,5,6},要求创建一颗二叉排序树(BST),并分析问题所在。
把它构造完成之后,左子树全部为空,从形式上看,更像一个单链表,查询速度明显降低。
解决方案:平衡二叉树(AVL)
我们的AVL相关代码可以直接从二叉排序树那边复制过来(下面我再列出来),下面我主要写插入的问题,因为平衡二叉树插入有时候可能需要旋转才能使其满足条件。
我们先写一个Node节点类:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32
| class Node{ int data; Node left; Node right; public Node(int data){ this.data = data; }
@Override public String toString() { return "Node{" + "data=" + data + '}'; } public void add(Node node){ if(node==null) return; if(node.data < this.data){ if(this.left==null) this.left = node; else this.left.add(node); }else { if(this.right==null) this.right = node; else { this.right.add(node); } } } }
|
它有对应的添加方法,接下来是AVL树 AVLTree
类:
1 2 3 4 5 6 7 8 9 10 11
| class AVLTree{ Node root; public void add(Node node){ if(root==null) root = node; else root.add(node); } }
|
树的高度
其实我们判断是否需要旋转的依据就是左子树和右子树的高度,我们要在Node类中完成三个方法,分别返回这棵树的高度、它的左子树的高度、它的右子树的高度。
先写以它自己为根节点的树的高度,其实很简单,就是递归调用下去:
1 2 3 4
| public int height(){ return Math.max(this.left==null ? 0 : this.left.height(),this.right==null ? 0 : this.right.height())+1; }
|
有了这个方法,那么要想返回其左子树和右子树的高度就很简单了,如下:
1 2 3 4 5 6 7 8
| public int leftHeight(){ return this.left==null ? 0 : this.left.height(); }
public int rightHeight(){ return this.right==null ? 0 : this.right.height(); }
|
左旋转

这种情况就需要左旋转,步骤如下:
以当前节点的值创建新节点
新节点左子树设置为当前左子树
新节点右子树为当前右子树的左子树
当前节点值替换为右子节点的值
当前节点右子树为右子树的右子树
当前节点的左子树设置为新节点
具体代码如下:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
| public void leftRotate(){ Node newNode = new Node(data); newNode.left = left; newNode.right = right.left; data = right.data; right = right.right; left = newNode; }
|
右旋转

代码如下:
1 2 3 4 5 6 7 8 9
| public void rightRotate(){ Node newNode = new Node(data); newNode.right = right; newNode.left = left.right; data = left.data; left = left.left; right = newNode; }
|
左右双旋转
一些时候进行进行单旋转(即一次旋转)就可以将非平衡二叉树转成平衡二叉树,但是在某些情况下,单旋转不能完成平衡二叉树的转换,如下图所示,需要进行两次旋转:

这样两种情况:
- 如果左子树的右子树的高度大于左子树的左子树的高度
- 如果右子树的左子树的高度大于右子树的右子树的高度
这种情况下,我们要进行两次旋转。
添加节点的方法
虽然旋转的方法不是很难写,但是我们怎样才能构造这样的平衡二叉树呢?
我们的节点是一个一个添加的,我们肯定得防微杜渐,从刚开始不满足就开始旋转,否则等全部建立起来了,可能左右子树高度都相差10000了,还调整个毛。所以我们可以修改我们Node节点的add添加方法,在后面判断是否需要旋转,如果高度相差大于1就对其旋转,这样就可以了,add方法代码如下:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34
| public void add(Node node){ if(node==null) return; if(node.data < this.data){ if(this.left==null) this.left = node; else this.left.add(node); }else { if(this.right==null) this.right = node; else { this.right.add(node); } } if(leftHeight()-rightHeight()>1){ if(left!=null && left.rightHeight()>left.leftHeight()){ left.leftRotate(); } rightRotate(); return; } if(rightHeight()-leftHeight()>1){ if(right!=null && right.leftHeight()>right.rightHeight()){ right.rightRotate(); } leftRotate(); } }
|