二叉平衡树(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、重新调整平衡

代码实现：

/**************************************************************** 
 * 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);
  
  
}

I9633，P3369

Back to Lesson

Next Topic

数据结构与算法

二叉平衡树(AVL tree)