[算法]平衡二叉树🌲

理解 78%

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

typedef struct AVLNode{
    int data;
    int height;
    struct AVLNode *lchild;
    struct AVLNode *rchild;    
}*AVLTree,Avlnode;
//  0.清倒垃圾

AVLTree Insert(AVLTree &T,int x);
AVLTree CreateAVL(AVLTree &T);
AVLTree Empty(AVLTree &T);

AVLTree Empty(AVLTree &T){
    if (T == NULL) return NULL;
    Empty(T->lchild);
    Empty(T->rchild);
    delete T;
    return NULL;
    // 释放空间做回自我
}
// 0. 杂
   // 获得高度
   inline int Height(AVLTree T){
       if(T == NULL) return 0;
       return T->height;
   }

   // 更新高度
   void updateHeight(AVLTree &T){
      T->height = max(Height(T->lchild),Height(T->rchild))+1;
   }
// ==================================================
   // LL转
   AVLTree LL_Rotation(AVLTree  &T){
       AVLTree temp = T->lchild;
       T->lchild = temp->rchild;
       temp->rchild = T;
       updateHeight(T);
       updateHeight(temp);
       return temp;

   }

   AVLTree RR_Rotation(AVLTree  &T){
     AVLTree temp = T->rchild;
     T->rchild = temp->lchild;
     temp->lchild = T;
     updateHeight(temp);
     updateHeight(T);
     return temp;
   }

   AVLTree LR_Rotation(AVLTree  &T){ // LR旋转
      T->lchild = RR_Rotation(T->lchild);
      return LL_Rotation(T);
   }
   
   AVLTrees RL_Rotation(AVLTree &T){
      T->rchild = LL_Rotation(T->rchild);
      return RR_Rotation(T);
   }
   //================================================



// ________________________________________五毛钱的分割线



// 1. 创建树🌲
AVLTree CreateAVL(AVLTree &T){
    // 创建 开始
    int n,x;
    cout <<"请输入要创建多少个节点：";
    cin >> n;
    cout << " 下面请输入"<<n<<"个数据!!:";

    for (int  i = 0; i < count; i++){
        cin >> x;
        T = Insert(T,x); // 
    }
}

// 2. 插入树🌲
AVLTree Insert(AVLTree &T,int x){
   // 原来是通过递归来做一些事情阿...
   //  好家伙了
    

    // 🥇插入核心
    if( T == NULL){
        T = new Avlnode;
        T->lchild = T->rchild = NuLL;
        T->data = x;
        T->height = 1;
        return T;
    }

    // 🥈查找成功啥也不作
    if (T->data == x) return T;

    // 🥉 开始正餐

    if(x < T->data){
        // 插入到左子树🌲
        T->lchild = Insert(T->lchild,x);
        // Insert Complete

        //============False WARNING WARNING CODE =========
           // 判断高度合法性了
           if(Height(T->lchild) - Height(T->rchild) == 2){
                // 出现不平衡
                if(x < T->lchild->data){
                    T = LL_Rotation(T);
                }else{
                    T = LR_Rotation(T);
                }           
           }

    }else{
        // 插入到右子树🌲
        T->rchild = Insert(T->rchild,x);
        // Insert Complete

        //============False WARNING WARNING CODE =========
        if(Height(T->lchild) - Height(T->rchild) == 2){
             // over,over , Here need noteing.😎  [ ]  
            if(x < T->rchild->data){
                T= RR_Rotation(T);
            }else{
                T = RL_Rotation(T);
            }
        }

    }
    

    //  😺搞完数据就更新了🐶
    updateHeight(T);
    return T;   

}

// 3.1 删除树 🌲
AVLTree Delete(AVLTree &T,int x){  
    if(T==NULL) return NULL; //如果没找到就返回🈳
    
    if(T->data==x){ // 如果找到了
    // over,over , Here need noteing.😎  [ ] 
         if(T->rchild == NULL){ // 如果右树为空 ，那么直接删除
            AVLTree temp = T;
            T = T->lchilde;
            delete temp;
            
         }else{
            // 否则，将其右子树最左孩子
            AVLTree temp;
            temp = T->rchild;
            while(temp->lchild){
                temp = temp->lchild;
            }
            T->data = temp->data;
            T->rchild = Delete(T->rchild,T->data);
            updateHeight(T);
         }
         return T;

    }

    // 不是就开始寻找
    if(T->data > x) T->lchild = Delete(T->lchild,x);
    if(T->data < x) T->rchild = Delete(T->rchild,x);

    // 擦屁股操作 
    updateHeight(T); // 删除完毕更新 树的高度
    T = adjust(T); -// 调整树；
}


// 3.2 检测删除后是否还是平衡  adjust=》调整🍫
AVLTree adjust(AVLTree &T){
  if(T == NULL) return NULL;

  if(Height(T->lchild) - Height(T->rchild) == 2){
    // over,over , Here need noteing.😎  [ ] 
     if(Height(T->lchild->lchild) >= Height(T->lchild->rchild)){
        T = LL_Rotation(T);
     }else{
        T = LR_Rotation(T);
     }
  }

  if(Height(T->rchild) - Height(T->lchild) == 2){
      if(Height(T->rchild->rchild) >= Height(T->rchild->lchild)){
        T = RR_Rotation(T);
      }else{
        T = RL_Rotation(T);
      }
  }
  updateHeight(T);
  return T;

}

int main(){
   // Step1.平衡二叉树的创建
   int x;
   AVLTree root = NULL;
   root = Empty(root); // 删除树？？？
   CreateAVL(root);


}