首页 > 笔记 > 各种树结构之二 AVL树

各种树结构之二 AVL树

闲话不多说

接着来

二叉搜索树的深度与搜索效率

一个有n个节点的二叉树,它的最小深度为log(n),最大深度为n。比如下面两个二叉树:
images

深度为n

images深度为log(n)

这两个二叉树同时也是二叉搜索树(参考这里)。注意,log以2为基底。log(n)是指深度的量级。根据我们对深度的定义,精确的最小深度为floor(log(n)+1)。

我们将处于同一深度的节点归为一层。如果除最后一层外的其他层都被节点填满时,二叉树有最小深度log(n)。

二叉搜索树的深度越小,那么搜索所需要的运算时间越小。一个深度为log(n)的二叉搜索树,搜索算法的时间复杂度也是log(n)。然而,我们在二叉搜索树中已经实现的插入和删除操作并不能让保持log(n)的深度。如果我们按照8,7,6,5,4,3,2,1的顺序插入节点,那么就是一个深度为n的二叉树。那么,搜索算法的时间复杂度为n。

n和log(n)的时间复杂度意味着什么呢?时间复杂度代表了完成算法所需要的运算次数。时间复杂度越小,算法的速度越快。

images

可以看到,随着元素的增加,log(n)的时间复杂度的增长要远小于n。所以,我们自然希望二叉搜索树能尽可能保持log(n)的深度。在上面深度为n的例子中,我们发现,每个节点只有左节点被填满。树的每一层都有很多空位。能不能尽可能减少每一层的空位呢? (相应的,减少树的深度)

一种想法是先填满一层,再去填充下一层,这样就是一个完全二叉树(complete binary tree)。这样的二叉树实现插入算法会比较复杂。所以今天介绍一种思路相似,但比较容易实现的树状数据结构——AVL树。

AVL树

AVL树是最先发明的自平衡二叉查找树,也被称为高度平衡树。相比于”二叉查找树”,它的特点是:AVL树中任何节点的两个子树的高度最大差别为1。

如下图:

images

AVL树的查找、插入和删除在平均和最坏情况下都是O(logn)。

如果在AVL树中插入或删除节点后,使得高度之差大于1。此时,AVL树的平衡状态就被破坏,它就不再是一棵二叉树;为了让它重新维持在一个平衡状态,就需要对其进行旋转处理。学AVL树,重点的地方也就是它的旋转算法;在后文的介绍中,再来对它进行详细介绍。

AVL树的实现

1.基本定义

1.1树的节点

1.2获取高度

1.3 计算高度

两子树高度最大者加一

2. 旋转
前面说过,如果在AVL树中进行插入或删除节点后,可能导致AVL树失去平衡。这种失去平衡的可以概括为4种姿态:LL(左左),LR(左右),RR(右右)和RL(右左)。下面给出它们的示意图:

images

总的来说,AVL树失去平衡时的情况一定是LL、LR、RL、RR这4种之一,它们都由各自的定义:

(1) LL:LeftLeft,也称为”左左”。插入或删除一个节点后,根节点的左子树的左子树还有非空子节点,导致”根的左子树的高度”比”根的右子树的高度”大2,导致AVL树失去了平衡。
例如,在上面LL情况中,由于”根节点(8)的左子树(4)的左子树(2)还有非空子节点”,而”根节点(8)的右子树(12)没有子节点”;导致”根节点(8)的左子树(4)高度”比”根节点(8)的右子树(12)”高2。

(2) LR:LeftRight,也称为”左右”。插入或删除一个节点后,根节点的左子树的右子树还有非空子节点,导致”根的左子树的高度”比”根的右子树的高度”大2,导致AVL树失去了平衡。
 例如,在上面LR情况中,由于”根节点(8)的左子树(4)的左子树(6)还有非空子节点”,而”根节点(8)的右子树(12)没有子节点”;导致”根节点(8)的左子树(4)高度”比”根节点(8)的右子树(12)”高2。

(3) RL:RightLeft,称为”右左”。插入或删除一个节点后,根节点的右子树的左子树还有非空子节点,导致”根的右子树的高度”比”根的左子树的高度”大2,导致AVL树失去了平衡。
例如,在上面RL情况中,由于”根节点(8)的右子树(12)的左子树(10)还有非空子节点”,而”根节点(8)的左子树(4)没有子节点”;导致”根节点(8)的右子树(12)高度”比”根节点(8)的左子树(4)”高2。

(4) RR:RightRight,称为”右右”。插入或删除一个节点后,根节点的右子树的右子树还有非空子节点,导致”根的右子树的高度”比”根的左子树的高度”大2,导致AVL树失去了平衡。
例如,在上面RR情况中,由于”根节点(8)的右子树(12)的右子树(14)还有非空子节点”,而”根节点(8)的左子树(4)没有子节点”;导致”根节点(8)的右子树(12)高度”比”根节点(8)的左子树(4)”高2。

前面说过,如果在AVL树中进行插入或删除节点后,可能导致AVL树失去平衡。AVL失去平衡之后,可以通过旋转使其恢复平衡,下面分别介绍”LL(左左),LR(左右),RR(右右)和RL(右左)”这4种情况对应的旋转方法。

2.1 LL的旋转

LL失去平衡的情况,可以通过一次旋转让AVL树恢复平衡。如下图:

images

图中左边是旋转之前的树,右边是旋转之后的树。从中可以发现,旋转之后的树又变成了AVL树,而且该旋转只需要一次即可完成。
对于LL旋转,你可以这样理解为:LL旋转是围绕”失去平衡的AVL根节点”进行的,也就是节点k2;而且由于是LL情况,即左左情况,就用手抓着”左孩子,即k1″向上拔。将k1变成根节点,k2变成k1的右子树,”k1的右子树”变成”k2的左子树”。

LL的旋转代码

 

2.2 RR的旋转

理解了LL之后,RR就相当容易理解了。RR是与LL对称的情况!RR恢复平衡的旋转方法如下:

images

图中左边是旋转之前的树,右边是旋转之后的树。RR旋转也只需要一次即可完成。

RR的旋转代码

 

2.3 LR的旋转

LR失去平衡的情况,需要经过两次旋转才能让AVL树恢复平衡。如下图:

images

第一次旋转是围绕”k1″进行的”RR旋转”,第二次是围绕”k3″进行的”LL旋转”。

LR的旋转代码

 

2.4 RL的旋转

RL是与LR的对称情况!RL恢复平衡的旋转方法如下:

images

第一次旋转是围绕”k3″进行的”LL旋转”,第二次是围绕”k1″进行的”RR旋转”。

RL的旋转代码

 

3. 插入

对于AVL树,可以证明,在新增一个节点时,总可以通过一次旋转恢复AVL树的性质。

当我们插入一个新的节点时,在哪里旋转?是用单旋转还是双旋转?

我们按照如下基本步骤进行:

1. 按照二叉搜索树的方式增加节点,新增节点称为一个叶节点。

2. 从新增节点开始,回溯到第一个失衡节点(5)。

(如果回溯到根节点,还没有失衡节点,就说明该树已经符合AVL性质。)

3. 找到断的边(5->3),并确定断弦的方向(5的左侧)

4. 以断边下端(3)为根节点,确定两个子树中的哪一个深度大(左子树还是右子树)。

(这两棵子树的深度不可能相等,而且深度大的子树包含有新增节点。)

5. 如果第2和第3步中的方向一致(都为左或者都为右),需要单旋转以失衡节点为根节点的子树。

否则,双旋转以失衡节点为根节点的子树。

插入节点的代码

4.删除

删除的方案有很多,但一般都会旋转下面这种,因为对整棵树各个分支深度的影响较小。

a.当被删除节点n是叶子节点,直接删除

b.当被删除节点n只有一个孩子,删除n,用孩子替代该节点的位置

c.当被删除结点n存在左右孩子时,真正的删除点是左子树最大的节点或右子树中最小的节点,之后n的值替换为真正删除点的值。这就把c归结为a,b的问题。

删除节点的代码

其他的操作和bst一样

参见 这里

The end.


1 COMMENT

  1. yhzq的徒弟2017-10-29 上午10:53

    %%

如果你觉的这篇文章不错,分享给朋友吧!

打开微信“扫一扫”,打开网页后点击屏幕右上角分享按钮

×