04-树5 Root of AVL Tree(25 分)

传送门

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;
}
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 你六周岁了,上小学了。 中午到家,你告诉我,期中考试数学考了一百分。你很开心。我夸奖了你,因为你平时就把做错的题目...
    小章鱼fancy阅读 339评论 0 1
  • 热油锅爆蒜末、姜末,加入紫菜洗水后装清水入锅煮开,加入打碎匀的鸡蛋,调入盐和鸡精,关火,盛入装有葱花的盆里
    渡把阅读 261评论 0 0
  • 尹天佑跑到宿舍区,然后“0.0,忘记问那栋了,不会又跑回去吧!”尹天佑发楞道 “你是尹天佑吧?我是你的室友,来我带...
    魔童兔兔TUT阅读 309评论 0 0