中国大学MOOC数据结构基础习题集、041、Root of AVL Tree

题目链接：http://www.patest.cn/contests/mooc-ds/04-1

题目分析：这是一颗平衡二叉树的“创建”问题。

　　输入：不断向树中增加新的结点，并通过左旋、右旋等操作调整树，使树保持平衡性。

　　输出：根结点的data区即可。

　　如果你没有看老师留下来的PPT，那么这时候不妨来回顾一下：

　　http://www.icourse163.org/learn/zju-93001#/learn/content?type=detail&id=404030&cid=433118

　　http://www.icourse163.org/learn/zju-93001#/learn/content?type=detail&id=404030&cid=475011

代码分析：

　　头文件声明：1~6

　　定义”平衡树结点“的结构体：7~16

　　获取当前结点的高度：17~22

　　四种旋转（就是按老师给的算法一点点改的，具体请参见注释）：23~60

　　插入结点的具体算法：61~107

　　主函数：108~124

  1 #include <iostream>
  2 #include <fstream>
  3 #include <cmath>
  4 
  5 using namespace std;
  6 
  7 template <class T>
  8 struct AVLTreeNode
  9 {
 10     T Data;
 11     AVLTreeNode<T>* Left;
 12     AVLTreeNode<T>* Right;
 13     int Height;
 14     AVLTreeNode(int value):Data(value),Left(NULL),Right(NULL),Height(0){}
 15 };
 16 
 17 template <class T>
 18 int GetHeight(AVLTreeNode<T>* ROOT){
 19     if(ROOT== NULL)return -1;
 20     return ROOT->Height;
 21 }
 22 
 23 template <class T>
 24 AVLTreeNode<T>* SingleLeftRotation(AVLTreeNode<T>* A){
 25     AVLTreeNode<T>* B = A -> Left;
 26     A -> Left = B -> Right;
 27     B -> Right = A;
 28     A -> Height = max(GetHeight(A->Left), GetHeight(A->Right)) +1;
 29     B -> Height = max(GetHeight(B->Left), A->Height) +1;
 30     return B;
 31 }
 32 
 33 template <class T>
 34 AVLTreeNode<T>* SingleRightRotation(AVLTreeNode<T>* A){
 35     AVLTreeNode<T>* B = A -> Right;
 36     A -> Right = B -> Left;
 37     B -> Left = A;
 38     A -> Height = max(GetHeight(A->Left), GetHeight(A->Right)) +1;
 39     B -> Height = max(GetHeight(B->Left), A->Height) +1;
 40     return B;
 41 }
 42 
 43 template <class T>
 44 AVLTreeNode<T>* DoubleLeftRightRotation(AVLTreeNode<T>* A){
 45     /*  注意：A 必须有一个左子结点 B，且 B 必须有一个右子结点 C */
 46     /*  将 A、B 与 C 做如图 4.38 所示的两次单旋，返回新的根结点 C */
 47     A->Left = SingleRightRotation(A->Left); /*将 B 与 C 做右单旋，C 被返回*/
 48     return SingleLeftRotation(A); /*将 A 与 C 做左单旋，C 被返回*/
 49 
 50     return A;
 51 }
 52 
 53 template <class T>
 54 AVLTreeNode<T>* DoubleRightLeftRotation(AVLTreeNode<T>* A){
 55     A->Right = SingleLeftRotation(A->Right); /*将 B 与 C 做右单旋，C 被返回*/
 56     return SingleRightRotation(A); /*将 A 与 C 做左单旋，C 被返回*/
 57 
 58     return A;
 59 }
 60 
 61 template <class T>
 62 AVLTreeNode<T>* InsertNode(T X, AVLTreeNode<T>* ROOT)
 63 {
 64     // 将 X 插入 AVL 树 T 中，并且返回调整后的 AVL 树
 65 
 66     if ( !ROOT ) // 若插入空树，则新建包含一个结点的树
 67     {
 68         ROOT = new AVLTreeNode<int>(X);
 69     } // if (插入空树)  结束
 70 
 71     else if (X < ROOT->Data) //  插入 T 的左子树
 72     {
 73         ROOT->Left = InsertNode(X, ROOT->Left);
 74         if (GetHeight(ROOT->Left) - GetHeight(ROOT->Right) == 2 )
 75         {
 76             // 需要左旋
 77             if (X < ROOT->Left->Data)
 78                 ROOT = SingleLeftRotation(ROOT);      //  左单旋
 79             else
 80                 ROOT = DoubleLeftRightRotation(ROOT); //  左-右双旋
 81         }
 82 
 83     } // else if (插入左子树)  结束
 84 
 85     else if (X > ROOT->Data)   //  插入 T 的右子树
 86     {
 87         ROOT->Right = InsertNode(X, ROOT->Right);
 88         if (GetHeight(ROOT->Left) - GetHeight(ROOT->Right) == -2 )
 89         {
 90             // 需要右旋
 91             if (X > ROOT->Right->Data)
 92                 ROOT = SingleRightRotation(ROOT);     // 右单旋
 93             else
 94                 ROOT = DoubleRightLeftRotation(ROOT); // 右-左双旋
 95         }
 96 
 97     } //else if (插入右子树)  结束
 98 
 99     // else X == T->Data，无须插入
100 
101     // 更新树高
102     ROOT->Height = GetHeight(ROOT->Left) > GetHeight(ROOT->Right) ? GetHeight(ROOT->Left) + 1 : GetHeight(ROOT->Right) + 1;
103 
104     return ROOT;
105 
106 }
107 
108 int main()
109 {
110     int n;
111     cin>>n;
112 
113     AVLTreeNode<int>* root = NULL;
114 
115     int x;
116     int i;
117     for(i=0; i<n; i++)
118     {
119         cin>>x;
120         root = InsertNode(x, root);
121     }
122     cout<< root->Data <<endl;
123     return 0;
124 }

AC成果：