1066 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 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.

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

题目描述：平衡二叉搜索树(AVL Tree)是能够自我调整到平衡的一棵树；何为平衡二叉搜索树？

1、左子树与右子树高度之差的绝对值不超过1
2、树的每个左子树和右子树都是AVL树
3、每一个节点都有一个平衡因子（balance factor），任一节点的平衡因子是-1、0、1（每一个节点的平衡因子 = 右子树高度 - 左子树高度）

现在就是要构建一棵AVL树。

输入：第一行n为节点数；第二行n个数，为要插入的元素。

输出：将构建的AVL数的根节点输出。

解题思路：构建一棵树，用结构体记录每个节点的信息，包括节点的值、左右子树的指针；一开始很难理解怎么转，仔细分析下，也就四种旋转（左旋转，右旋转，左右旋转、右左旋转），有点蒙？画个图就清晰了。灵魂画手上线：

1、右旋转：插入的是数据C，C<B<A

2、左右旋转：插入的是数据C，B<C<A

3、左旋转：插入数据是C，C>B>A

4、右左旋转：插入数据是C，B>C>A

#include<bits/stdc++.h>
using namespace std;
struct node{
	int val;
	node *left, *right;
};

node *routerRight(node *root){
	node *t = NULL;
	t = root->left;
	root->left = t->right;
	t->right = root;
	return t;
}
node *routerLeft(node *root){
	node *t = NULL;
	t = root->right;
	root->right = t->left;
	t->left = root;
	return t;
}

node *routerLeftRight(node *root){
	root->left = routerLeft(root->left);
	return routerRight(root);
}

node *routerRightLeft(node *root){
	root->right = routerRight(root->right);
	return routerLeft(root);
}

int height(node *root){
	if(root==NULL) return 0;
	return max(height(root->left),height(root->right))+1;
}
node *insert(node *root, int val){
	if(root==NULL){
		root = new node();
		root->val = val;
		root->left = root->right = NULL;
	}
	else if(val < root->val){
		root->left = insert(root->left,val);
		if(height(root->left)-height(root->right)==2){
			root = val < root->left->val ? routerRight(root):routerLeftRight(root);
		}
	}
	else{
		root->right = insert(root->right,val);
		if(height(root->right)-height(root->left)==2){
			root = val > root->right->val ? routerLeft(root):routerRightLeft(root); 
		}
	}
	return root;
}
int n;
int main()
{
	int m;
	scanf("%d", &n);
	node *root = NULL;
	for(int i=0; i<n; i++){
		scanf("%d", &m);
		root = insert(root,m);
	}
	printf("%d", root->val);
	return 0;
}