数据结构和平衡二叉树的讲解(数据结构与算法-二叉查找树平衡)

上节讨论的DSW算法可以从全局重新平衡树:每个节点都可能参与树的重新平衡,或者从节点中移除数据,或者重新设置指针的值。但是,当插入或删除元素时,将只影响树的一部分,此时树的重新平衡可以只在局部进行。局部平衡二叉查找树有一个鼎鼎大名的算法,叫做AVL算法,由AVL算法构建出来的二叉树称之为AVL树。

数据结构和平衡二叉树的讲解(数据结构与算法-二叉查找树平衡)(1)

AVL树首先是一颗二叉查找树,其次,AVL树要求每个节点左右子树的高度差最大为1。例如,图1-1中的所有树都是AVL树。节点中的数字表示平衡因子,即左右子树的高度差。平衡因子等于右子树的高度减去左子树的高度。对于AVL树,所有的平衡因子都应是 1、0或-1。平衡AVL树的技术不保证得到的树是完全平衡的,但却是高度平衡的。有关平衡的概念可以参考数据结构与算法-二叉查找树平衡(DSW)。

假设我们已经有了一颗AVL树,那么如何保证在插入或者删除元素时继续保持AVL树的特性呢?

  • 插入

前人对于AVL树的插入操作进行总结,发现一共有4种情况需要讨论。其中,在左子树中插入有两种情况,在右子树中插入也有两种情况。并且它们是对称的,因此,我们以右子树为例,只需要讨论两种情况即可。

假设我们在AVL树中插入一个新的节点p,那么p的父节点以及祖父节点的平衡因子都有可能改变,我们从下到上更新节点的平衡因子,如果发现某个节点的平衡因子成为 2或者-2,那么就以该节点为根截取这段子树。如果根节点平衡因子成为了 2,代表节点插入到了右子树中,如果根节点平衡因子成为了-2,代表节点插入到了左子树。我们这里只讨论 2,即节点插入到右子树上的两种情况。

如果节点平衡因子变成了 2,那么,我们可以将这颗子树抽象出来,它必然是下面这种样子:

数据结构和平衡二叉树的讲解(数据结构与算法-二叉查找树平衡)(2)

也就是说,如果插入新节点使P节点的平衡因子成了 2,那么以P为根的子树,必然是上面的样子。插入的新节点要么放在Q的左子树上,要么放在Q的右子树上,这就是我们要讨论的两种情况。

1、RR

第一种情况有个简称,叫做RR,也就是说新节点插入到右子树的右节点,就像这样:

数据结构和平衡二叉树的讲解(数据结构与算法-二叉查找树平衡)(3)

怎么处理呢?P节点的左子树比右子树低,还记得左旋的效果吗?左旋可以提高左子树的高度,降低右子树的高度,用在这里正合适。将Q节点围绕P节点进行左旋之后效果如下:

数据结构和平衡二叉树的讲解(数据结构与算法-二叉查找树平衡)(4)

非常完美,左旋在这里产生了两个效果。首先,左旋使当前子树重新保持平衡,其次,左旋没有改变当前子树的高度。左旋之前子树高度为h 2,左旋之后依然是h 2。这就意味着,从Q节点开始往上的节点不需要更新平衡因子了。所以,左旋使得算法变得足够简单。

  • RL

顾名思义,RL的意思是将新节点插入到右子树的左节点上,就像这样:

数据结构和平衡二叉树的讲解(数据结构与算法-二叉查找树平衡)(5)

怎么处理呢?首先还是左旋,但是很快你会发现,左旋确实提高了左子树高度,但是太高了,又造成了新的不平衡,就像这样:

数据结构和平衡二叉树的讲解(数据结构与算法-二叉查找树平衡)(6)

究其原因,是h 1那颗子树大大提高了左子树高度,我们必须把它放在右子树上才行,可以这样处理。首先,我们认为,如果是因为在P树的右子树的左节点上插入元素导致P节点不平衡,那么,在没有插入新节点之前,P树肯定是下面这种样子的:

数据结构和平衡二叉树的讲解(数据结构与算法-二叉查找树平衡)(7)

Q的左子树插入了新的节点,可能插入到R的左子树或者右子树,先不管这个,为了降低Q的左子树的高度,将R围绕着Q进行右旋,结果是这样:

数据结构和平衡二叉树的讲解(数据结构与算法-二叉查找树平衡)(8)

靠谱,R的左子树高度就是就是m1树的高度,既可能是h - 1,也可能是h,但是都比h 1要小,这时我们再做一次左旋,结果如下:

数据结构和平衡二叉树的讲解(数据结构与算法-二叉查找树平衡)(9)

完美,R树最终平衡了,并且R树的高度依然保持在h 2,这也意味着不必更新R节点之上的祖先节点的平衡因子了。至于P和Q节点的平衡因子,这要看新节点是插入到m1树还是m2树上了,但是无论如何,R树都已经高度平衡了。

总结一下,对于RL形式的子树,首先对右子树的左节点做一次右旋,然后对新的根节点做一次左旋即可。

插入还有LL,LR两种形式,但是它们分别和RR,RL形式对称,这里就不多介绍了。

这里有个我看到的非常精辟的总结,引用一下:

数据结构和平衡二叉树的讲解(数据结构与算法-二叉查找树平衡)(10)

下面介绍删除节点之后如何平衡二叉查找树。

  • 删除

删除比插入更加复杂,但是有着插入节点积累的经验,理解删除反而更加容易。

删除节点首先面对的问题是平衡因子从哪个节点开始变化的?这就要说到二叉查找树的删除逻辑了,在数据结构与算法-二叉查找树中有着详细的介绍。这里简单介绍一下,删除叶子节点或者度为1的节点,平衡因子从被删除节点的父节点开始变化。删除度为2的节点需要使用复制删除的技巧,使用被删除节点的直接前驱或者直接后继来替换被删除节点,然后删除直接前驱或者直接后继,那么,平衡因子就是从直接前驱或者直接后继的父节点开始变化的。

既然知道了平衡因子开始变化的节点,就可以从下到上的更新平衡因子的变化。

在探讨插入节点引起的二叉树的变化时,我们总结出了RR、RL、LL、LR四种情况,删除节点会引起怎样的变化呢?

删除和插入有两个不同点:

1、删除不仅包含以上四中变化,还多出两种,当然这两种也是对称的

数据结构和平衡二叉树的讲解(数据结构与算法-二叉查找树平衡)(11)

多出来的两种是当前节点的父节点的平衡因子等于 2或者-2时,当前节点的平衡因子等于0。

插入节点之所以没有这两种变化,是因为插入节点使当前节点平衡因子变成0,说明当前节点的高度没有变化,更加不会引起祖先节点的平衡因子变化了。而删除节点时,如果当前节点平衡因子变成0,那么当前节点的高度其实变小了,可能引起祖先节点的平衡因子变化。

怎么处理这种情况呢?如果父节点平衡因子等于 2,那就对当前节点进行左旋。如果父节点平衡因子等于-2,那就对当前节点进行右旋即可。

2、重新平衡过程没有在发现平衡因子为 2或者-2的第一个节点P后停止,而是追踪到根节点

在插入节点的重新平衡过程中,我们在意的是第一个平衡因子为 2或者-2的节点,原因在于我们执行左旋或者右旋之后,子树不仅重新平衡并且高度也和没有插入节点之前保持一致,因此,祖先节点的平衡因子就不会发生变化了。但是删除节点发生了变化,重新平衡之后子树的高度变小了。

为什么重新平衡之后,插入节点高度不变而删除节点高度变小呢?

可以思考下平衡的过程,假设平衡因子变化为 2的节点为P,它的左子树高度为h,右子树高度必然为h 1,只有在右子树插入新的节点,P节点的平衡因子才会变化为 2,重新平衡之后该树的左右子树高度为h 1,因此该树的高度h 2没有变化。但是对于删除又有不同,假设P节点左子树高度为h,右子树高度必然为h 1,只有在左子树删除节点之后,P节点的平衡因子才会变化为2,重新平衡之后该树的左右子树的高度为h,那么该树的高度h 1比原来就减少了1。因为上述原因,删除节点之后重新平衡的逻辑不能只执行一次,而是从平衡因子发生变化的节点开始往上一直追踪到根节点,发现不平衡的节点都要执行平衡逻辑。

到此为止,AVL树中添加和删除节点的逻辑已经探讨完毕。当然,这里纯粹是学术上的探讨,没有代码示例,更加精深的内容需要在实践中摸索。

知识的积累从来不是看了一两篇文章就可以完成的,毕竟,功夫在诗外。

数据结构与算法-二叉查找树平衡(DSW)

,

免责声明:本文仅代表文章作者的个人观点,与本站无关。其原创性、真实性以及文中陈述文字和内容未经本站证实,对本文以及其中全部或者部分内容文字的真实性、完整性和原创性本站不作任何保证或承诺,请读者仅作参考,并自行核实相关内容。文章投诉邮箱:anhduc.ph@yahoo.com

    分享
    投诉
    首页