04-树4. 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 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