04-树5 Root of AVL Tree (25分)
04-树5 Root of AVL Tree (25分)
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 NN (\le 20≤20) which is the total number of keys to be inserted. Then NN 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:
70 Sample Input 2:
7 88 70 61 96 120 90 65 Sample Output 2:
88
AC代码:
#include <iostream>
#include <algorithm>
#include <stdlib.h>
using namespace std;
typedef struct AVLNode* AVLTree ;
struct AVLNode{
int val;
AVLTree left;
AVLTree right;
int height;
};
//求数的深度的函数
int getHeight(AVLTree t)
{
if (t)
return max(getHeight(t->left) , getHeight(t->right)) + 1;
else
return 0;
}
//左旋
AVLTree SingleLeftRotation(AVLTree a)
{
AVLTree b = a->left;
a->left = b->right;
b->right = a;
a->height = max(getHeight(a->left),getHeight(a->right))+1;
b->height = max(getHeight(b->left), a->height)+1;
return b;
}
//右旋
AVLTree SingleRightRotation(AVLTree t)
{
AVLTree b = t->right;
t->right = b->left;
b->left = t;
t->height = max(getHeight(t->left), getHeight(t->right)) + 1;
b->height = max(getHeight(b->right),t->height) + 1;
return b;
}
//左右旋
AVLTree DoubleLeftRightRotation(AVLTree t)
{
t->left = SingleRightRotation(t->left);
return SingleLeftRotation(t);
}
//右左旋
AVLTree DoubleRightLeftRotation(AVLTree t)
{
t->right = SingleLeftRotation(t->right);
return SingleRightRotation(t);
}
//插入函数
AVLTree AVL_Insertion(int x, AVLTree t)
{
/* 插入X到AVL中 并返回调整后的AVL树 */
if (!t) {
t = (AVLTree)malloc(sizeof(struct AVLNode));
t->val = x;
t->height = 0;
t->left = t->right = NULL;
}
else if (x < t->val) {
t->left = AVL_Insertion(x, t->left);
if (getHeight(t->left) - getHeight(t->right) == 2) {
/*需要左旋*/
if (x < t->left->val) {
t = SingleLeftRotation(t);/* 左单旋 */
}
else {
t = DoubleLeftRightRotation(t); /* 左右双旋 */
}
}
}
else if ( x> t->val) {
t->right = AVL_Insertion(x, t->right);
if (getHeight(t->right) - getHeight(t->left) == 2) {
/*需要左旋*/
if (x > t->right->val) {
t = SingleRightRotation(t);/* 左单旋 */
}
else {
t = DoubleRightLeftRotation(t); /* 右左双旋 */
}
}
}
t->height = max(getHeight(t->left), getHeight(t->right)) + 1;
return t;
}
//递归先序遍历
void preOrder(AVLTree avl)
{
if (avl) {
cout << avl->val << " ";
preOrder(avl->left);
preOrder(avl->right);
}
}
int main()
{
int N;
cin>>N;
AVLTree avl = NULL;
for ( int i = 0 ; i < N ; i++){
int t;
cin>>t;
avl = AVL_Insertion(t,avl);
}
cout<<avl->val;
return 0;
} 
