题目要求:
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很清晰,(引一下,侵删)重点是找到“麻烦结点”对“不平衡发现者”是怎样破环的