1066. 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 (<=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

 

解题思路：

考查AVL树的构建，可以参考：http://www.cppblog.com/cxiaojia/archive/2013/07/22/187776.html

参考代码：

 

#include<iostream>  
#include<cmath>  
using namespace std;  
  
struct TreeNode  
{  
    int value;  
    TreeNode *left;  
    TreeNode *right;  
    int height;  
    TreeNode(int v):value(v),left(NULL),right(NULL),height(0){}  
    TreeNode():left(NULL),right(NULL){}  
};  
  
int getHeight(TreeNode *t)  
{  
    if(t == NULL) return -1;  
    else return t->height;  
}  
  
int max(int a,int b) {return a>b? a:b;}  
  
//左左  
TreeNode *SingleRotateLeft(TreeNode *t2)  
{  
    TreeNode *t1;  
    t1 = t2->left;  
    t2->left = t1->right;  
    t1->right = t2;  
  
    t2->height = max(getHeight(t2->left),getHeight(t2->right)) + 1;  
    t1->height = max(getHeight(t1->left),getHeight(t1->right)) + 1;  
    return t1;  
}  
  
//右右  
 TreeNode *SingleRotateRight(TreeNode *t2)  
 {  
     TreeNode *t1;  
     t1 = t2->right;  
     t2->right = t1->left;  
     t1->left = t2;  
  
     t2->height = max(getHeight(t2->left),getHeight(t2->right)) + 1;  
     t1->height = max(getHeight(t1->left),getHeight(t1->right)) + 1;  
     return t1;  
 }  
  
 //左右  
 TreeNode * DoubleRotateLR(TreeNode *t3)  
 {  
     t3->left = SingleRotateRight(t3->left);  
     return SingleRotateLeft(t3);  
 }  
  
 //右左  
 TreeNode * DoubleRotateRL(TreeNode *t3)  
 {  
     t3->right = SingleRotateLeft(t3->right);  
     return SingleRotateRight(t3);  
 }  
   
 bool isBalanced(TreeNode *left,TreeNode *right)  
 {  
     return abs(getHeight(left) - getHeight(right)) < 2;  
 }  
  
 TreeNode* insert(int v, TreeNode *root)  
 {  
    if(root == NULL)  
    {  
        root = new TreeNode(v);  
        return root;  
    }  
    if(v > root->value) //节点插入在右子树中  
    {  
        root->right = insert(v,root->right);  
        if(!isBalanced(root->left,root->right)){  
            if(v > root->right->value)  
                root = SingleRotateRight(root);  
            else  
                root = DoubleRotateRL(root);  
        }  
    }else{  
        root->left = insert(v,root->left);  
        if(!isBalanced(root->left,root->right)){  
            if(v < root->left->value)  
                root = SingleRotateLeft(root);  
            else  
                root = DoubleRotateLR(root);  
        }  
    }  
    root->height = max(getHeight(root->left),getHeight(root->right)) + 1;  
    return root;  
 }  
  
 int main()  
 {  
     int n;  
     while(cin>>n)  
     {  
         int t;  
         TreeNode *root = NULL;  
         for(int i=0; i<n; i++)  
         {    
             cin>>t;  
             root = insert(t,root);            
         }  
         cout<<root->value<<endl;  
     }  
     return 0;  
 }  

 

 

补充：软件开发 , C++ ,