普通的二叉查找树在插入有序的数据的时候会退化为链表，查找的时间复杂度退化为O(n)。而平衡二叉树在插入数据的时候一直保持二叉树的平衡，从而保证查找的时间复杂度维持在O(logn)。
平衡二叉树的定义
一棵平衡二叉树是其每个结点的左子树和右子树的高度最多相差1的二叉查找树(空树的高度为-1)。
二叉树的高度——当前结点到叶子结点的最长路径
四种旋转的情况
若平衡二叉树种某个结点的左子树和右子树的高度相差大于1，该树就是失衡了，该结点称为失衡点，就要通过旋转来保持二叉树的平衡。
一共分四种情况导致结点失衡：
- 在结点的左孩子的左子树中插入数据（LL）
- 在结点的左孩子的右子树中插入数据（LR）
- 在结点的右孩子的左子树中插入数据（RL）
- 在结点的右孩子的右子树中插入数据（RR）
第1和4种情况是对称的，可用单旋来解决，而第2和3种情况也是对称的，要用双旋来解决。
LL型（左孩子的左子树）通过右旋解决
对于LL型的情况，要使用右旋来解决，将失衡点右旋到其左孩子的右孩子的位置，失衡点的左子树更新为其原来左孩子的右子树。
RR型（右孩子的右子树）通过左旋解决
对于RR型的情况，要使用左旋来解决，将失衡点左旋到其右孩子的左孩子的位置，失衡点的右子树更新为其原来右孩子的左子树。
LR型（左孩子的右子树）通过先左旋再右旋解决
对于LR型的情况，要使用先对失衡点的左孩子进行左旋，然后再对失衡点进行右旋来解决。
RL型（右孩子的左子树）通过先右旋再左旋解决
对于RL型的情况，要使用先对失衡点的右孩子进行右旋，然后再对失衡点进行左旋来解决。
以上图片来自：AVL平衡二叉树详解与实现
代码实现
AVLNode
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| public class AVLNode<T extends Comparable<T>> {
public AVLNode<T> left;
public AVLNode<T> right;
public T data;
public int height;
public AVLNode(T data) {
this.data = data;
}
}
|
AVLNode中一定要保存结点的高度，并在高度有变化的时候进行更新，我看过有一些简单的实现，在结点的数据结构中没有记录结点的高度，每次判断是否平衡的时候都要重新递归计算结点的高度，这样的做法效率很低
四种情况的旋转操作
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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
|
public AVLNode<T> singleRotateRight(AVLNode<T> unbalance) {
AVLNode<T> leftNode = unbalance.left;
unbalance.left = leftNode.right;
leftNode.right = unbalance;
unbalance.height = Math.max(height(unbalance.left),height(unbalance.right)) + 1;
leftNode.height = Math.max(height(leftNode.left),unbalance.height) + 1;
return leftNode;
}
public AVLNode<T> singleRotateLeft(AVLNode<T> unbalance) {
AVLNode<T> rightNode = unbalance.right;
unbalance.right = rightNode.left;
rightNode.left = unbalance;
unbalance.height = Math.max(height(unbalance.left),height(unbalance.right)) + 1;
rightNode.height = Math.max(height(rightNode.right), unbalance.height) + 1;
return rightNode;
}
public AVLNode<T> doubleRotateLeftRight(AVLNode<T> unbalance) {
unbalance.left = singleRotateLeft(unbalance.left);
return singleRotateRight(unbalance);
}
public AVLNode<T> doubleRotateRightLeft(AVLNode<T> unbalance) {
unbalance.right = singleRotateRight(unbalance.right);
return singleRotateLeft(unbalance);
}
|
旋转的操作的代码其实比较简单，按照着上边所描述的旋转的操作进行相应的结点左右孩子指针的更新就可以了
插入操作
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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
| public int height() {
return height(root);
}
public int height(AVLNode<T> node) {
return node==null?-1:node.height;
}
public void insert(T data) {
if (data==null){
throw new RuntimeException("data can\'t not be null ");
}
this.root = insert(data, root);
}
public AVLNode<T> insert(T data,AVLNode<T> node) {
if(node==null) {
node = new AVLNode<T>(data);
}
int comp = data.compareTo(node.data);
if(comp<0) {
node.left = insert(data, node.left);
if(height(node.left)-height(node.right)==2) {
if(data.compareTo(node.left.data)<0) {
node = singleRotateRight(node);
}
else {
node = doubleRotateLeftRight(node);
}
}
}
else if(comp>0) {
node.right = insert(data, node.right);
if(height(node.right)-height(node.left)==2) {
if(data.compareTo(node.right.data)<0) {
node = doubleRotateRightLeft(node);
}
else {
node = singleRotateLeft(node);
}
}
}
node.height = Math.max(height(node.left), height(node.right)) + 1;
return node;
}
|
插入操作的代码我觉得是比较有难度的，上边的插入操作的代码思路我是参考java数据结构与算法之平衡二叉树(AVL树)的设计与实现这篇博客的代码思路的
主要的思路就是利用查找树的性质，递归的找到数据要插入的位置，然后在递归返回的时候，更新结点的高度，并判断结点是否失衡了，一旦找到发现失衡点，就调用相应的旋转操作函数进行恢复。
删除操作
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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
|
public void remove(T data) {
if (data==null){
throw new RuntimeException("data can\'t not be null ");
}
this.root=remove(data,root);
}
private AVLNode<T> remove(T data,AVLNode<T> p){
if(p ==null)
return null;
int result=data.compareTo(p.data);
if(result<0){
p.left=remove(data,p.left);
if(height(p.right)-height(p.left)==2){
AVLNode<T> currentNode=p.right;
if(height(currentNode.right)>=height(currentNode.left)){
p=singleRotateLeft(p);
}else{
p=doubleRotateRightLeft(p);
}
}
}
else if(result>0){
p.right=remove(data,p.right);
if(height(p.left)-height(p.right)==2){
AVLNode<T> currentNode=p.left;
if(height(currentNode.left)>=height(currentNode.right)){
p=singleRotateRight(p);
}else{
p=doubleRotateLeftRight(p);
}
}
}
else if(p.right!=null&&p.left!=null){
p.data=findMin(p.right).data;
p.right = remove( p.data, p.right );
}
else {
p=(p.left!=null)? p.left:p.right;
}
if(p!=null)
p.height = Math.max( height( p.left ), height( p.right ) ) + 1;
return p;
}
|
删除操作跟插入操作差不多，递归地找到要删除的数据的位置，然后利用查找树删除结点的方法来删除结点，在递归返回的时候更新结点的高度，并检查判断结点是否失衡了，一旦找到发现失衡点，就调用相应的旋转操作函数进行恢复。这里强调一下，插入操作只需要如果发现失衡点，只需要一次或两次旋转就可以恢复平衡了，而删除操作有可能多次发现失衡点，因此删除操作最多要旋转操作log(n)遍。
上边讲的主要是针对插入数据时会产生的四种情况，在删除数据时又是怎么对应上边的四种情况来选择相应的旋转操作的呢，我看了好几个博客，基本都没有详细说明，只有代码，在研究删除代码的时候，我还发现了java数据结构与算法之平衡二叉树(AVL树)的设计与实现这篇博客的删除代码是有问题的，主要问题就是没有正确用上相应的旋转操作，下边我来总结一下删除数据时，出现失衡点后，怎么对应上边的四种情况选择相应的旋转操作，并给出实际的例子。
若删除的数据，是在失衡点的左子树，那么这个时候就判断一下失衡点的右孩子的左右子树的高度，若失衡点的右孩子的右子树高度大于等于左子树的高度，则该失衡点对应RR型，要对失衡点进行左旋操作；若右子树高度小于左子树，则对应RL型，要对失衡点的右孩子进行右旋操作，在对失衡点进行左旋操作。如下图的例子（用软件画图太麻烦了[捂脸]）
代码地址
参考：
java数据结构与算法之平衡二叉树(AVL树)的设计与实现
【数据结构】平衡二叉树/AVL树/——删除
