【树】Root of AVL Tree

【树】Root of AVL Tree

题目要求：

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.

输入格式：

Each input file contains one test case. For each case, the first line contains a positive integer N (≤20) 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.

输出格式：

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

输入样例1：

5 88 70 61 96 120

输出样例1：

7 88 70 61 96 120 90 65

输入样例2：

5 88 70 61 96 120

输出样例2：

88

解题思路：

题目给出序列，根据序列建AVL树然后输出根结点的值。其实核心就在于建树，采用插入的方式建二叉查找树，每当插入一个结点时判定是否平衡，然后采用对应的旋转方式：LL旋转、RR旋转、LR旋转、RL旋转。

完整程序：

/* 【解题思路】 题目给出序列，根据序列建AVL树然后输出根结点的值。其实核心就在于建树，采用插入的方式建二叉查找树，每当插入一个结点时判定是否 平衡，然后采用对应的旋转方式：LL旋转、RR旋转、LR旋转、RL旋转 */ #include <stdio.h> #include <stdlib.h> typedef struct TreeNode *Tree; struct TreeNode { int Data; Tree Left; Tree Right; }; Tree BuildTree(int n); // 建树 Tree BuildNode(int data); // 建树结点 int Height(Tree T); // 求树高度 Tree Insert(Tree T,int data); // 结点插入，注意因为是AVL树，因此需要特殊判断 Tree LLrotation(Tree T); // LL旋转 Tree RRrotation(Tree T); // RR旋转 Tree LRrotation(Tree T); // LR旋转 Tree RLrotation(Tree T); // RL旋转 int main() { int N; // 树结点数 Tree T; scanf("%d",&N); T = BuildTree(N); printf("%d\n",T -> Data); return 0; } Tree BuildTree(int n) { Tree T; int i,data; scanf("%d",&data); T = BuildNode(data); for(i = 1;i < n;i ++) { scanf("%d",&data); T = Insert(T,data); } return T; } Tree BuildNode(int data) { Tree T = (Tree)malloc(sizeof(struct TreeNode)); T -> Data = data; T -> Left = NULL; T -> Right = NULL; return T; } int Height(Tree T) { int hl,hr; // 左子树和右子树高度 int max; if(T) { hl = Height(T -> Left); hr = Height(T -> Right); max = hl > hr ? hl : hr; max = max + 1; // 左或右子树的最大高度加1就是树的最大高度 return max; } else return 0; // 空树 } Tree Insert(Tree T,int data) { if(!T) // 如果是空树，就建立一个新结点作为空结点 T = BuildNode(data); else { if(data > T -> Data) { T -> Right = Insert(T -> Right,data); /*因为是AVL树，一定要判断树是否平衡*/ if(Height(T -> Right) - Height(T -> Left) > 1) { if(data < T -> Right -> Data) T = RLrotation(T); // RL旋转 else T = RRrotation(T); // RR旋转 } } else { T -> Left = Insert(T -> Left,data); /*因为是AVL树，一定要判断树是否平衡*/ if(Height(T -> Left) - Height(T -> Right) > 1) { if(data < T -> Left -> Data) T = LLrotation(T); // LL旋转 else T = LRrotation(T); // LR旋转 } } } return T; } Tree LLrotation(Tree T) { Tree a = T; // 记录树根结点 Tree b = a -> Left; // 根结点的左孩子 Tree bl = b -> Left, br = b -> Right,ar = a -> Right; // 根结点左孩子的左孩子，根结点左孩子的右孩子，根结点的右孩子 b -> Left = bl; b -> Right = a; a -> Left = br; a -> Right = ar; return b; } Tree RRrotation(Tree T) { Tree a = T; Tree b = a -> Right; Tree al = a -> Left,bl = b -> Left,br = b -> Right; b -> Left = a; b -> Right = br; a -> Left = al; a -> Right = bl; return b; } Tree LRrotation(Tree T) { Tree a = T; Tree b = a -> Left; Tree c = b -> Right; Tree bl = b -> Left,cl = c -> Left,cr = c -> Right,ar = a -> Right; c -> Left = b; c -> Right = a; b -> Left = bl; b -> Right = cl; a -> Left = cr; a -> Right = ar; return c; } Tree RLrotation(Tree T) { Tree a = T; Tree b = a -> Right; Tree c = b -> Left; Tree al = a -> Left,cl = c -> Left,cr = c -> Right,br = b -> Right; c -> Left = a; c -> Right = b; a -> Left = al; a -> Right = cl; b -> Left = cr; b -> Right = br; return c; }