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

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

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

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

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

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

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

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

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

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

使用未排序的数组或向量来实现表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)的操作。

用排序的数组或向量实现表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)下运行。

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

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

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

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

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

可用于实现表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?

另一个可以用来实现表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?

讨论上述答案！提示：回到前4张幻灯片。

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

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

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

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

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

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

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

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

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

我们为以下常见的 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)。

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

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

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

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

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

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

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

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

请注意，这个术语是基于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中，这就是它的位置。

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

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

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

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

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)（应该没有）。
   

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

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

基本上，在前序遍历中，我们在访问左子树和右子树之前先访问当前的根。对于背景中显示的示例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吗？对于后序遍历的类似问题也是可能的。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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).

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

那么，有没有办法使我们的BST '不那么高'？

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

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

正式公式是:

v.height = -1 (if v is an empty tree)
v.height = max(v.left.height, v.right.height) + 1 (otherwise)

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

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

If we have N elements/items/keys in our BST, the lower bound height h = Ω(log₂ 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).

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)

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?

我们知道，对于 N 个顶点的任何其他AVL树（不一定是最小尺寸的），N ≥ N_h。

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

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)

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)) (最终结论)

再看一下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。 我们需要恢复平衡。

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

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

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

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

只有以下四种情况：

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

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

讨论：AVL Tree的 Insert(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)。

我们现在已经看到了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）一起使用。

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

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

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

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