浙大数据结构慕课课后题（04-树5 Root of AVL Tree）

 题目要求：

AVL 树是一种自平衡的二叉搜索树。在 AVL 树中，任何节点的两个子子树的高度最多相差一;如果在任何时候它们相差不止一，则进行重新平衡以恢复此属性。图 1-4 说明了旋转规则。

 

                                图1

                                图2

                                图3

                                图4

现在给定一系列插入，您应该分辨生成的 AVL 树的根。

输入规格： 

 每个输入文件都包含一个测试用例。对于每种情况，第一行都包含一个正整数N(<=20)，这是要插入的键的总数。然后N不同的整数键在下一行中给出。一行中的所有数字都用空格分隔。

输出规格： 

 对于每个测试用例，将生成的 AVL 树的根打印在一行中。

示例输入 1： 

 5
88 70 61 96 120

 示例输出 1：

 70

题解： 

        思路如注释所示，可通过所有测试点。

#include<bits/stdc++.h>
using namespace std;   
typedef struct AVLNode *Position;
typedef Position AVLTree;
typedef int ElementType;
struct AVLNode{ElementType Data;AVLTree Left;AVLTree Right;int Hight; 
};             int Max(int a,int b){return a > b ? a:b;
}int GetHight(AVLTree A)
{return A == NULL ? -1 : A->Hight;
}AVLTree SingleLeftRotation(AVLTree A){AVLTree B = A->Left;A->Left = B->Right;B->Right = A;A->Hight = Max( GetHight(A->Left), GetHight(A->Right) ) + 1;B->Hight = Max( GetHight(B->Left), A->Hight ) + 1;return B;
}AVLTree SingleRightRotation(AVLTree A){AVLTree B = A->Right;A->Right = B->Left;B->Left = A;A->Hight = Max( GetHight(A->Left), GetHight(A->Right) ) + 1;B->Hight = Max( GetHight(B->Right), A->Hight ) + 1;return B; 
}AVLTree DoubleLeftRightRotation(AVLTree A){/* 注意：A必须有一个左子结点B，且B必须有一个右子结点C *//* 将A、B与C做两次单旋，返回新的根结点C *//* 将B与C做右单旋，C被返回 */A->Left = SingleRightRotation(A->Left);/* 将A与C做左单旋，C被返回 */return SingleLeftRotation(A);
}AVLTree DoubleRightLeftRotation(AVLTree A){A->Right = SingleLeftRotation(A->Right);return SingleRightRotation(A);	
}AVLTree Insert(AVLTree T,ElementType X){if(!T){ //若插入空树。则新建一个结点 T = (AVLTree)malloc(sizeof(struct AVLNode));T->Data = X;T->Hight = 0;T->Left = NULL;T->Right = NULL;}	else if(X < T->Data){ //插入左树 T->Left = Insert(T->Left,X);if(GetHight(T->Left)-GetHight(T->Right) == 2){   //出现不平衡           if(X < T->Left->Data)T = SingleLeftRotation(T);   //插入在左树的左边->单左旋elseT = DoubleLeftRightRotation(T);   //插入再左树的右边->左右双旋				}}else if(X > T->Data){ //插入右树T->Right = Insert(T->Right,X);if(GetHight(T->Right)-GetHight(T->Left) == 2){   //出现不平衡 if(X > T->Right->Data)T = SingleRightRotation(T);      //单右旋 elseT = DoubleRightLeftRotation(T);	 	//右左旋 }} else return T;T->Hight = Max(GetHight(T->Left),GetHight(T->Right))+1;return T;
}int main(){AVLTree T = NULL;int t;cin>>t;while(t--){int num;cin>>num;T = Insert(T,num);}cout<<T->Data;
}

此题有以下几个要注意的点：

        1.Hight是指把 一个给定结点作为根节点时，其代表的树的树高，这样当左右子树树高差大于等于2时，可以发现平衡树失衡。

        2.树高取左右子树的最大值。

        3.左右双旋的时候在代码层面实际是先右单旋再左单旋，右左单旋时同理。

这里感觉何老师的ppt很清晰，（引一下，侵删）重点是找到“麻烦结点”对“不平衡发现者”是怎样破环的