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
=====================================================
简单的平衡树创建，值得注意的地方是 在插入的时候 为了保证树的平衡而进行的旋转
---------------src--------------------
#include <cstdio> #include <stdlib.h> #define max(a,b) ((a>b)?(a):(b)) typedef struct AvlNode { int data ; struct AvlNode *left ; struct AvlNode *right ; int height ; }AvlNode ; int height ( AvlNode *t ) { return t == NULL ? -1 : t->height; } void LLRotate ( AvlNode *& t ) //左左 对应的情况是 旋转节点的左孩子 代替传入节点，即 传入节点的左子树上面 有新增节点 为了保持平衡 需要向右单旋转
{ AvlNode *tmp = t->left ; t->left = tmp->right ; tmp->right = t ; tmp->height = max(height(tmp->left) , height(tmp->right) )+1; t->height = max (height(t->left) , height(t->right )) +1 ; t = tmp ; } void RRRotate ( AvlNode *& t )//右右 对应的情况是 传入节点的右孩子 在旋转之后 代替传入节点， 即 传入节点的右子树上面有新增节点 需要 向左单旋转
{ AvlNode *tmp = t->right ; t->right = tmp->left ; tmp->left = t ; tmp->height = max ( height ( tmp->left) , height ( tmp->right ) ) +1 ; t->height = max ( height(t->left) , height(t->right ) )+1 ; t = tmp ; } void RLRotate ( AvlNode *& t )// 对应 传入节点的 右孩子的 左子树 有新增节点，先将 右孩子向右单向旋转，使右孩子的左右子树平衡，然后 向左单向旋转 传入节点 是传入节点的左右子树达到平衡
{ LLRotate( t->right) ; RRRotate( t ) ; } void LRRotate ( AvlNode *& t )//对应传入节点 的左孩子的 右子树上面 有新增节点， 先将 左孩子 向左 单向旋转，是的左孩子的左右子树平衡，
//然后 向右单方向旋转 传入节点 使得 传入节点 的左右子树达到平衡
{ RRRotate( t->left) ; LLRotate( t ) ; } //由于 生成AVL 树的时候 ， 需要动态生成， 所以 保证 传入的指针参数所指向的实体 在 函数中的变化是 被记录的，所以 需要使用引用符号 ‘&’ void insert ( const int &x , AvlNode *&t ) { if ( t == NULL ) { t = (AvlNode*)malloc(sizeof(AvlNode)) ; t->data = x ; t->height = 0 ; t->left = t->right = NULL ; } else if ( x < t->data ) { insert ( x , t->left ) ; if ( height( t->left ) - height( t->right ) == 2 ) if ( x < t->left->data ) LLRotate( t ) ; else LRRotate( t ) ; } else if ( t->data < x ) { insert ( x , t->right ) ; if ( height( t->right ) - height ( t->left) == 2 ) if ( x > t->right->data ) RRRotate( t ) ; else RLRotate( t ) ; } else ; t->height = max( height ( t->left ) , height(t->right)) +1 ; } int main ( void ) { AvlNode *root = NULL ; int N ; int i ; int num[22] ; scanf("%d", &N) ; for ( i = 0 ; i < N ; i++ ) { scanf("%d", &(num[i] )) ; } for ( i = 0 ; i < N ; i++ ) { insert( num[i] , root ) ; } printf("%d" , root->data) ; return 0 ; }