typedef struct avltreenode *avltree;
typedef struct avltreenode{
int data;
avltree left;
avltree right;
int height;
};
int getheight(avltree a)
{
if(a==NULL) return -1;
return a->height;
}
//a必須有一個左子結點b
//a與b做左單旋,更新a與b高度,返回新的根結點b
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),a->height)+1;
return b;
}
//右單旋
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->right),a->height)+1;
return b;
}
//左右雙旋
//a必須有一個左子結點b,且b必須有一個右子結點c
//a,b,c,做兩次單旋,返回新的根結點c
//先對b和c做右單旋,在對a和c做左單旋
avltree doubleleftrightrotation(avltree a)
{
a->left=singlerightrotation(a->left);
return singleleftrotation(a);
}
//右左雙旋
avltree doublerightleftrotation(avltree a)
{
a->right=singleleftrotation(a->right);
return singlerightrotation(a);
}
avltree avl_insertion(int x,avltree t)
{
/*將X插入avl樹T中,並返回調整後的avl樹*/
if(!t)/*插入空樹,則新建包含一個結點的樹*/
{
t=(avltree)malloc(sizeof(struct avltreenode));
t->data=x;
t->height=0;
t->left=t->right=NULL;
}/*插入空樹結束*/
else if(xdata)
{
t->left=avl_insertion(x,t->left);
if(getheight(t->left)-getheight(t->right)==2)
{
/*需要左旋*/
if(xleft->data)
t=singleleftrotation(t);//左單旋 singleleftrotation
else
t=doubleleftrightrotation(t);//左右雙旋
}
}
else if(x>t->data)
{
t->right=avl_insertion(x,t->right);
if(getheight(t->left)-getheight(t->right)==-2)
{
/*需要右旋*/
if(x>t->right->data)
t=singlerightrotation(t);//右單旋
else
t=doublerightleftrotation(t);//右左雙旋
}
}
//x=data,無須插入
t->height=max(getheight(t->left),getheight(t->right))+1;
return t;
}