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
在插入结点的过程中维护二叉搜索树的平衡，左子数的height比右子树大2的前提下，如果插入结点在左子树的左子树，直接对根进行左左旋，如果插入结点在左子树的右子树，就对左子树进行右右旋，然后对根进行左左旋。
反过来右子树的height比左子树大2，也一样，如果插入结点在右子树的右子树，直接对根进行右右旋，如果插入结点在右子树的左子树，就对右子树进行左左旋，然后对根进行右右旋。
代码：
#include <stdio.h> #include <stdlib.h> typedef struct tree///二叉搜索树结构体 { int data; struct tree *left,*right; }tree; tree *creatnode(int data)///创建新结点 { tree *p = (tree *)malloc(sizeof(tree)); p -> left = p -> right = NULL; p -> data = data; return p; } int max(int a,int b) { return a > b ? a : b; } int getheight(tree *t)///返回结点高度 即以当前结点为根的子树的最大层数 { if(t == NULL)return 0; return max(getheight(t -> left),getheight(t -> right)) + 1; } tree *ll_r(tree *t)///左左旋 { tree *l = t -> left; t -> left = l -> right; l -> right = t; return l; } tree *rr_r(tree *t)///右右旋 { tree *r = t -> right; t -> right = r -> left; r -> left = t; return r; } tree *lr_r(tree *t)///左右旋 { t -> left = rr_r(t -> left); return ll_r(t); } tree *rl_r(tree *t)///右左旋 { t -> right = ll_r(t -> right); return rr_r(t); } tree *insertavltree(int data,tree *t)///插入并平衡 { if(t == NULL)return creatnode(data); else if(data < t -> data) { t -> left = insertavltree(data,t -> left); } else { t -> right = insertavltree(data,t -> right); } if(getheight(t -> left) - getheight(t -> right) == 2) { if(data < t -> left -> data)t = ll_r(t); else t = lr_r(t); } else if(getheight(t -> left) - getheight(t -> right) == -2) { if(data < t -> right -> data)t = rl_r(t); else t = rr_r(t); } return t; } int main() { int n,d; scanf("%d", &n); tree *root = NULL; for(int i = 0; i < n; i ++) { scanf("%d",&d); root = insertavltree(d,root); } printf("%d", root->data); }