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 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树的根
主要就是针对AVL树的失衡的几种情况，分别进行重新平衡
LL型：由于在A左子树根节点的左子树上插入结点，使A的平衡由1增至2.此时可以通过右旋来实现。所谓右旋就是将根节点作为其左子树的右子树。
若原左子树上有右结点，此时作为根节点的左子树。
RR型：由于在A右子树根节点的右子树上插入节点，使A的平衡由-1变成-2.此时可以通过左旋实现。所谓左旋就是将根节点作为其右子树的左子树。
若原右子树有左孩子，此时作为根节点的右孩子。
LR型：由于在A左子树根节点的右子树上插入节点，使A的平衡由1增至2.此时可现对root->left进行一次左旋，再对root进行一次右旋
RL型：由于在A右子树根节点的左子树上插入节点，使A的平衡由-1变成-2.此时可现对root->right进行一次右旋，在对root进行一次左旋。
具体代码如下：
#include<iostream> #include<cstdio> using namespace std; struct Node { int val; Node *left,*right; }; Node* rotateright(Node *root) //右旋 LL型 { Node *t=root->left; root->left=t->right; t->right=root; return t; } Node* rotateleft(Node *root) //左旋 RR型 { Node *t=root->right; root->right=t->left; t->left=root; return t; } Node* rotateleftright(Node *root) //LR型 { root->left=rotateleft(root->left); return rotateright(root); } Node* rotaterightleft(Node *root) { root->right=rotateright(root->right); return rotateleft(root); } int getHeight(Node *root) { if(root==NULL) return 0; else return max(getHeight(root->left),getHeight(root->right))+1; } Node* build(Node *root,int val) { if(root==NULL) { root=new Node(); root->val=val; root->left=root->right=NULL; } else if(val<root->val)//插入到左子树中 { root->left=build(root->left,val); if(getHeight(root->left)-getHeight(root->right)==2) { root=val<root->left->val ?rotateright(root):rotateleftright(root); //如果是LL型，做右旋，否则先左旋后右旋 } } else { root->right=build(root->right,val); if(getHeight(root->left)-getHeight(root->right)==-2) root=val>root->right->val ? rotateleft(root):rotaterightleft(root); } return root; } int main() { int n; scanf("%d",&n); Node *root=NULL; for(int i=1;i<=n;i++) { int val; scanf("%d",&val); root=build(root,val); } printf("%d ",root->val); }