二叉平衡树(AVL tree)

适用组别:提高组
难度系数:8

一、二叉平衡树(Balanced Binary Tree)
又被称为AVL树(AVL是三个发明人名子的首子母)。
具有以下性质:
1、它是一棵二叉搜索树(binary search tree)。
2、它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1;
3、并且左右两个子树都是一棵平衡二叉树。

这个方案很好的解决了二叉查找树退化成链表的问题,把插入,查找,删除的时间复杂度最好情况和最坏情况都维持在O(logN)。

但是频繁旋转会使插入和删除牺牲掉O(logN)左右的时间,不过相对二叉查找树来说,时间上稳定了很多。


二、理想平衡与适度平衡
理想平衡就是左子树和右子树的高度一样,适度平衡就是放松平衡标准,大体上平衡就可以。
例如:AVL树的左右子树高差不大于1。


三、调平衡

找到最小不平衡子树,从这个树的根a开始调整

把需要重新平衡的结点叫做α,由于任意两个结点最多只有两个儿子,因此高度不平衡时,α结点的两颗子树的高度相差2.容易看出,这种不平衡可能出现在下面4中情况中:
1. α的左子树的左子树
2. α的左子树的右子树
3. α的右子树的左子树
4. α的右子树的右子树

调整平衡


四、插入

1、如果平衡二叉树为空,则创建新节点
2、如果node->data=x,已经存在x,什么也不做
3、如果x< node-data,插入到左子树,否则插入到右子树
4、调平衡


五、删除操作

同插入操作一样,删除结点时也有可能破坏平衡性,这就要求我们删除的时候要进行平衡性调整。

1、如果平衡二叉树为空,则什么也不做。
2、如果node->data==x,找到要删除结点,如果node有一个孩子,让孩子顶替,否则令其直接前驱(或者直接后继)代替。然后删除其直接前驱(或直接后继)
3、如果x<node->data,到左子树查找并删除,否则到右子树查找删除
4、重新调整平衡


代码实现:

  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
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
/**************************************************************** 
 * Description: C++ implementation of self balancing binary search tree
 * Author: Alex Li
 * Date: 2023-06-27 18:16:01
 * LastEditTime: 2023-06-29 16:24:48
****************************************************************/
#include <iostream>
using namespace std;

//结点结构体,一个数据域,一个高度域,两个指针域,分别指向左右结点
struct Node{
    int data;
    int height;
    struct Node  *left;
    struct Node *right; 
};

//计算高度
int Height(Node *N){
    if(N!=NULL)return N->height;
    else return 0;
}

//更新高度
void UpdateHeight(Node *N){
    if(N!=NULL)N->height =max(Height(N->left),Height(N->right))+1;
    else return;
}

// 创建新结点
Node *newNode(int data) {
  Node *node = new Node();
  node->data = data;
  node->left = NULL;
  node->right = NULL;
  node->height = 1;
  return node;
}

// left left rotation  左左旋转
Node *LL_Rotate(Node *y) {
  Node *x = y->left;
  y->left = x->right;
  x->right = y;
  UpdateHeight(y);
  UpdateHeight(x); //x基于y计算高度,所以必须先算y
  return x;
}

// right right rotaion  右右旋转 
Node *RR_Rotate(Node *y) {
  Node *x = y->right;
  y->right=x->left;
  x->left =y;
  UpdateHeight(y);
  UpdateHeight(x);//x基于y计算高度,所以必须先算y
  return x;
}
// left right rotaion  左右旋转 
Node *LR_Rotate(Node *y){
     Node *x=y->left->right;
     //Node *z=y->left;
     y->left->right=x->left;
     x->left=y->left;
     y->left=x->right;
     x->right=y;
     return x;
//可以用下面丙行代码替代上面代码。
    // y->left= RR_Rotate(y->left);
    // return LL_Rotate(y);

}

Node *RL_rotate(Node *y){
     Node *x=y->right->left;
     y->right->left=x->right;
     x->left=y->right;
     y->right=x->right;
     x->left=y;
     return x;
     ////可以用下面丙行代码替代上面代码。
    // y->right= LL_Rotate(y->right);
    // return RR_Rotate(y);
}

// Get the balance factor of each node
int getBalanceFactor(Node *N) {
  if (N == NULL)
    return 0;
  return Height(N->left) -Height(N->right);
}

Node *AdjustBalance(Node *node){
   
   if(node==NULL)return node;
    int balanceFactor = getBalanceFactor(node);
  if (balanceFactor > 1) {//沿着高的哪棵子树调整
    if(Height(node->left->left)>=Height(node->left->right))
      
        node=LL_Rotate(node);
    else
      node=LR_Rotate(node);
  }
  else if (balanceFactor < -1) {
    if (Height(node->right->right)>=Height(node->right->left)) 
      node=RR_Rotate(node);
    else
      node=RL_rotate(node); 
  }

  return node;
}

// Insert a node
Node *insertNode(Node *node, int data) {
  // Find the correct postion and insert the node
  if (node == NULL){
    node=newNode(data);
    return node;
  }
  if (data < node->data)
    node->left = insertNode(node->left, data);
  else if(data>node->data)
    node->right = insertNode(node->right, data);
  

  // Update the balance factor of each node and
  // balance the tree
  UpdateHeight(node);
  node=AdjustBalance(node);
  
  return node;
}


// Delete a node
 Node *DeleteNode(Node *node, int data) {
   if(node==NULL)return node;
   if(node->data==data){  //找到要删除的节点
        if(!node->left||!node->right){   //如果有一个孩子为空,子承父业
          Node *temp=node;
          node=(node->left)?node->left:node->right;
          delete temp;
        }
         else{  //选其直接前驱(也就是左子树的最右节点)代替,然后删除其直接前驱
          Node *temp;
          temp=node->left;
          while(temp->right)temp=temp->right;
          node->data=temp->data;
          node->left=DeleteNode(node->left,node->data);
        }
   }
   else if(node->data>data)
        node->left=DeleteNode(node->left,data); //在左子树中删除
   else 
        node->right=DeleteNode(node->right,data); //在右子树中删除
   UpdateHeight(node);
   node=AdjustBalance(node);
   return node;
}

//前序遍历查看结果
void Inorder(Node *node){
  if(node==NULL)  return ;
  Inorder(node->left);
  cout<<node->data<<"\t"<<node->height<<endl;
  Inorder(node->right);
}

int main() {
  Node *node = NULL;
  node = insertNode(node, 33);
  node = insertNode(node, 13);
  node = insertNode(node, 53);
  node = insertNode(node, 9);
  node = insertNode(node, 21);
  node = insertNode(node, 61);
  node = insertNode(node, 8);
  node = insertNode(node, 11);
  node = insertNode(node,7);
  
  Inorder(node);
  
  node = DeleteNode(node, 61);
  cout << "After deleting " << endl;
  Inorder(node);
  
  
}
Scroll to Top