二叉搜索树→平衡树(AVL、splay)总结
暑期专题二
距离上个专题总结连一个星期都没到。。。但刚放假时没怎么搞OI然后下个星期又要出外8天又没有时间,下个月还有3个专题,所以得稍微快一点。。。
平衡树是二叉搜索树的强化版,首先说一说二叉搜索树:
二叉搜索树是一种二叉树,它每个节点都对应有一个权值且任意两个节点权值互不相同,一棵二叉树成为二叉搜索树的条件如下:
1、它是一棵空树,否则满足所有下面条件。
2、对于任意节点,它的左子树的任意节点的权值都要小于这个节点的权值。
3、对于任意节点,它的右子树的任意节点的权值都要大于这个节点的权值。
那么看到了二叉搜索树的定义,可以得到它的几个基本的功能:
1:查找
查找二叉搜索树中是否有权值为n的节点。
这个很简单,根据二叉搜索树的定义,从根节点开始,n比当前节点大就往右找,否则往左找,找到一样的退出,如果到了叶子节点还是不一样就说明没有权值为n的节点。
2:插入
将一个权值为n的节点加入二叉搜索树(保证n的值与其他所有节点权值不同)。
如果当前树为空,直接将n变成根节点,否则也是先查找,找到叶子节点,再根据定义将n作为这个叶子节点的左节点或者右节点。
3:删除
将二叉搜索树中已经有的权值为n的节点删除。
如果n为叶子节点,直接将n删除就可以,如果n只有左节点或者右节点,那就将左节点或者右节点代替n原来的位置,如果都有,先用n的右子树代替n,然后一直往n的右节点搜索,知道找到一个没有左子树的节点,把n的左子树作为这个节点的右子树即可。
我们通过实践可以发现,节点插入的顺序的不同会直接导致形成的二叉搜索树的形态不同,比如说:
就是一个很好的例子。
对于同样的一堆节点,插入顺序的问题会导致二叉搜索树退化成为一条链,原本操作O(logN)的复杂的上升为O(N),而且根据二叉搜索树本身的功能欠缺导致无法优化,这时各种平衡树就应运而生了,平衡树有很多种,这里就不一一列举了。
一个树平衡的定义:
1、这个树是空树,否则满足一下所有条件。
2、每个节点左子树的深度与右子树的深的相差不超过1。
所以如果能维护树的平衡,我们就可以保证每次操作的时间都是O(logN)的。
首先讲讲AVL树。
大部分平衡树维护平衡的方式都是树的旋转,通过旋转可以将因为插入、删除等操作破坏了平衡的树重新获得平衡,大致分为四种情况。
1、某个节点的左子树比右子树深度大2,那个节点的左节点的左子树比右子树深度大2(LL)。
2、某个节点的左子树比右子树深度大2,那个节点的左节点的右子树比左子树深度大2(LR)。
3、某个节点的右子树比左子树深度大2,那个节点的右节点的左子树比右子树深度大2(RL)。
4、某个节点的右子树比左子树深度大2,那个节点的右节点的右子树比左子树深度大2(RR)。
说起来有点复杂,但画个图还是很容易弄明白是怎么回事的啦~(明明是你懒得插图好不好)
对于不平衡的现象,平衡树的解决办法是树的旋转,一共有两种旋转方式,左旋转和右旋转,两种旋转方式是互相对称的。这两种旋转统称为单旋转。
对于具体的选择操作看图可以明白,右旋转是把P(旋转位置)的左节点不变,右节点变为原来的父亲节点,右子树变成新的右子树的左子树,左旋转类似。(至于为啥要这么弄,最好还是自己琢磨一下,毕竟这一段是平衡树的精髓所在,这里给个小提示:旋转不能破坏二叉搜索树的基本性质)。
好了,了解了旋转,我们就要去解决实际问题了,回到上面的4种情况,我们画出图后可以发现LL和RR是对称的,LR和RL是对称的,所以我们只要讨论两种情况,剩下两种情况就可以对称弄出来。
首先是比较简单的LL(RR)
这是初始情况,我们只要对K1进行一次右旋转就会变成:新的平衡状态。
然后是LR(RL),这回就会麻烦一点。
这是初始情况,先对K1进行右旋转:还不行,但这时已经变成了LL状态,我们只要再对K2进行左旋转:就成功了 。
而会出现平衡问题的也就是插入和删除,只需要根据实际情况判断出需要进行怎样的旋转就可以,有一个秘诀:L情况进行右旋转,R情况进行左旋转(把右的往左变,把左的往右变)。
还有一种平衡树叫做splay,与AVL不同的是,splay不算严格意义上的平衡树,它容许有不平衡的现象存在,它在每次操作后都将操作的节点旋转到根节点的位置(splay操作),虽然也有退化成链的可能,但大部分情况下平均的时间复杂度都是O(logN)级别的。
对于进行splay操作的节点,有三种情况(假设要将x旋转到根节点):
1、x的父亲p是根节点。
2、x的父亲p不是根节点。
1情况我们只需要进行一次zig(单旋转)操作:
与AVL类似,x为右节点进行左旋转,x为左节点进行右旋转。
2情况就是AVL的4种平衡被破坏的情况,在splay中,分为两种情况:
一、x与p同为左节点或右节点,进行zig-zig(双旋转)操作。
这里是对x和p分别做一次旋转,同样,当x和p为左节点时右旋转,右节点时左旋转。
这里我们可以发现,splay操作后整棵树不一定就变成了平衡树,splay只是尽量将整棵树变得平衡。
二、x与p一个是左节点一个是右节点,进行zig-zag(双旋转)操作。
和AVL一样,对右节点进行左旋转,左节点进行右旋转。
对于splay的平衡效果,我们可以用一些具体操作看一下:
这是一开始的树,可以看到它已经退化成了链,假设我们要查询节点2,查询后对2进行splay操作:
处理完毕后2变为根节点,整棵树的深度也是大大减小了。
呼,总算写完了,这篇文章基本上是从很多神犇的博客里整合来的,图片也大部分来自于别人博客,全部手打还是很累的。。。。。。
本文章整合于:
http://www.cnblogs.com/vamei/archive/2013/03/24/2976545.html
http://blog.csdn.net/changtao381/article/details/8936765
http://www.cppblog.com/cxiaojia/archive/2012/08/20/187776.html
感谢以上神犇!
zhouzixuan
orzzzzzzz
xyyxiao007
@zhouzixuan orz,话说肘子你为什么不登录了再评论啊。。。