分享
 
 
 

07 AVL 树

王朝other·作者佚名  2006-09-05
窄屏简体版  字體: |||超大  

用二叉树的遍历来消除递归。

前面说了模拟系统函数调用的方法消除递归,现在再说说利用遍历消除递归的方法。

先看两个递归函数。

void MergeSort(int [] array,int left,int right){

if(right<=left) return;

int mid=(left+right)/2;

MergeSort(array,left,mid);

MergeSort(array,mid+1,right);

Merge(array,left,mid,mid+1,right);

}

void QuickSort(int[] array,int left,int right){

if(right<=left) return;

选择枢轴,把它放到正确的位置,并把比它小的放到它的左边,比它大的放到右边;

QuickSort(左边的数组);

QuickSort(右边的数组);

}

这两个递归函数都调用自身两次。这和二叉树的遍历有什么关系呢?

两次递归把整个代码分成三部分。比如:归并排序。

part1 int mid=(left+right)/2;

递归调用1 MergeSort(array,left,mid);

part2 空

递归调用2 MergeSort(array,mid+1,right);

part3 Merge(array,left,mid,mid+1,right);

函数的执行过程是:进入part1(当前节点),进入递归调用1(左孩子),part2(当前节点),进入递归调用2(右孩子),进入part3(当前节点)。

哦,有点遍历的意思了,但遍历是每个节点访问一次,你都访问3次了!part2是空,就算少一次,还有part1和part3呀!先我们不看part1,那么就是一个后序的遍历。

QuickSort比较简单part2和part3本来就是空的,所以它是个先序的遍历。

现在我们来看看为什么MergeSort对应一个后续遍历?即为什么part1可以不理睬?

MergeSort的目的就是把输入――array[left….right]中的数从小到大排序并放到array[left…right]中。我们要处理的数据是array数组,而part1的int mid=(left+right)/2;和array是没有关系的。

AVL树

一般书讲AVL树,一上来就是插入节点有两种情况(对称又两种),怎么旋转使它平衡;删除又有四种情况,怎么旋转使它平衡。却没有说明为什么插入有两种不平衡的情况?为什么没有3种4种?

先看插入节点。

首先当然是用BST的插入算法找到插入的位置。另外从根到插入节点路径上所有的节点(即插入节点的祖先们)都可能被用到,所以在查找的过程中要把他们都保存下来。

从被插入节点一直向上走,因为原来的树是平衡的(注意,这里说的平衡是只满足AVL性质,即左右子树的高度之差的绝对值不超过1,而不是说树是最优平衡的),所以它遇到的节点的平衡因子只能是0,+1或-1。如果遇到的是0,则插入一个节点后它的平衡因子就会变成-1或+1,但树的高度加1,所以还要继续向上走。如果遇到的是+1或-1,那么可能变成0,+2或-2。如果变成0了,那么树还是平衡的,并且树的高度不再增加,所以不用再向走上了。如果变成2,则出现第一个不平衡的节点。

既然不平衡了,那么我们就想办法使它平衡。注意,除了使它平衡外,最好它的高度还不变,这样我们就不用向上走了。

总结一下:我们从被插入节点一直向上走,遇到0就把它变成+1或-1(左上是+1,右上是-1),并继续向上走;遇到+1或-1则分两种情况:一是变成0,一是变成+2或-2。但不管哪种情况都不用再向上走了(变成0树高肯定不变,变成+2或-2我们假设在使它平衡的同时还不增加树高,后面我们会发现只是可行的)。

假设向上第一个不平衡的节点(即平衡因子由+1或-1变成+2或-2的节点)为P,由于对称性我们假设它由+1变成+2。(万一没有节点从+1或-1变成+2或-2呢?那么有两种情况:有节点从+1或-1变成0;一直到了根了。无论哪种情况树都已经平衡了。)

则原来的树一定是下面的形状。图上用括号括起来的是节点的平衡因子。

P(+1)

/ (h) Q(0)

/ (h) (h)

为什么Q的平衡因子是0?因为根据前面的分析,从被插入节点一直向上P是第一个平衡因子是+1或-1,其余的都是0。

因此插入后又有两种情况:Q的左子树变成高为h+1;Q的右子树变成高为h+1。

我们来分别讨论。

先讨论右子树增高的情况(先看简单的)。插入后的树变成下图的形状。

P(+2)

/ (h) Q(+1)

/ (h) (h+1)

树不平衡了!哪不平衡?P的右子树Q(的右子树)太高了!所以要把它弄上去。当然不能随便弄上去,要保持BST树的性质。这就是所谓的RR旋转。旋转的结果是:

Q(0)

/ P(0) (h+1)

/ (h) (h)

结果很好,比原来还平衡,而且树的高度不变(旋转前后都是h+2)。

再来看左子树增高的情况,如下图。

P(+2)

/ (h) Q(-1)

/ (h+1) (h)

如果我们还是依葫芦画瓢把Q弄上去的话,则会变成下面的树:

Q(-2)

/ P(+1) (h)

/ (h) (h+1)

还是不平衡!因为这次不平衡的元凶不是Q的右子树而是左子树,因此我们要把Q的左子树的根弄上去。

把Q的左子树也画出来的树如下:

P(+2)

/ (h) Q(-1)

/ R(+1) (h)

/ (h-1) (h)

注意R为-1的情况与+1是一样的;R不能为0,为什么?(因为原来R是0,在向上走的过程中被变成了+1或-1)。

我们先把R弄上去:

P(+2)

/ (h) R(+2)

/ (h-1) Q(0)

/ (h) (h)

R又太高了,再把它也弄上去:

R(0)

/ P(-1) Q(0)

/ \ / (h) (h-1) (h) (h)

这下总算平衡了,而且经过两次旋转后,树的高度不变,还是h+2。

这就是所谓的RL旋转。

除此之外还有对称的LL和LR旋转。

接着来看AVL树删除节点的方法。

在这之前先来复习一下BST删除节点的算法。

分三种情况:删除叶子;被删除的节点有一个孩子;被删除的节点有两个孩子。

删除叶子最简单,直接把它的父亲节点的指针置成空就可以了。如下图:

15 15

/ \ 删除16 / 4 20 --------> 4 20

/ / /

1 16 1

删除只有一个孩子的节点也不难,把它的父亲指向它的孩子就可以了。

15 15

/ \ 删除20 / 4 20 --------> 4 16

/ / /

1 16 1

删除有两个孩子的节点有点麻烦。有两种方法――归并删除法和拷贝删除法。

归并删除的思路是:先安排被删除节点的左孩子,这和只有一个孩子的节点的删除是一样的;然后把被删除节点的右孩子插入到合适的位置(也就是被删除节点左子树的最右节点)。

15 10

/ \ 删除15 / 10 30 ---------> 5 11

/ \ / \ 5 11 20 40 12

\ 12 30

/ 20 40

上面的例子说明删除一个节点可能使得树的高度反而变高了。

拷贝删除的思路是:在被删除节点的左子树(或右子树)找到最大也即最右的节点(或最小的节点),左子树最右的节点最多只有一个孩子。把删除有两个孩子的节点转变成删除最多一个孩子的节点。然后把这个节点拷贝到真正被删除的节点里。

15 12

/ \ 删除15 / 10 30 ---------> 10 30

/ \ / \ / \ / 5 11 20 40 5 11 20 40

\

12

它的好处是树的高度不会增加。而且,真正被删除的节点为根的子树的高度是一定减少的。因为如果删除的是叶子,那么原来高度是1,现在变成0了;如果删除的是只有一个孩子的节点,那么它的子树替代了被删除的节点,也使树的高度少1。

在AVL树的删除中我们会用第二种方法,因为我们不希望在删除节点和树反而变高了。

我们还使按照与插入类似的分析方法。

找到第一个真正被删除的节点(叶子或一个孩子的节点),删除这个节点后这个节点的子树还是平衡的(叶子的子树是空树,一个孩子的节点它的孩子原来就是平衡的)。但删除节点后,以它为根的子树高度减一,这可能导致它的父亲不平衡。

因此我们沿着这个被删除的节点一直向上走。遇到的节点不外乎0,+1和-1三种。

如果遇到了0,则把它变成+1或-1(向右向上是+1向左向上是-1),树依然平衡,由于这时树的高度不会减少,所以不用再向上走了。

如果遇到了+1或-1,又有两种情况:变成0;变成+2或-2。

如果变成0的话树仍然是平衡的,但树的高度少一,所以还要往上走。

变成+2或-2的话树就不平衡了,需要我们通过旋转使之平衡。但平衡的同时能不能保证树的高度不减少呢(这样就不用向上走了)?通过分析我们将会发现有时树的高度会减少的。

由于对称性,我们假设某个节点P由+1变成了+2,原因是左子树变矮了。那么P的右孩子Q的平衡因子有3种情况(0,+1和-1)。

1.Q的平衡因子为1的如下图:

P(+1) P(+2) Q(0)

/ \ / \ / (h) Q(+1) (h-1) Q(+1) P(0) (h)

/ \ / \ / (h-1) (h) (h-1) (h) (h-1) (h-1)

原来的情况 左子树变矮后 把Q转上去后

通过旋转,树变平衡了,但新树的高度减少了,因此还有继续往上走。

2.Q的平衡因子为0的情况如下图:

P(+1) P(+2) Q(-1)

/ \ / \ / (h) Q(0) (h-1) Q(0) P(+1) (h)

/ \ / \ / (h) (h) (h) (h) (h-1) (h)

原来的情况 左子树变矮后 把Q转上去后

通过旋转,树平衡了,而且新树的高度不变,不用再向上走了。

3.Q的平衡因子为-1的情况。

如果我们还是把Q转上去的话,依然是不平衡的,如下图:

P(+1) P(+2) Q(-2)

/ \ / \ / (h) Q(-1) (h-1) Q(-1) P(+1) (h-1)

/ \ / \ / (h) (h-1) (h) (h-1) (h-1) (h)

原来的情况 左子树变矮后 把Q转上去后

原因和插入的RL旋转有些类似,因为Q的左子树太高了,所以我们先要把Q的左子树R转上来(Q下去),然后R再转上去(P下去)。但R的平衡因子可能有三种情况,这会不会影响其它的节点呢?我们分三种情况讨论。

3.1 R的平衡因子是-1

如下图:

P(+1) P(+2) P(+2) R(0)

/ \ / \ / \ / \

(h) Q(-1) (h-1) Q(-1) (h-1) R(+1) P(0) Q(+1)

/ \ / \ / \ / \ / R(-1) (h-1) R(-1) (h-1) (h-1) Q(+1) (h-1) (h-1) (h-2) (h-1)

/ \ / \ / (h-1) (h-2) (h-1) (h-2) (h-2) (h-1)

原来的情况 左子树变矮后 把R转到Q上面后 把R转到P上面后

通过两次旋转,树变得平衡了,但树的高度减少。

3.2 R的平衡因子是+1。

P(+1) P(+2) P(+2) R(0)

/ \ / \ / \ / \

(h) Q(-1) (h-1) Q(-1) (h-1) R(+2) P(-1) Q(0)

/ \ / \ / \ / \ / R(+1) (h-1) R(+1) (h-1) (h-2) Q(0) (h-1) (h-2) (h-1) (h-1)

/ \ / \ / (h-2) (h-1) (h-2) (h-1) (h-1) (h-1)

原来的情况 左子树变矮后 把R转到Q上面后 把R转到P上面后

通过两次旋转,树变得平衡了,但树的高度减少。

3.3 R的平衡因子是0

P(+1) P(+2) P(+2) R(0)

/ \ / \ / \ / \

(h) Q(-1) (h-1) Q(-1) (h-1) R(+1) P(0) Q(0)

/ \ / \ / \ / \ / R(0) (h-1) R(0) (h-1) (h-1) Q(0) (h-1) (h-1) (h-1) (h-1)

/ \ / \ / (h-1) (h-1) (h-1) (h-1) (h-1) (h-1)

原来的情况 左子树变矮后 把R转到Q上面后 把R转到P上面后

通过两次旋转,树变得平衡了,但树的高度减少。

从上面的图中可以看出R的平衡因子是什么没有关系,只要把R两次转上去就可以了。

总结一下删除的过程:找到真正被删除的节点,然后从它一直向上走。

如果遇到了0,则把它变成+1或-1(向右向上是+1向左向上是-1),且不用再向上走了。

如果遇到了+1或-1并且把它变成了0(向左遇到+1,向右遇到-1),继续向上走。

如果遇到了+1或-1并且把它(设为P)变成了+2或-2(向右遇到+1,向左遇到-1),则分三种情况(我们只讨论了+1,-1类似)。a)P的孩子Q是+1,把Q转上去,继续往上走;b)P的孩子Q是0,把Q转上去,不用上走了;c)P的孩子Q是-1,把Q的孩子R两次转上去,继续往上走。

 
 
 
免责声明:本文为网络用户发布,其观点仅代表作者个人观点,与本站无关,本站仅提供信息存储服务。文中陈述内容未经本站证实,其真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
2023年上半年GDP全球前十五强
 百态   2023-10-24
美众议院议长启动对拜登的弹劾调查
 百态   2023-09-13
上海、济南、武汉等多地出现不明坠落物
 探索   2023-09-06
印度或要将国名改为“巴拉特”
 百态   2023-09-06
男子为女友送行,买票不登机被捕
 百态   2023-08-20
手机地震预警功能怎么开?
 干货   2023-08-06
女子4年卖2套房花700多万做美容:不但没变美脸,面部还出现变形
 百态   2023-08-04
住户一楼被水淹 还冲来8头猪
 百态   2023-07-31
女子体内爬出大量瓜子状活虫
 百态   2023-07-25
地球连续35年收到神秘规律性信号,网友:不要回答!
 探索   2023-07-21
全球镓价格本周大涨27%
 探索   2023-07-09
钱都流向了那些不缺钱的人,苦都留给了能吃苦的人
 探索   2023-07-02
倩女手游刀客魅者强控制(强混乱强眩晕强睡眠)和对应控制抗性的关系
 百态   2020-08-20
美国5月9日最新疫情:美国确诊人数突破131万
 百态   2020-05-09
荷兰政府宣布将集体辞职
 干货   2020-04-30
倩女幽魂手游师徒任务情义春秋猜成语答案逍遥观:鹏程万里
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案神机营:射石饮羽
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案昆仑山:拔刀相助
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案天工阁:鬼斧神工
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案丝路古道:单枪匹马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:与虎谋皮
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:李代桃僵
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:指鹿为马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:小鸟依人
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:千金买邻
 干货   2019-11-12
 
推荐阅读
 
 
 
>>返回首頁<<
 
靜靜地坐在廢墟上,四周的荒凉一望無際,忽然覺得,淒涼也很美
© 2005- 王朝網路 版權所有