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 ythe 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

#include <stdio.h>

struct Node {

	int val;

	int height;

	struct Node *left;

	struct Node *right;

};

int max(int a, int b) {				//返回两者较大者

	return a > b ?

a : b;

}

int height(struct Node* root) {		//为了兼容空树，树高度不能直接返回根节点的height属性

	if (root == NULL) {

		return -1;

	}

	else {

		return root->height;

	}

}

struct Node* RRrotation(struct Node* k1) {		//右右旋转

	struct Node* k2 = k1->right;		//k2为根节点k1的右儿子

	k1->right = k2->left;				//将k2的左儿子连接到k1的右子节点

	k2->left = k1;						//将k1连接到k2的左子节点

	k1->height = max(height(k1->left), height(k1->right)) + 1;	//更新节点高度，仅仅有k1，k2节点高度变化

	k2->height = max(height(k2->left), height(k2->right)) + 1;

	return k2;

}

struct Node* LLrotation(struct Node* k1) {		//左左旋转

	struct Node* k2 = k1->left;

	k1->left = k2->right;

	k2->right = k1;

	k1->height = max(height(k1->left), height(k1->right)) + 1;

	k2->height = max(height(k2->left), height(k2->right)) + 1;

	return k2;

}

struct Node* RLrotation(struct Node* k1) {		//右左旋转

	//分两步：先对根节点的右子树做左左旋转。再对根做右右旋转

	k1->right = LLrotation(k1->right);

	return RRrotation(k1);

}

struct Node* LRrotation(struct Node* k1) {		//左右旋转

	k1->left = RRrotation(k1->left);

	return LLrotation(k1);

}

struct Node* insertAvlTree(struct Node* node, struct Node* root) {

	if (root == NULL) {

		root = node;

		return root;

	}

	if (node->val > root->val) {

		root->right = insertAvlTree(node, root->right);		//插入右子树

		if (height(root->right) - height(root->left) == 2) {

			if (node->val > root->right->val) {				//假设插入右子树的右子树，进行右右旋转

				root = RRrotation(root);

			}

			else if (node->val < root->right->val) {		//进行右左旋转

				root = RLrotation(root);

			}

		}

	}

	else if (node->val < root->val) {		//插入左子树情况与上面相似

		root->left = insertAvlTree(node, root->left);

		if (height(root->left) - height(root->right) == 2) {

			if (node->val < root->left->val) {

				root = LLrotation(root);

			}

			else if(node->val > root->left->val) {

				root = LRrotation(root);

			}

		}

	}

	//递归中不断更新插入节点到根节点路径上全部节点的高度

	root->height = max(height(root->left), height(root->right)) + 1;

	return root;

}

int main() {

	freopen("test.txt", "r", stdin);

	int n;

	scanf("%d", &n);

	struct Node nodes[20];

	struct Node *root = NULL;

	for (int i = 0; i < n; ++i) {		//初始化一个节点。并插入AVL树中

		scanf("%d", &nodes[i].val);

		nodes[i].height = 0;			//孤立的节点高度为0

		nodes[i].left = NULL;

		nodes[i].right = NULL;

		root = insertAvlTree(&nodes[i], root);

	}

	printf("%d", root->val);

	return 0;

}

题目链接：http://www.patest.cn/contests/mooc-ds/04-%E6%A0%914