PAT 解题报告 1066. Root of AVL Tree (25)

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.

Root of AVL Tree算法分析：

```#include <cstdio>
#include <cmath>
#include <algorithm>

struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
int height;
TreeNode(int v): val(v), left(NULL), right(NULL), height(0) {}
TreeNode(): val(0), left(NULL), right(NULL), height(0) {}
};

int getHeight(TreeNode *node) {
if(NULL == node) return -1;
return node->height;
}

TreeNode *singleRoateLeft(TreeNode *k2) {
TreeNode *k1 = k2->left;
k2->left = k2->right;
k1->right = k2;

k2->height = std::max(getHeight(k2->left), getHeight(k2->right)) + 1;
k1->height = std::max(getHeight(k1->left), getHeight(k1->right)) + 1;
return k1;
}

TreeNode *singleRoateRight(TreeNode *k1) {
TreeNode *k2 = k1->right;
k1->right= k2->left;
k2->left = k1;

k1->height = std::max(getHeight(k1->left), getHeight(k1->right)) + 1;
k2->height = std::max(getHeight(k2->left), getHeight(k2->right)) + 1;
return k2;
}

TreeNode *doubleRoateLeft(TreeNode *k3) {
k3->left = singleRoateRight(k3->left);
return singleRoateLeft(k3);
}

TreeNode *doubleRoateRight(TreeNode *k1) {
k1->right = singleRoateLeft(k1->right);
return singleRoateRight(k1);
}

bool isBalanced(TreeNode *left, TreeNode *right) {
return std::abs(getHeight(left) - getHeight(right)) < 2;
}

TreeNode *insert(int v, TreeNode *root) {
if(NULL == root) {
root = new TreeNode(v);
return root;
}
if(v < root->val) {
root->left = insert(v, root->left);
if(!isBalanced(root->left, root->right)) {
// test single or double
if(v < root->left->val)
root = singleRoateLeft(root);
else
root = doubleRoateLeft(root);
}
}
else {
root->right = insert(v, root->right);
if(!isBalanced(root->left, root->right)) {
if(v > root->right->val)
root = singleRoateRight(root);
else
root = doubleRoateRight(root);
}
}
root->height = std::max(getHeight(root->left), getHeight(root->right)) + 1;
return root;
}

int main() {
int n, v;
scanf("%d", &n);
TreeNode *root = NULL;

while(n--)  {
scanf("%d", &v);
root = insert(v, root);
}
printf("%d\n", root->val);
// destroy(root);
return 0;
}
```

Root of AVL Tree注意点：

Written on October 11, 2013