首页 技术 正文
技术 2022年11月24日
0 收藏 599 点赞 5,007 浏览 3433 个字

  以下用大O表示节点,ABC表示三个集合。

  仅分析左子树的情况,因为对称,右子树的情况一样。

  插入节点前

      O

     /     \

    O        A

     /    \

B       C

  插入节点后:

      O

     /     \

    O        A

     /    \

B       C

/

O

此时造成了最高节点的不平衡,说明了B+2 – A = 2;另外可以知道B = C,考虑B<C,那么在插入节点前最高点就已经不平衡了,考虑B > C,那么最高的左子树就已经不平衡了,而不应该考虑最高点。所以此时可以知道A = B = C。

  左子树单旋转之后:

      O

     /     \

    B        O

     /          /    \

O         C       A

  对于最高点来说,左子树深度为B+1,右子树深度为A+1,即B + 1。

  对比插入后的树,可以知道只有原最高节点的深度发生变化,所以只需更新该节点的深度。

另外一种情况:

插入后:

 

      O

     /     \

    O        A

     /    \

B       C

/

O

此时如果单旋转,结果为:

      O

     /     \

    B        O

                 /    \

C       A

/

O

明显这个情况并没有得到解决。

所以首先要单右旋转最高节点的左子树,结果为:

      O

     /     \

    C        A

     /    \

O       O

/

B

此时可以知道C集合的深度发生了变化,需要更新C的深度,而之前更新的是最高点的深度,所以在旋转时需要更新原最高点和现最高点的深度。

第二次左旋转原最高点,结果为

      C

     /     \

    O        O

     /         /    \

B        O       A

这里面的正确有一些缺陷,应该把ABC集合多展开几层,否则在双旋转时的证明有些怪异,反正就是这个思路,因为画图实在是太麻烦了。

最后是代码:

  

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
typedef struct _node
{
int element;
int high;
struct _node *lefttree;
struct _node *righttree;
}node;int gethigh(node *t)
{
if(t == )
return -;
return t->high;
}node *singlerotatewithleft(node *t)
{
node *tmp = t->lefttree;
t->lefttree = tmp->righttree;
tmp->righttree = t; tmp->high = ((gethigh(tmp->lefttree) > gethigh(tmp->righttree))?gethigh(tmp->lefttree):gethigh(tmp->righttree)) + ;
t->high = ((gethigh(t->lefttree) > gethigh(t->righttree))?gethigh(t->lefttree):gethigh(t->righttree)) + ;
return tmp;
}node *singlerotatewithright(node *t)
{
node *tmp = t->righttree;
t->righttree = tmp->lefttree;
tmp->lefttree = t; tmp->high = ((gethigh(tmp->lefttree) > gethigh(tmp->righttree))?gethigh(tmp->lefttree):gethigh(tmp->righttree)) + ;
t->high = ((gethigh(t->lefttree) > gethigh(t->righttree))?gethigh(t->lefttree):gethigh(t->righttree)) + ;
return tmp;
}node *doubleroratewithleft(node *t)
{
t->lefttree = singlerotatewithright(t->lefttree);
return singlerotatewithleft(t);
}node *doubleroratewithright(node *t)
{
t->righttree = singlerotatewithleft(t->righttree);
return singlerotatewithright(t);
}node *insert(node *t,int element)
{
if (t == )
{
t = (node *)malloc(sizeof(node));
t->element = element;
t->lefttree = t->righttree = ;
}
else if(t->element > element){
t->lefttree = insert(t->lefttree,element);
if(gethigh(t->lefttree) - gethigh(t->righttree) == )
if(element < t->lefttree->element)
t= singlerotatewithleft(t);
else
t= doubleroratewithleft(t);
}
else if(t->element < element){
t->righttree = insert(t->righttree,element);
if(gethigh(t->righttree) - gethigh(t->lefttree) == )
if(element > t->righttree->element)
t= singlerotatewithright(t);
else
t= doubleroratewithright(t); }
t->high = ((gethigh(t->lefttree) > gethigh(t->righttree))?gethigh(t->lefttree):gethigh(t->righttree)) + ;
return t;
}node *find(node *t,int element)
{
if(t == )
return ;
else if(t->element > element)
return find(t->lefttree,element);
else if(t->element < element)
return find(t->righttree,element);
else
return t;
}node* findmin(node *t)
{
if(t == )
return ;
if(t->lefttree == )
return t;
else
return findmin(t->lefttree);
}node *delele(node *t,int element)
{
if(t == )
return ;
else if(t->element > element)
t->lefttree = delele(t->lefttree,element);
else if(t->element < element)
t->righttree = delele(t->righttree,element);
else
{
if(t->lefttree && t->righttree)
{
node *tmp;
tmp = findmin(t->righttree);
t->element = tmp->element;
t->righttree = delele(t->righttree,tmp->element);
}
else
{
node *tmp;
tmp = t->lefttree?t->lefttree:t->righttree;
free(t);
t = tmp;
}
}
return t;
}void printtree(node *t)
{
if(t == )
return;
printtree(t->lefttree);
printf("%d\t",t->element);
printf("high = %d\n",t->high);
printtree(t->righttree);
}int main()
{
int a[] = {,,,,,,,,};
node *t;
int i = ;
t = insert(,);
for(;i<;i++){
t = insert(t,a[i]);
//printtree(t);
//sleep(1);
}
//t = delele(t,6);
printtree(t);
printf("\n");
//while(1);
return ;
}

 

 

 

微信扫一扫

支付宝扫一扫

本文网址:https://www.zhankr.net/141922.html

相关推荐
python开发_常用的python模块及安装方法
adodb:我们领导推荐的数据库连接组件bsddb3:BerkeleyDB的连接组件Cheetah-1.0:我比较喜欢这个版本的cheeta…
日期:2022-11-24 点赞:875 阅读:5,067
Educational Codeforces Round 11 C. Hard Process 二分
C. Hard Process题目连接:http://www.codeforces.com/contest/660/problem/CDes…
日期:2022-11-24 点赞:806 阅读:3,504
下载Ubuntn 17.04 内核源代码
zengkefu@server1:/usr/src$ uname -aLinux server1 4.10.0-19-generic #21…
日期:2022-11-24 点赞:565 阅读:4,312
可用Active Desktop Calendar V7.86 注册码序列号
可用Active Desktop Calendar V7.86 注册码序列号Name: www.greendown.cn Code: &nb…
日期:2022-11-24 点赞:730 阅读:4,307
Android调用系统相机、自定义相机、处理大图片
Android调用系统相机和自定义相机实例本博文主要是介绍了android上使用相机进行拍照并显示的两种方式,并且由于涉及到要把拍到的照片显…
日期:2022-11-24 点赞:512 阅读:4,904
Struts的使用
一、Struts2的获取  Struts的官方网站为:http://struts.apache.org/  下载完Struts2的jar包,…
日期:2022-11-24 点赞:671 阅读:3,097
发表评论
暂无评论

还没有评论呢,快来抢沙发~

助力内容变现

将您的收入提升到一个新的水平

点击联系客服

在线时间:8:00-16:00

客服电话

400-888-8888

客服邮箱

ceotheme@ceo.com

扫描二维码

关注微信公众号

扫描二维码

手机访问本站