二叉搜索树

1. Introduction

二叉搜索树(BST)是一种特殊的二叉树,每个顶点最多可以有两个子节点。这种结构遵循BST属性,规定给定顶点的左子树中的每个顶点的值必须小于给定顶点的值,右子树中的每个顶点的值必须大于给定顶点的值。这个可视化实现了 'multiset' 属性:虽然所有的键都是不同的整数,但重复整数的信息被存储为频率属性(只显示出现多次的键)。作为演示,使用 Search(7) 函数来动画显示在上面随机生成的BST中搜索范围在1到99的随机值。


Adelson-Velskii Landis(AVL)树是一种自平衡的BST,它保持其高度在对数阶(O(log N)相对于AVL树中存在的顶点数(N)。

2. BST和平衡BST(AVL树)

要在标准二叉搜索树和AVL树(主要在插入和删除整数时有所不同)之间切换,请选择相应的标题。


我们还提供一个URL快捷方式,可以快速访问AVL树模式,可在https://visualgo.net/en/avl找到。URL中的 'en' 可以替换为您首选语言的两个字符代码(如果有的话)。

3. 动机

BST,特别是像AVL树这样的平衡BST,是实现某种类型(或映射)抽象数据类型(ADT)的有效数据结构。


表ADT应该有效地支持至少以下三种操作:

  1. Search(v) — 确定v是否存在于ADT中,
  2. Insert(v) — 将v添加到ADT中,
  3. Remove(v) — 从ADT中删除v

对于类似的讨论,请参考哈希表电子讲座幻灯片

3-1. 什么样的表ADT?

我们正在讨论一种特殊类型的表ADT,其中的键必须是有序的。这与允许无序键的其他类型的表ADT形成对比。


这种表ADT类型的具体要求将在后续幻灯片中进行阐明。

3-2. 使用Sorted Array / Vector

使用未排序的数组或向量来实现表ADT可能会导致效率低下:

  1. Search(v)的时间复杂度为O(N),因为如果v不存在,我们可能需要遍历ADT的所有N个元素,
  2. Insert(v)可以用O(1)的时间复杂度实现,只需在数组的末尾追加v
  3. Remove(v)的运行时间复杂度也为O(N),因为我们首先需要搜索v(已经是O(N)),然后关闭由删除操作产生的间隙 —— 这也是一个O(N)的操作。

3-3. 使用Sorted Array / Vector

排序的数组或向量实现表ADT可以提高Search(v)的性能,但这是以牺牲Insert(v)性能为代价的:

  1. 现在可以用时间复杂度为O(log N)来实现Search(v),因为我们可以在排序的数组上使用二分查找策略,
  2. Insert(v)现在的操作时间复杂度为O(N),因为我们需要使用类似插入排序的策略来确保数组保持排序,
  3. Remove(v)仍然在O(N)时间复杂度下运行。虽然Search(v)在O(log N)下操作,但我们仍然需要关闭由删除引起的间隙,这在O(N)下运行。

3-4. O(log N)复杂性?

本电子讲座的目标是介绍BST和平衡BST数据结构,即AVL树,它们使我们能够实现基本的表ADT操作,如 Search(v),Insert(v) 和 Remove(v) —— 以及其他一些表ADT操作(参见下一张幻灯片)——在O(log N) 时间内。这个时间复杂度明显小于 N。请尝试下面的交互式滑块,感受这个显著的差异。



log N = 20, N = 1048576.


PS: 更有经验的读者可能会注意到存在另一种数据结构,它可以更快地执行这三个基本的表ADT操作。但是,请继续阅读...

3-5. 其他表ADT操作

除了基本的三种操作外,还有几种其他的表ADT操作:

  1. 找到 Min()/Max() 元素,
  2. 找到 Successor(v),或者说是'下一个更大'的元素,和 Predecessor(v),或者说是'前一个更小'的元素,
  3. 按排序顺序列出元素,
  4. Rank(v) & Select(k)
  5. 还有其他可能的操作。

讨论:给定使用排序或未排序的数组/向量的约束,对于上述的前三个附加操作,最优的实现方式是什么?

3-6. 答案

[This is a hidden slide]

3-7. 链表怎么样?

可用于实现表ADT的更简单的数据结构是链接列表

Quiz: Can we perform all basic three Table ADT operations: Search(v)/Insert(v)/Remove(v) efficiently (read: faster than O(N)) using Linked List?

No
Yes

讨论:为什么?

3-8. 答案

[This is a hidden slide]

3-9. 哈希表 (Hash Table) 怎么样?

另一个可以用来实现表ADT的数据结构是哈希表。它具有非常快的 Search(v)、Insert(v) 和 Remove(v) 性能(所有这些都在预期的 O(1) 时间内)。


Quiz: So what is the point of learning this BST module if Hash Table can do the crucial Table ADT operations in unlikely-to-be-beaten expected O(1) time?

There is no point, so this BST module can be ignored
There are valid reasons, which are ____


讨论上述答案!提示:回到前4张幻灯片

3-10. 答案

[This is a hidden slide]

4. 可视化

我们现在将介绍BST数据结构。请参考上面提供的一个示例BST的可视化!


在BST中,根顶点是唯一的,没有父节点。相反,叶顶点,可以有几个,没有子节点。不是叶子的顶点被称为内部顶点。有时,根顶点不包括在内部顶点的定义中,因为只有一个顶点(即根顶点)的BST在技术上也可以符合叶子的定义。


在插图的例子中,顶点15是根,顶点5、7和50是叶子,顶点4、6、15(也是根)、23和71是内部顶点。

4-1. BST 的节点属性

每个顶点都有几个关键属性:指向左子节点的指针,指向右子节点的指针,指向父顶点的指针,键/值/数据,以及为实现 'multiset' 的这个可视化特别添加的:每个键的频率(可能还有其他属性)。并非所有属性都会用于所有顶点,例如,叶顶点的左右子属性都会 = NULL。其他一些实现将键(用于在BST中排序顶点)与与键关联的实际卫星数据分开。


顶点的左/右子(除叶子外)分别在该顶点的左/右和下方绘制。顶点的父(除根外)在该顶点上方绘制。每个顶点的(整数)键在代表该顶点的圆内绘制,如果有相同(整数)键的重复插入,将会有一个额外的连字符 '-' 和该键的实际频率(≥ 2)。在上面的例子中,(键)15的左子是6,右子是23。因此,6(和23)的父是15。一些键可能会以随机方式有 '-'(实际频率)。


讨论:实际上可以省略每个顶点的父指针。如何做到?

4-2. 删除父指针

[This is a hidden slide]

4-3. BST的属性

在这个可视化中,我们允许重复的整数,通过保持N(整数)键的不同,但任何现有键的重复将被存储为该键的'frequency'属性(可视化为'-'(实际频率,但只有当它≥2时))。因此,我们可以使用简单的BST属性,如下:对于每个顶点X,X的左子树上的所有顶点都严格小于X,X的右子树上的所有顶点都严格大于X。


在上面的例子中,根15的左子树上的顶点:{4, 5, 6, 7}都小于15,根15的右子树上的顶点:{23, 50, 71}都大于15。你也可以递归地检查其他顶点的BST属性。


在这个可视化中,我们允许键在[-99..99]的范围内。

5. BST的操作

我们为以下常见的 BST/AVL 树操作提供可视化:

  1. 查询操作(BST 结构保持不变):
    1. Search(v)(或 LowerBound(v)),
    2. Predecessor(v)(以及类似的 Successor(v)),以及
    3. Inorder/Preorder/Postorder 遍历,
  2. 更新操作(BST 结构(很可能)会改变):
    1. 创建 BST(几个标准),
    2. Insert(v),以及
    3. Remove(v)。

5-1. 一些其他的 BST 操作

在 VisuAlgo 中,还有一些其他的 BST (查询) 操作还未被可视化:

  1. Rank(v):给定一个键v,确定它在 BST 元素排序顺序中的排名(基于1的索引)。也就是说,Rank(FindMin()) = 1 和 Rank(FindMax()) = N。如果v不存在,我们可以报告 -1。
  2. Select(k):给定一个排名k,1 ≤ kN,确定在 BST 中具有该排名k的键v。或者换句话说,找到 BST 中第k小的元素。也就是说,Select(1) = FindMin() 和 Select(N) = FindMax()。

这两个操作的详细信息目前在某个 NUS 课程中被隐藏,以便于教学。

5-2. 静态与动态数据结构

如果没有(或很少)更新,特别是插入和/或删除操作,那么这种数据结构就被称为静态 (static) 数据结构。


即使有很多更新操作,也能保持高效的数据结构被称为动态 (dynamic) 数据结构。二叉搜索树(BST)和特别是平衡二叉搜索树(例如,AVL树)属于这一类别。

6. 搜索(v)

由于数据(对于这个可视化来说是不同的整数)在BST中的组织方式,我们可以二分搜索一个整数v(这就是二叉搜索树的名字的由来)。


首先,我们将当前顶点设置为根,然后检查当前顶点是小于/等于/大于我们正在搜索的整数v。然后我们分别进入右子树/停止/进入左子树。我们一直这样做,直到我们找到所需的顶点或者我们找不到。


在上面的BST示例中,尝试点击 Search(23)(在2次比较后找到),Search(7)(在3次比较后找到),Search(21)(在2次比较后未找到 - 在这一点上我们会意识到我们找不到21)。

6-1. lower_bound(v)

请注意,这个术语是基于C++ std::set::lower_bound中给出的定义。其他编程语言,例如,Java TreeSet有一个类似的方法 "higher()"。


如果v存在于BST中,那么 lower_bound(v)与Search(v)相同。但是,如果v不存在于BST中,lower_bound(v)将找到BST中严格大于v的最小值(除非v > BST中的最大元素)。如果稍后将这个当前不存在的v插入到这个BST中,这就是它的位置。

6-2. SearchMin() 和 SearchMax()

同样,由于BST内部数据的组织方式,我们可以通过从根开始,分别向左/右子树不断前进,找到最小/最大元素(在这个可视化中是一个整数)。


尝试点击上面示例BST中的 SearchMin()SearchMax()。答案应该是4和71(分别在与从根到最左顶点/最右顶点的3个整数比较后得出)。

6-3. O(h)时间复杂性

Search(v)/lower_bound(v)/SearchMin()/SearchMax() 操作在 O(h) 中运行,其中 h 是 BST 的高度。


但请注意,如上面的随机 '偏右' 示例所示,这个 h 在普通 BST 中可以高达 O(N)。尝试 Search(100)(这个值不应该存在,因为我们只使用 [1..99] 之间的随机整数来生成这个随机 BST,因此 Search 程序应该从根检查到唯一的叶子,时间为 O(N) —— 效率不高。

7. 后继(v)

由于BST属性,我们可以找到整数 v 的后继(假设我们通过之前调用 Search(v) 已经知道整数 v 的位置),如下所示:
  1. 如果 v 具有右子树,则 v 的右子树中的最小整数必须是 v 的后继。尝试Successor(23)(应为50)。
  2. 如果 v 没有右子树,我们需要遍历 v 的祖先,直到我们找到'右转'到顶点 w(或者,直到我们发现第一个大于顶点 v 的顶点 w)。 一旦我们找到顶点 w,我们将看到顶点 v w 的左子树中的最大元素。 试试Successor(7)(应该是15)。
  3. 如果 v 是BST中的最大整数,则 v 没有后继。 试试Successor(71)(应该没有)。

7-1. 前驱(v)

整数v的前驱的操作类似地定义(只是后继操作的镜像)。
尝试相同的三个镜像的极端情况:Predecessor(6)(应为5),Predecessor(50)(应为23),Predecessor(4)(应为无/none)。
此时,请暂停一会并思考这三个后继(v)/ 前驱(v)案例,以确保您理解这些概念。

7-2. O(h)时间复杂性

前驱(v)和后继(v)操作在 O(h) 中运行,其中h是BST的高度。
但请记住,这个h可以和正常BST中的 O(N) 一样高,如上面的随机“倾斜右侧”示例所示。 如果我们调用Successor(FindMax()),我们将在 O(N) 时间从最后一个叶子回到根 - 效率不高。

8. 中序遍历

我们可以执行这个BST的Inorder Traversal(中序遍历)来获得这个BST中的排序整数列表(事实上,如果我们将BST压平成一行,我们将看到顶点是从最小/最左边到最大/最右边来排序的)。

中序遍历是一种递归方法,我们首先访问左子树,遍历左子树中的所有项,访问当前子树的根,然后浏览右子树和右子树中的所有项。 不用多说了,让我们尝试Inorder Traversal,看看它在上面的BST示例中如何操作。

8-1. O(N)的时间复杂度

无论BST的高度如何,Inorder Traversal都以O(N)运行。
讨论:为什么?
PS:有些人调用N个无序整数插入O(N log N)中的BST,然后执行O(N)Inorder Traversal作为'BST sort'。 它很少使用,因为有几种比这更容易使用(基于比较)的排序算法

8-2. 答案

[This is a hidden slide]

8-3. 前序遍历和后序遍历

我们已经包含了前序遍历和后序遍历树的动画方法。


基本上,在前序遍历中,我们在访问左子树和右子树之前先访问当前的根。对于背景中显示的示例BST,我们有:{{15},{6, 4, 5, 7},{23, 71, 50}}。

PS:你注意到递归模式了吗?根,根的左子树的成员,根的右子树的成员。


在后序遍历中,我们先访问左子树和右子树,然后再访问当前的根。对于背景中显示的示例BST,我们有:{{5, 4, 7, 6},{50, 71, 23},{15}}。


讨论:给定一个BST的前序遍历,例如[15, 6, 4, 5, 7, 23, 71, 50],你能用它恢复原始的BST吗?对于后序遍历的类似问题也是可能的。

8-4. 答案

[This is a hidden slide]

9. 插入(v)

我们可以通过执行类似于Search(v)的操作将新的整数插入到BST中。但是这次,我们不再报告新的整数未找到,而是在插入点创建一个新的顶点,并将新的整数放在那里。尝试在上面的例子中使用 Insert(60)(第一次插入将创建一个新的顶点,但请看下面)。


由于我们现在实现了 'multiset',我们可以插入重复的元素,例如,尝试在上面的例子中使用 Insert(7)(多次)或再次点击 Insert(60)(重复的)。

9-1. O(h)时间复杂性

插入(v)在O(h)中运行,其中h是BST的高度。
到目前为止你应该知道这个 h 在正常BST中可以和 O(N) 一样高,如上面随机的“向右倾斜”示例所示。 如果我们调用Insert(FindMax()+1),即我们插入一个大于当前最大值的新整数,我们将在O(N)时间内从根向下移动到最后一个叶子,然后插入新整数作为最后一个叶子的右子节点 - 效率不高(请注意,在此可视化中我们最多只允许h=9)。

9-2. 小测验

Quiz: Inserting integers [1,10,2,9,3,8,4,7,5,6] one by one in that order into an initially empty BST will result in a BST of height:

8
10
9
The height cannot be determined

专业提示:您可以使用“探索模式”来验证答案。

10. 删除(v) - 三个可能的案例

我们可以通过执行类似于 Search(v) 的操作来从BST中删除一个整数。


如果在BST中找不到 v,我们就什么都不做。


如果在BST中找到了 v,我们不会报告找到了现有的整数 v,而是进行以下检查。如果 v 的频率 ≥ 2,我们只需将其频率减一,而不做任何其他操作。然而,如果 v 的频率正好为1,我们将执行三种可能的删除情况之一,这将在三个单独的幻灯片中详细说明(我们建议你逐一尝试它们)。

10-1. 删除(v) - 案例1

第一个情况是最简单的:顶点 v 目前是BST的叶子顶点之一。


删除叶子顶点非常简单:我们只需删除那个叶子顶点 - 尝试在上面的BST示例上点击 Remove(5)(如果随机化导致顶点5有多于一个的副本,只需再次点击该按钮)。


这部分显然是 O(1) ——在早先的 O(h) 搜索类似的努力之上。

10-2. 删除(v) - 案例2

第二种情况也不是那么难:顶点 v 是 BST 的(内部/根)顶点,并且它有 恰好一个子节点。如果不做任何其他操作就删除 v,将会断开 BST。


删除只有一个子节点的顶点并不难:我们将该顶点的唯一子节点与该顶点的父节点连接起来 - 尝试在上面的 BST 示例上点击 Remove(23)(如果随机化导致顶点 23 有多于一个的副本,只需再次点击该按钮)。


这部分也显然是 O(1) ——在早先的 O(h) 搜索类似的努力之上。

10-3. 删除(v) - 案例3

三个情况中,第三个情况是最复杂的:顶点 v 是BST的(内部/根)顶点,它有正好两个子节点。如果不做任何其他操作就删除 v,将会断开BST。


删除具有两个子节点的顶点的方法如下:我们用它的后继顶点替换该顶点,然后在其右子树中删除其重复的后继顶点 - 尝试在上面的示例BST上 Remove(6)(如果随机化导致顶点6有多于一个的副本,只需再次点击该按钮)。


由于需要找到后继顶点,这部分需要 O(h) —— 除了之前的 O(h) 搜索类似的努力。

10-4. 删除(v) - 案例3讨论

本案例3值得进一步讨论:

  1. 为什么用后继C替换有两个子节点的顶点B总是一个有效的策略?
  2. 我们可以用它的前身A替换有两个子节点的顶点B吗? 为什么或者为什么不?

10-5. 答案

[This is a hidden slide]

10-6. O(h) 时间复杂度

Remove(v) 的运行时间为 O(h),其中 h 是 BST 的高度。删除情况 3(删除具有两个子节点的顶点是最“重”的,但它不超过 O(h))。


如您现在应该完全理解的,h 在正常的 BST 中可以像在上面的随机“偏右”示例中一样高达 O(N)。如果我们调用 Remove(FindMax()),即我们删除当前的最大整数,我们将从根节点下降到最后一个叶节点,然后在 O(N) 时间内删除它(当其频率为 1 时)——这并不高效。

11. 创建BST

To make life easier in 'Exploration Mode', you can create a new BST using these options:

  1. Empty BST (you can then insert a few integers one by one),
  2. A few e-Lecture Examples that you may have seen several times so far,
  3. Random BST (which is unlikely to be extremely tall — the expected height of a randomly built BST is still O(log N)),
  4. Skewed Left/Right BST (tall BST with N vertices and N-1 linked-list like edges, to showcase the worst case behavior of BST operations; disabled in AVL Tree mode).

12. 间奏曲

我们正在解释这个BST模块的过程中。到目前为止,我们注意到许多基本的表ADT操作在O(h)中运行,h可以像显示的 '偏左' 示例那样高达N-1条边 —— 效率低 :(...


那么,有没有办法使我们的BST '不那么高'?


附言:如果你想学习这些基本BST操作在真实程序中是如何实现的,你可以下载这个BSTDemo.cpp | py | java

12-1. 尝试探索模式

此时,我们建议您按 [Esc] 或单击此e-Lecture幻灯片右下角的X按钮进入“探索模式”并自行尝试各种BST操作,以加强您对这种多功能数据结构的理解。
当您准备继续阅读平衡BST(以AVL树为示例)时,再次按 [Esc] 或从右上角的下拉菜单中将模式切换回“电子演讲模式”。 然后,使用幻灯片选择器下拉列表this slide 12-1恢复。

13. 平衡 BST

我们从之前的幻灯片中看到,除了中序遍历之外,我们的大部分BST操作都在 O(h) 中运行,其中h是BST的高度,可以与 N-1 一样高。
我们将继续讨论平衡BST的概念,以使得 h = O(log N)。

13-1. AVL 树

有几种已知的平衡BST的实现,但是太多了不能在VisuAlgo中逐一可视化和解释。
我们专注于AVL Tree(Adelson-Velskii&Landis,1962),以其发明者Adelson-Velskii和Landis命名。
其他平衡的BST实现(或多或少好于常数因子c)是:红黑树,B树/ 2-3-4树(Bayer&McCreight,1972),Splay树(Sleator 和Tarjan,1985),Skip Lists(Pugh,1989),Treaps( Seidel和Aragon,1996)等。

13-2. 额外的BST属性:高度 height(v)

为了促进AVL Tree的实现,我们需要增加 - 为每个BST顶点添加更多信息/属性。
对于每个顶点v,我们定义height(v):从顶点v到其最深叶子的路径上的边数。 此属性保存在每个顶点中,因此我们可以在O(1)中访问顶点的高度,而无需每次都重新计算它。

13-3. 高度 height(v) 的正式定义

正式公式是:

v.height = -1 (if v is an empty tree)
v.height = max(v.left.height, v.right.height) + 1 (otherwise)
因此,BST的高度是: root.height

在上面的例子BST上, height(11) = height(32) = height(50) = height(72) = height(99) = 0 (所有都是叶子)。height(29) = 1,因为有1个边将它连接到它唯一的叶子32上。

13-4. 小测试

Quiz: What are the values of height(20), height(65), and height(41) on the BST above?

height(65) = 2
height(20) = 2
height(65) = 3
height(20) = 3
height(41) = 3
height(41) = 4

13-5. BST高度的下限

If we have N elements/items/keys in our BST, the lower bound height h = Ω(log2 N) (the detailed formula in the next slide) if we can somehow insert the N elements in perfect order so that the BST is perfectly balanced.


See the example shown above for N = 15 (a perfect BST which is rarely achievable in real life — try inserting any other (distinct) integer and it will not be perfect anymore).

13-6. 下限的推导

N ≤ 1 + 2 + 4 + ... + 2h
N ≤ 20 + 21 + 22 + … + 2h
N ≤ 2h+1-1 (sum of geometric progression)
N+1 ≤ 2h+1 (apply +1 on both sides)
log2 (N+1) ≤ log2 2h+1 (apply log2 on both sides)
log2 (N+1) ≤ (h+1) * log2 2 (bring down the exponent)
log2 (N+1) ≤ h+1 (log2 2 is 1)
h+1 ≥ log2 (N+1) (flip the direction)
h ≥ log2 (N+1)-1 (apply -1 on both sides)

13-7. BST高度的上限

If we have N elements/items/keys in our BST, the upper bound height h = O(N) if we insert the elements in ascending order (to get skewed right BST as shown above).


The height of such BST is h = N-1, so we have h < N.


Discussion: Do you know how to get skewed left BST instead?

13-8. 答案

[This is a hidden slide]

13-9. 联合约束

我们已经看到大多数BST操作需要 O(h) 时间,并且结合h的下限和上限后会得到 log2 N < h < N
log2 N N 之间存在显着差异,我们从下限的讨论中看到,总是获得完美BST几乎不可能......
那么,对于一个小的常数因子c,我们可以得到高度接近 log2 N 的BST,即高度c * log2 N 的 BST 吗? 如果可以,那么需要O(h)运行的BST操作实际上只需 O(log N) 运行...

14. AVL 树

介绍AVL Tree,其早在1962年由两位俄罗斯(苏联)发明家 Georgy Adelson-Velskii和Evgenii Landis 发明。
在AVL树中,我们稍后会看到它的高度 h < 2 * log N(有更严谨的分析,但我们将在VisuAlgo中使用 c = 2 情况下的较简单的分析)。 因此,大多数AVL Tree操作以 O(log N) 时间高效运行。
插入(v)和删除(v)更新操作可能会更改AVL树的高度 h,但我们将看到旋转操作以保持较低的 AVL 树高度。

14-1. 步骤1:高效维持高度 height(v)

为了提高效率,每次有更新 (Insert(v)/Remove(v)) 操作时,我们都不会通过 O(N) 递归方法维护 height(v) 属性。
相反,我们在 Insert(v)/Remove(v) 操作的后面计算 O(1) 的:x.height = max(x.left.height, x.right.height) + 1,因为只有沿插入/移除路径的顶点的高度 (height) 可能会受到影响。 因此,只有 O(h) 顶点可以改变其 height(v) 属性,并且在AVL树中,h <2 * log N.
在示例AVL树上尝试Insert(37)(暂时忽略生成的旋转,我们将在接下来的几张幻灯片中回到它)。 请注意,沿插入路径只有几个顶点:{41,20,29,32}将高度增加+1,所有其他顶点的高度不变。

14-2. 第2步:定义AVL树不变式

让我们定义以下重要的AVL树不变式(永不改变的属性):如果|v.left.height - v.right.height| ≤ 1,则顶点 v 被称为高度平衡
如果BST中的每个顶点都是高度平衡的,则根据上面的不变式此BST被称为高度平衡。 这样的BST称为AVL Tree,就像上面的例子一样。
在这里暂停一会,并尝试插入一些新的随机顶点或删除一些随机存在的顶点。 生成的BST是否仍然被认为是高度平衡的?

14-3. 证明 - 1

Adelson-Velskii 和 Landis 声称具有N个顶点的AVL树(满足AVL树不变式的高度平衡BST)具有高度 h < 2 * log2N
证明依赖于高度为 h 的最小 AVL 树。
令 Nh 为高度为h的AVL树中的最小顶点数。
Nh的前几个值是N0 = 1(单个根顶点),N1 = 2(只有一个左子或一个右子的根顶点),N2 = 4,N3 = 7,N4 = 12,N5 = 20(见背景图片),等等(见下两张幻灯片)。

14-4. 证明 - 2

我们知道,对于 N 个顶点的任何其他AVL树(不一定是最小尺寸的),N ≥ Nh

Proof-2

在背景图片中,我们有N5 = 20个顶点,但我们知道在我们有一个高度为h = 5的完美二叉树之前,我们可以再挤进43个顶点(最多N = 63)。

14-5. 证明 - 3

Nh = 1 + Nh-1 + Nh-2 (高度为h的最小大小AVL树的公式)
Nh > 1 + 2*Nh-2 (因为 Nh-1 > Nh-2)
Nh > 2*Nh-2 (显然)
Nh > 4*Nh-4 (递归)
Nh > 8*Nh-6 (另一步递归)
... (我们只能做这个h/2次,假设初始h是偶数)
Nh > 2h/2*N0 (我们达到基本情况)
Nh > 2h/2 (因为 N0 = 1)
证明-3

14-6. 证明 - 4

N ≥ Nh > 2h/2 (结合前两张幻灯片)
N > 2h/2
log2(N) > log2(2h/2) (两边都取 log2)
log2(N) > h/2 (公式简化)
2 * log2(N) > h 或 h < 2 * log2(N)
h = O(log(N)) (最终结论)
Proof-4

14-7. 第3步:保持不变性

再看一下BST示例。 看到所有顶点都是高度平衡的AVL树。
为了快速检测顶点v是否高度平衡,我们将AVL树的(内部具有绝对函数的)不变式修改为:bf(v) = |v.left.height - v.right.height|
现在再次在AVL树上尝试Insert(37)。 插入路径上的几个顶点:{41,20,29,32}的高度增加1。 在插入之后顶点{29,20}将不再高度平衡了(并且将在稍后旋转 - 在接下来的几张幻灯片中讨论),i.e. bf(29)= -2和bf(20)= -2。 我们需要恢复平衡。

14-8. 介绍树旋转

树旋转

看上面的图片。在左图上调用 rotateRight(D) 将产生右图。在右图上调用 rotateLeft(B) 将再次产生左图。


只有当 T 有左/右子节点时,才能调用 rotateRight(T)/rotateLeft(T)


树旋转 保留 BST 属性。
旋转前,A < B < C < D < E。
旋转后,注意以 C 为根的子树(如果存在)更换了父节点,
但 A < B < C < D < E 的顺序并未改变。

14-9. 重要的 O(1) 树旋转的伪码

BSTVertex rotateLeft(BSTVertex T) // 先决条件:T的右子节点 T.right != null
BSTVertex w = T.right // 右旋是这个的镜像
w.parent = T.parent // 这个方法新手很难写对
T.parent = w
T.right = w.left
if (w.left != null) w.left.parent = T
w.left = T
// 更新 T 和 w 的高度 height
return w

14-10. 四个重新平衡案例

四种情况

只有以下四种情况:

  1. 左左情况:bf(F) = +2 和 bf(D) = +1,解决方案:rotateRight(F)
  2. 左右情况:bf(F) = +2 和 bf(B) = -1,解决方案:先 rotateLeft(B) 将此情况转变为左左情况,然后转到步骤1
  3. 右右情况:bf(B) = -2 和 bf(D) = -1,解决方案:rotateLeft(B)
  4. 右左情况:bf(B) = -2 和 bf(F) = +1,解决方案:先 rotateRight(F) 将此情况转变为右右情况,然后转到步骤3

14-11. 在AVL树中插入(v)

  1. 只需像普通BST一样插入v,
  2. 从插入点向上走AVL树回到根。每走一步,我们更新受影响顶点的高度和平衡因子:
    1. 如果有的话,停止在不平衡的第一个顶点(+2或-2),
    2. 使用四个树旋转案例中的一个来重新平衡它,例如 在上面的例子上尝试Insert(37)并通过调用 rotateLeft(29) 解决不平衡问题。

讨论:AVL Tree的 Insert(v) 操作是否还有其他树旋转情况?

14-12. 答案

[This is a hidden slide]

14-13. 在AVL树中删除(v)

  1. 只需删除正常BST中的v(三个删除案例中的一个),
  2. 在AVL树种从删除点向上走回根节点,每一步,我们都会更新受影响的顶点的高度和平衡因子:
    1. 现在,对于每个不平衡的顶点(+2或-2),我们使用四个树旋转情况中的一个来重新平衡它们(可能多于一个)。

与AVL树中的 Insert(v) 相比的主要区别在于,我们可能会多次触发四种可能的重新平衡情况中的一种,但不会超过 h = O(log N) 次 :O。在上面的示例中尝试Remove(7),能看到连锁反应rotateRight(6) 然后rotateRight(16) + rotateLeft(8)

14-14. AVL树摘要

我们现在已经看到了AVL树如何定义高度平衡不变式,在对Insert(v)和Remove(v)更新操作期间对所有顶点进行维护,并且证明了AVL树的高度 h < 2 * log N


因此,所有二叉搜索树(BST)操作(包括更新和查询操作,除了中序遍历),如果它们的时间复杂度为O(h),则在使用AVL树版本的BST时,它们的时间复杂度为O(log N)。


这标志着本次电子讲座的结束,但请切换到“探索模式”,并尝试在AVL树模式下进行各种Insert(v)和Remove(v)调用,以加强您对这种数据结构的理解。


附言:如果您想学习这些看似复杂的AVL树(旋转)操作如何在实际程序中实现,您可以下载这个AVLDemo.cpp | java(必须与这个BSTDemo.cpp | java)一起使用。

15. 附加功能

在这个模块的结尾,我们将讨论一些关于BST和平衡BST(尤其是AVL树)的有趣事情。

15-1. 那2个额外的BST操作

[This is a hidden slide]

15-2. 平衡BST还能怎样使用?

[This is a hidden slide]

15-3. 在线测验

关于这个数据结构的一些更有趣的问题,请在BST/AVL培训模块上进行练习(无需登录)。


然而,对于注册用户,您应该登录并从主页点击培训图标来正式完成这个模块,这样的成就将会被记录在您的用户账户中。

15-4. 在线评测练习

我们还有一些编程问题需要使用这种平衡的BST(如AVL Tree)数据结构:Kattis - compoundwordsKattis - baconeggsandspam
尝试使用它们来巩固和提高您对此数据结构的理解。 如果这样可以简化您的实现,则可以使用C ++ STL map / set或Java TreeMap / TreeSet。

尝试使用它们来巩固和提高您对此数据结构的理解。你可以使用 C++ STL map/set,Java TreeMap/TreeSet,或 OCaml Map/Set 来简化您的实现。请注意 Python 没有内置的平衡 BST 的实现。

15-5. 答案

[This is a hidden slide]