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 $N$ ($\le 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二叉树，涉及到LL，RR，LR和RL的rotate，其中的关键在于计算节点的高度，这不能错，我就在getHeight出错了，找了好久的bug，哭晕在厕所。直接代码，简洁明了： #include <iostream> #include <stdlib.h> using namespace std; typedef struct node *avltree; struct node{ int data; avltree left; avltree right; }; int getHeight(avltree &root){ if(root) return max(getHeight(root->left),getHeight(root->right))+1; else return 0; } avltree rotateLL(avltree &root){ avltree tree = root->left; root->left = tree->right; tree->right = root; return tree; } avltree rotateRR(avltree &root){ avltree tree = root->right; root->right = tree->left; tree->left = root; return tree; } avltree rotateLR(avltree &root){ root->left = rotateRR(root->left); return rotateLL(root); } avltree rotateRL(avltree &root){ root->right = rotateLL(root->right); return rotateRR(root); } avltree insert(avltree &root, int data){ if(root == NULL){ avltree tree = new node; tree->data = data; tree->left = NULL; tree->right = NULL; root = tree; return root; } if(data < root->data){ root->left = insert(root->left, data); if(getHeight(root->left) - getHeight(root->right) == 2){ if(data < root->left->data){ root = rotateLL(root); }else{ root = rotateLR(root); } } }else{ root->right = insert(root->right, data); if(getHeight(root->left) - getHeight(root->right) == -2){ if(data > root->right->data){ root = rotateRR(root); }else{ root = rotateRL(root); } } } return root; } void print(avltree root){ cout<<root->data<<' '; if(root->left) print(root->left); if(root->right) print(root->right); } int main(){ int N, data; cin>>N; avltree tree = NULL; for(int i = 0; i < N; i++){ cin>>data; insert(tree, data); } cout<<tree->data; return 0; }