AVL树代码实现

AVL树，二叉平衡树。一共四种调整方法。

LL

RR

LR

RL

  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 struct Node{
  4     Node *left;
  5     Node *right;
  6     int val;
  7     int height;
  8
  9     void UpdateHeight(){
 10         int Left = left ? left->height : 0;
 11         int Right = right ? right->height : 0;
 12         height = max(Left, Right) + 1;
 13     }
 14
 15     int cal_height(){
 16         int Left = left ? left->height : 0;
 17         int Right = right ? right->height : 0;
 18         return Left - Right;
 19     }
 20 };
 21 Node* LL(Node* node){
 22     Node* Right = node->right;
 23     Node* Left = Right->left;
 24     Right->left = node;
 25     node->right = Left;
 26     node->UpdateHeight();
 27     Right->UpdateHeight();
 28     return Right;
 29 }
 30 Node* RR(Node* node){
 31     Node* Left = node->left;
 32     Node* Right = Left->right;
 33     Left->right = node;
 34     node->left = Right;
 35     node->UpdateHeight();
 36     Left->UpdateHeight();
 37     return Left;
 38 }
 39 Node *RL(Node* node){
 40     node->right = RR(node->right);
 41     return LL(node);
 42 }
 43 Node *LR(Node* node){
 44     node->left = LL(node->left);
 45     return RR(node);
 46 }
 47 Node* Insert(Node* node, int val){
 48     if(node == NULL){
 49         node = new Node();
 50         node->val = val;
 51      //   return node;
 52     }
 53     else if(val > node->val){
 54         node->right = Insert(node->right, val);
 55         int Height = node->cal_height();
 56         if(Height == -2){
 57             if(val > node->right->val){
 58                 node = LL(node);
 59             }
 60             else node = RL(node);
 61         }
 62     }
 63     else {
 64         node->left = Insert(node->left, val);
 65         int Height = node->cal_height();
 66         if(Height == 2){
 67             if(val < node->left->val){
 68                 node = RR(node);
 69             }
 70             else node = LR(node);
 71         }
 72     }
 73     node->UpdateHeight();
 74     return node;
 75 }
 76
 77 void pre_travel(Node* node)
 78 {
 79     if(node==NULL) return;
 80     printf("%d ",node->val);
 81     pre_travel(node->left);
 82     pre_travel(node->right);
 83 }
 84
 85 int main(){
 86    Node *root = NULL;
 87     root = Insert(root, 5);
 88  //   cout << 5 << endl;
 89     root = Insert(root, 6);
 90  //   cout << 6 << endl;
 91     root = Insert(root, 3);
 92  //   cout << 3 << endl;
 93    // root = Insert(root, 3);
 94     root = Insert(root, 2);
 95 //    cout << 2 << endl;
 96     root = Insert(root, 4);
 97 //    cout << 4 << endl;
 98     root = Insert(root, 1);
 99  //   cout << 1 << endl;
100     root = Insert(root, 9);
101     cout << 9 << endl;
102     root = Insert(root, 8);
103     cout << 8 << endl;
104     root = Insert(root, 7);
105     cout << 7 << endl;
106     printf("先序遍历\n");
107     pre_travel(root);
108     printf("\n");
109     return 0;
110 }