二叉搜索树→平衡树(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操作:

zig-zag

zig-zig

zig

处理完毕后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

感谢以上神犇!

 

评论

2条评论
  1. Gravatar 头像

    zhouzixuan 回复

    orzzzzzzz

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据