平衡二叉树

平衡二叉树(AVL)是一种特殊的二叉搜索树，他满足两个性质：

1. 此树是二叉搜索树

2. 任意节点的左右子树高度差的绝对值不超过1

这样是为了提高查询的效率，因为一般的二叉搜索树有可能不会是完全二叉树或者接近完全二叉树情况，有的甚至退化成链表，所以平衡二叉树将二叉树平衡一下，使得查询效率满足logn，主要有四种情况，一种是LL型，RR型，LR型，RL型，具体见代码实现：

  1 #include <iostream>
  2 #include <algorithm>
  3 #include <stdlib.h>
  4 using namespace std;
  5 typedef struct AVLTree{
  6     int data;
  7     struct AVLTree *lchild, *rchild;
  8     int height;
  9 }AVLTree, *PAVLTree;
 10 int getHeight(PAVLTree T)
 11 {
 12     int height = 0;
 13     if (T != NULL)
 14     {
 15         height = 1;
 16         if (T->lchild != NULL)
 17             height = T->lchild->height + 1;
 18         if (T->rchild != NULL)
 19             height = max(height, T->rchild->height) + 1;
 20     }
 21     return height;
 22     //recursion version
 23 //    if (T != NULL)
 24 //        return max(getHeight(T->lchild), getHeight(T->rchild)) + 1;
 25 //    else
 26 //        return 0;
 27 }
 28 //LL type
 29 PAVLTree SingleLeft(PAVLTree A)
 30 {
 31     PAVLTree B = A->lchild;
 32     A->lchild = B->rchild;
 33     B->rchild = A;
 34     A->height = max(getHeight(A->lchild), getHeight(A->rchild)) + 1;
 35     B->height = max(getHeight(B->lchild), getHeight(B->rchild)) + 1;
 36     return B;
 37 }
 38 //RR type
 39 PAVLTree SingleRight(PAVLTree A)
 40 {
 41     PAVLTree B = A->rchild;
 42     A->rchild = B->lchild;
 43     B->lchild = A;
 44     //update height
 45     A->height = max(getHeight(A->lchild), getHeight(A->rchild));
 46     B->height = max(getHeight(B->lchild), getHeight(B->rchild));
 47     return B;
 48 }
 49 //LR type
 50 PAVLTree Double_Left_Right(PAVLTree A)
 51 {
 52     A->lchild = SingleRight(A->lchild);
 53     return SingleLeft(A);
 54 }
 55 //RL type
 56 PAVLTree Double_Right_Left(PAVLTree A)
 57 {
 58     A->rchild = SingleLeft(A->rchild);
 59     return SingleRight(A);
 60 }
 61 //insert function
 62 PAVLTree insert_AVL_tree(int data, PAVLTree T)
 63 {
 64     //the process same as binary search tree, but keep balance of the tree after inserted data
 65     if (T == NULL)
 66     {
 67         T = (PAVLTree)malloc(sizeof(AVLTree));
 68         T->data = data;
 69         T->lchild = T->rchild = NULL;
 70         T->height = 0;
 71     }
 72     if (data < T->data)
 73     {
 74         T->lchild = insert_AVL_tree(data, T->lchild);
 75         //if can not meeting the conditions
 76         if (getHeight(T->lchild) - getHeight(T->rchild) == 2)
 77         {
 78             if (data < T->lchild->data)
 79             {
 80                 T = SingleLeft(T);
 81             }
 82             else
 83                 T = Double_Left_Right(T);
 84         }
 85     }
 86     //if can not meeting the conditions
 87     else if (data > T->data)
 88     {
 89         T->rchild = insert_AVL_tree(data, T->rchild);
 90         if (getHeight(T->lchild) - getHeight(T->rchild) == -2)
 91         {
 92             if (data > T->rchild->data)
 93                 T = SingleRight(T);
 94             else
 95                 T = Double_Right_Left(T);
 96         }
 97     }
 98     //update the height
 99     T->height = max(getHeight(T->lchild), getHeight(T->rchild)) + 1;
100 
101     return T;
102 
103 
104 }
105 //previous order traverse
106 void preOrderTraverse(PAVLTree T)
107 {
108     if (T != NULL)
109     {
110         cout << T->data << " ";
111         preOrderTraverse(T->lchild);
112         preOrderTraverse(T->rchild);
113     }
114 }
115 int main()
116 {
117     int n;
118     cin >> n;//the number of test data
119     int t;
120     PAVLTree root = NULL;
121     for (int i = 0; i < n; i++)
122     {
123         cin >> t;
124         root = insert_AVL_tree(t, root);//create the AVL tree
125     }
126     preOrderTraverse(root);//show the result
127     return 0;
128 }