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.
Each input file contains one test case. For each case, the first line contains a positive integer N (≤) 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.
For each test case, print the root of the resulting AVL tree in one line.
5
88 70 61 96 120
70
7
88 70 61 96 120 90 65
88
题意：
给出一组数字，要求按照给出的顺序插入到一棵平衡二叉树中，最后求这棵AVL Tree的根结点中的数值。
思路：
首先应该清楚，在构建的过程中四种旋转的的情况。应该先利用递归将结点插入，然后再判断是否需要旋转。
Code：
1 #include <bits/stdc++.h> 2 3 using namespace std; 4 5 typedef struct Node* node; 6 7 struct Node { 8 int val; 9 node left; 10 node right; 11 Node(int v) { 12 val = v; 13 left = NULL; 14 right = NULL; 15 } 16 }; 17 18 node rightRotate(node root) { 19 node temp = root->left; 20 root->left = temp->right; 21 temp->right = root; 22 return temp; 23 } 24 25 node leftRotate(node root) { 26 node temp = root->right; 27 root->right = temp->left; 28 temp->left = root; 29 return temp; 30 } 31 32 node rightLeft(node root) { 33 root->right = rightRotate(root->right); 34 return leftRotate(root); 35 } 36 37 node leftRight(node root) { 38 root->left = leftRotate(root->left); 39 return rightRotate(root); 40 } 41 42 int findHeight(node root) { 43 if (root == NULL) return 0; 44 int l = findHeight(root->left); 45 int r = findHeight(root->right); 46 return max(l, r) + 1; 47 } 48 49 void insertNode(node& root, int val) { 50 if (root == NULL) { 51 root = new Node(val); 52 } else if (root->val > val) { 53 insertNode(root->left, val); 54 int l = findHeight(root->left); 55 int r = findHeight(root->right); 56 if (abs(r - l) > 1) { 57 if (root->left->val > val) { 58 root = rightRotate(root); 59 } else { 60 root = leftRight(root); 61 } 62 } 63 } else { 64 insertNode(root->right, val); 65 int l = findHeight(root->left); 66 int r = findHeight(root->right); 67 if (abs(r - l) > 1) { 68 if (root->right->val < val) { 69 root = leftRotate(root); 70 } else { 71 root = rightLeft(root); 72 } 73 } 74 } 75 } 76 77 void preTraveser(node root) { 78 if (root == NULL) return; 79 cout << root->val << " "; 80 preTraveser(root->left); 81 preTraveser(root->right); 82 } 83 84 int main() { 85 int n, t; 86 cin >> n; 87 node root = NULL; 88 for (int i = 0; i < n; ++i) { 89 cin >> t; 90 insertNode(root, t); 91 } 92 cout << root->val << endl; 93 return 0; 94 }
原文：https://www.cnblogs.com/ruruozhenhao/p/12828354.html