传送门

04-树5 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 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

提交代码

#include <iostream>
#include <cstdlib>

using namespace std;

typedef struct _node {int v;struct _node * left;struct _node * right;int height;} *AVLtree;
int max(int a, int b);
AVLtree insert (AVLtree t, int x);
AVLtree singleLeftRotation(AVLtree a);
AVLtree doubleLeftRightRotation(AVLtree a);
AVLtree doubleRightLeftRotation(AVLtree a);
AVLtree singleRightRotation(AVLtree a);
int getHeight(AVLtree t);

int main()
{
    int n, v;
    cin >> n;
    AVLtree root = NULL;
    for ( int i=0; i<n; i++ ) {
        cin >> v;
        root = insert(root, v);
    }
    cout << root->v;
    return 0;
}

int max(int a, int b)
{
    return a>b ? a:b;
}

AVLtree insert (AVLtree t, int x)
{
    if ( !t ) {//empty tree
        t = (AVLtree)malloc(sizeof(struct _node));
        t->v = x;
        t->left = t->right = NULL;
        t->height = 0;
    } else if ( x<t->v ) {
        t->left = insert(t->left, x);
        if ( getHeight(t->left)-getHeight(t->right)==2 ) {
            if ( x<t->left->v ) t = singleLeftRotation(t);
            else t = doubleLeftRightRotation(t);
        }
    } else if ( x>t->v ) {
        t->right = insert(t->right, x);
        if ( getHeight(t->left)-getHeight(t->right)==-2 ) {
            if ( x>t->right->v ) t = singleRightRotation(t);
            else t = doubleRightLeftRotation(t);
        }
    }
    //renew the height
    t->height = max( getHeight(t->left), getHeight(t->right) ) + 1;
    return t;
}

AVLtree singleLeftRotation(AVLtree a)
{
    AVLtree b = a->left;
    a->left = b->right;
    b->right = a;
    a->height = max( getHeight(a->left), getHeight(a->right) ) + 1;
    b->height = max( getHeight(b->left), getHeight(b->right) ) + 1;
    return b;
}

AVLtree doubleLeftRightRotation(AVLtree a)
{
    AVLtree b = a->left, c = b->right, cl = c->left, cr = c->right;
    a->left = cr;
    b->right = cl;
    c->left = b;
    c->right= a;
    a->height = max( getHeight(a->left), getHeight(a->right) ) + 1;
    b->height = max( getHeight(b->left), getHeight(b->right) ) + 1;
    c->height = max( getHeight(c->left), getHeight(c->right) ) + 1;
    return c;
}

AVLtree doubleRightLeftRotation(AVLtree a)
{
    AVLtree b = a->right, c = b->left, cl = c->left, cr = c->right;
    a->right = cl;
    b->left = cr;
    c->right = b;
    c->left = a;
    a->height = max( getHeight(a->left), getHeight(a->right) ) + 1;
    b->height = max( getHeight(b->left), getHeight(b->right) ) + 1;
    c->height = max( getHeight(c->left), getHeight(c->right) ) + 1;
    return c;
}

AVLtree singleRightRotation(AVLtree a)
{
    AVLtree b = a->right;
    a->right = b->left;
    b->left = a;
    a->height = max( getHeight(a->left), getHeight(a->right) ) + 1;
    b->height = max( getHeight(b->left), getHeight(b->right) ) + 1;
    return b;
}

int getHeight(AVLtree t)
{
    if ( !t ) return 0;
    else return t->height;
}