1066 Root of AVL Tree (25分)(AVL树的实现)

An AVL tree is a self-balancing binary search tree. In an AVL tree, the heights of the two child subtrees of any node differ by at most one; if at any time they differ by more than one, rebalancing is done to restore this property. Figures 1-4 illustrate the rotation rules.

Now given a sequence of insertions, you are supposed to tell the root of the resulting AVL tree.

Input Specification:

Each input file contains one test case. For each case, the first line contains a positive integer N (≤) which is the total number of keys to be inserted. Then N distinct integer keys are given in the next line. All the numbers in a line are separated by a space.

Output Specification:

For each test case, print the root of the resulting AVL tree in one line.

Sample Input 1:

5

88 70 61 96 120

Sample Output 1:

Sample Input 2:

7

88 70 61 96 120 90 65

Sample Output 2:

88

题目分析：写一个AVL树 背课文是好的 但也要理解清除AVL树的原理 之后还要学习各种平衡树 如红黑树什么的

 #define _CRT_SECURE_NO_WARNINGS

 #include <climits>

 #include<iostream>

 #include<vector>

 #include<queue>

 #include<map>

 #include<set>

 #include<stack>

 #include<algorithm>

 #include<string>

 #include<cmath>

 using namespace std;

 typedef struct TNode* Tree;

 struct TNode {

     int Data;

     Tree TL;

     Tree TR;

     int Height;  //要初始化为-1;

 };

 int GetHeight(Tree T) {

     if (T)

         return T->Height;

     else

         return -;

 }

 Tree singleLeftRotate(Tree T) {

     Tree TL = T->TL;

     T->TL = TL->TR;

     TL->TR = T;

     T->Height = max(GetHeight(T->TL), GetHeight(T->TR)) + ;

     TL->Height = max(GetHeight(TL->TL), GetHeight(TL->TR)) + ;

     return TL;

 }

 Tree singleRightRotate(Tree T) {

     Tree TR = T->TR;

     T->TR = TR->TL;

     TR->TL = T;

     T->Height = max(GetHeight(T->TL), GetHeight(T->TR)) + ;

     TR->Height = max(GetHeight(TR->TL), GetHeight(TR->TR)) + ;

     return TR;

 }

 Tree doubleLeftRightRotate(Tree T) {

     T->TL = singleRightRotate(T->TL);

     return singleLeftRotate(T);

 }

 Tree doubleRightLeftRotate(Tree T) {

     T->TR = singleLeftRotate(T->TR);

     return singleRightRotate(T);

 }

 Tree Insert(Tree T,int data) {

     if (!T)

     {

         T = new TNode();

         T->Data = data;

         T->Height = ;

         T->TL = T->TR = NULL;

     }

     else if (data > T->Data) {

         T->TR = Insert(T->TR, data);

         T->Height = max(GetHeight(T->TL), GetHeight(T->TR)) + ;

         if (GetHeight(T->TR) - GetHeight(T->TL) == ) {

             if (data > T->TR->Data)

                 T=singleRightRotate(T);

             else

                 T=doubleRightLeftRotate(T);

         }

     }

     else {

         T->TL = Insert(T->TL, data);

         T->Height = max(GetHeight(T->TL), GetHeight(T->TR)) + ;

         if (GetHeight(T->TL) - GetHeight(T->TR) == ) {

             if (data < T->TL->Data)

                 T=singleLeftRotate(T);

             else

                 T=doubleLeftRightRotate(T);

         }

     }

     return T;

 }

 int main()

 {

     int N;

     Tree T = NULL;

     int data;

     cin >> N;

     for (int i = ; i < N; i++)

     {

         cin >> data;

         T = Insert(T, data);

     }

     cout << T->Data;

 }

巴特西