1x

Remarks: By default, we show e-Lecture Mode for first time (or non logged-in) visitor.
If you are an NUS student and a repeat visitor, please login.

🕑

Pro-tip 1: Since you are not logged-in, you may be a first time visitor (or not an NUS student) who are not aware of the following keyboard shortcuts to navigate this e-Lecture mode: [PageDown]/[PageUp] to go to the next/previous slide, respectively, (and if the drop-down box is highlighted, you can also use [→ or ↓/← or ↑] to do the same),and [Esc] to toggle between this e-Lecture mode and exploration mode.

🕑

Pro-tip 2: We designed this visualization and this e-Lecture mode to look good on 1366x768 resolution or larger (typical modern laptop resolution in 2021). We recommend using Google Chrome to access VisuAlgo. Go to full screen mode (F11) to enjoy this setup. However, you can use zoom-in (Ctrl +) or zoom-out (Ctrl -) to calibrate this.

🕑

Pro-tip 3: Other than using the typical media UI at the bottom of the page, you can also control the animation playback using keyboard shortcuts (in Exploration Mode): Spacebar to play/pause/replay the animation, / to step the animation backwards/forwards, respectively, and -/+ to decrease/increase the animation speed, respectively.

🕑

2. Insert(v)可以用O(1)的时间复杂度实现，只需在数组的末尾追加v
3. Remove(v)的运行时间复杂度也为O(N)，因为我们首先需要搜索v（已经是O(N)），然后关闭由删除操作产生的间隙 —— 这也是一个O(N)的操作。
🕑

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

log N = 20, N = 1048576.

🕑

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

🕑

The content of this interesting slide (the answer of the usually intriguing discussion point from the earlier slide) is hidden and only available for legitimate CS lecturer worldwide. This mechanism is used in the various flipped classrooms in NUS.

If you are really a CS lecturer (or an IT teacher) (outside of NUS) and are interested to know the answers, please drop an email to stevenhalim at gmail dot com (show your University staff profile/relevant proof to Steven) for Steven to manually activate this CS lecturer-only feature for you.

FAQ: This feature will NOT be given to anyone else who is not a CS lecturer.

🕑

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

🕑

The content of this interesting slide (the answer of the usually intriguing discussion point from the earlier slide) is hidden and only available for legitimate CS lecturer worldwide. This mechanism is used in the various flipped classrooms in NUS.

If you are really a CS lecturer (or an IT teacher) (outside of NUS) and are interested to know the answers, please drop an email to stevenhalim at gmail dot com (show your University staff profile/relevant proof to Steven) for Steven to manually activate this CS lecturer-only feature for you.

FAQ: This feature will NOT be given to anyone else who is not a CS lecturer.

🕑

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 are valid reasons, which are ____
There is no point, so this BST module can be ignored

🕑

The content of this interesting slide (the answer of the usually intriguing discussion point from the earlier slide) is hidden and only available for legitimate CS lecturer worldwide. This mechanism is used in the various flipped classrooms in NUS.

If you are really a CS lecturer (or an IT teacher) (outside of NUS) and are interested to know the answers, please drop an email to stevenhalim at gmail dot com (show your University staff profile/relevant proof to Steven) for Steven to manually activate this CS lecturer-only feature for you.

FAQ: This feature will NOT be given to anyone else who is not a CS lecturer.

🕑

🕑

🕑

The content of this interesting slide (the answer of the usually intriguing discussion point from the earlier slide) is hidden and only available for legitimate CS lecturer worldwide. This mechanism is used in the various flipped classrooms in NUS.

If you are really a CS lecturer (or an IT teacher) (outside of NUS) and are interested to know the answers, please drop an email to stevenhalim at gmail dot com (show your University staff profile/relevant proof to Steven) for Steven to manually activate this CS lecturer-only feature for you.

FAQ: This feature will NOT be given to anyone else who is not a CS lecturer.

🕑

🕑

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)。
🕑

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()。

🕑

🕑

🕑

🕑

🕑

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

🕑

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

🕑

🕑

🕑

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

🕑

The content of this interesting slide (the answer of the usually intriguing discussion point from the earlier slide) is hidden and only available for legitimate CS lecturer worldwide. This mechanism is used in the various flipped classrooms in NUS.

If you are really a CS lecturer (or an IT teacher) (outside of NUS) and are interested to know the answers, please drop an email to stevenhalim at gmail dot com (show your University staff profile/relevant proof to Steven) for Steven to manually activate this CS lecturer-only feature for you.

FAQ: This feature will NOT be given to anyone else who is not a CS lecturer.

🕑

PS：你注意到递归模式了吗？根，根的左子树的成员，根的右子树的成员。

🕑

The content of this interesting slide (the answer of the usually intriguing discussion point from the earlier slide) is hidden and only available for legitimate CS lecturer worldwide. This mechanism is used in the various flipped classrooms in NUS.

If you are really a CS lecturer (or an IT teacher) (outside of NUS) and are interested to know the answers, please drop an email to stevenhalim at gmail dot com (show your University staff profile/relevant proof to Steven) for Steven to manually activate this CS lecturer-only feature for you.

FAQ: This feature will NOT be given to anyone else who is not a CS lecturer.

🕑

🕑

🕑

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
The height cannot be determined
9
10

🕑

🕑

🕑

🕑

🕑

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

The content of this interesting slide (the answer of the usually intriguing discussion point from the earlier slide) is hidden and only available for legitimate CS lecturer worldwide. This mechanism is used in the various flipped classrooms in NUS.

If you are really a CS lecturer (or an IT teacher) (outside of NUS) and are interested to know the answers, please drop an email to stevenhalim at gmail dot com (show your University staff profile/relevant proof to Steven) for Steven to manually activate this CS lecturer-only feature for you.

FAQ: This feature will NOT be given to anyone else who is not a CS lecturer.

🕑

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

🕑

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

🕑

🕑

🕑

🕑

🕑

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

🕑

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

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

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

🕑
`N ≤ 1 + 2 + 4 + ... + 2hN ≤ 20 + 21 + 22 + … + 2hN ≤ 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?

🕑

The content of this interesting slide (the answer of the usually intriguing discussion point from the earlier slide) is hidden and only available for legitimate CS lecturer worldwide. This mechanism is used in the various flipped classrooms in NUS.

If you are really a CS lecturer (or an IT teacher) (outside of NUS) and are interested to know the answers, please drop an email to stevenhalim at gmail dot com (show your University staff profile/relevant proof to Steven) for Steven to manually activate this CS lecturer-only feature for you.

FAQ: This feature will NOT be given to anyone else who is not a CS lecturer.

🕑

log2 N N 之间存在显着差异，我们从下限的讨论中看到，总是获得完美BST几乎不可能......

🕑

🕑

🕑

🕑
Adelson-Velskii 和 Landis 声称具有N个顶点的AVL树（满足AVL树不变式的高度平衡BST）具有高度 h < 2 * log2N

Nh的前几个值是N0 = 1（单个根顶点），N1 = 2（只有一个左子或一个右子的根顶点），N2 = 4，N3 = 7，N4 = 12，N5 = 20（见背景图片），等等（见下两张幻灯片）。
🕑

🕑
`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/2log2(N) > log2(2h/2) (两边都取 log2)log2(N) > h/2 (公式简化)2 * log2(N) > h 或 h < 2 * log2(N)h = O(log(N)) (最终结论)`
🕑

🕑

🕑
`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) 解决不平衡问题。

🕑

The content of this interesting slide (the answer of the usually intriguing discussion point from the earlier slide) is hidden and only available for legitimate CS lecturer worldwide. This mechanism is used in the various flipped classrooms in NUS.

If you are really a CS lecturer (or an IT teacher) (outside of NUS) and are interested to know the answers, please drop an email to stevenhalim at gmail dot com (show your University staff profile/relevant proof to Steven) for Steven to manually activate this CS lecturer-only feature for you.

FAQ: This feature will NOT be given to anyone else who is not a CS lecturer.

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

🕑

🕑

🕑

The content of this interesting slide (the answer of the usually intriguing discussion point from the earlier slide) is hidden and only available for legitimate CS lecturer worldwide. This mechanism is used in the various flipped classrooms in NUS.

If you are really a CS lecturer (or an IT teacher) (outside of NUS) and are interested to know the answers, please drop an email to stevenhalim at gmail dot com (show your University staff profile/relevant proof to Steven) for Steven to manually activate this CS lecturer-only feature for you.

FAQ: This feature will NOT be given to anyone else who is not a CS lecturer.

🕑

The content of this interesting slide (the answer of the usually intriguing discussion point from the earlier slide) is hidden and only available for legitimate CS lecturer worldwide. This mechanism is used in the various flipped classrooms in NUS.

If you are really a CS lecturer (or an IT teacher) (outside of NUS) and are interested to know the answers, please drop an email to stevenhalim at gmail dot com (show your University staff profile/relevant proof to Steven) for Steven to manually activate this CS lecturer-only feature for you.

FAQ: This feature will NOT be given to anyone else who is not a CS lecturer.

🕑

🕑

🕑

The content of this interesting slide (the answer of the usually intriguing discussion point from the earlier slide) is hidden and only available for legitimate CS lecturer worldwide. This mechanism is used in the various flipped classrooms in NUS.

If you are really a CS lecturer (or an IT teacher) (outside of NUS) and are interested to know the answers, please drop an email to stevenhalim at gmail dot com (show your University staff profile/relevant proof to Steven) for Steven to manually activate this CS lecturer-only feature for you.

FAQ: This feature will NOT be given to anyone else who is not a CS lecturer.

You have reached the last slide. Return to 'Exploration Mode' to start exploring!

Note that if you notice any bug in this visualization or if you want to request for a new visualization feature, do not hesitate to drop an email to the project leader: Dr Steven Halim via his email address: stevenhalim at gmail dot com.

🕑

Toggle BST Layout

(k)

Traverse(root)

>

Examples

N =

Skewed

v =

v =

v =

k =

Inorder(root)

Preorder(root)

Postorder(root)

#### 关于

VisuAlgo最初由副教授Steven Halim于2011年构思，旨在通过提供自学、互动式学习平台，帮助学生更深入地理解数据结构和算法。

VisuAlgo涵盖了Steven Halim博士与Felix Halim博士、Suhendry Effendy博士合著的书《竞技编程》中讨论的许多高级算法。即使过去十年，VisuAlgo仍然是可视化和动画化这些复杂算法的独家平台。

VisuAlgo仍然在不断发展中，正在开发更复杂的可视化。目前，该平台拥有24个可视化模块。

VisuAlgo配备了内置的问题生成器和答案验证器，其“在线测验系统”使学生能够测试他们对基本数据结构和算法的理解。问题根据特定规则随机生成，并且学生提交答案后会自动得到评分。随着越来越多的计算机科学教师在全球范围内采用这种在线测验系统，它可以有效地消除许多大学标准计算机科学考试中手工基本数据结构和算法问题。通过给通过在线测验的学生分配一个小但非零的权重，计算机科学教师可以显著提高学生对这些基本概念的掌握程度，因为他们可以在参加在线测验之前立即验证几乎无限数量的练习题。每个VisuAlgo可视化模块现在都包含自己的在线测验组件。

VisuAlgo已经被翻译成三种主要语言：英语、中文和印尼语。此外，我们还用各种语言撰写了关于VisuAlgo的公开笔记，包括印尼语、韩语、越南语和泰语：

id, kr, vn, th.

#### 团队

Associate Professor Steven Halim, School of Computing (SoC), National University of Singapore (NUS)
Dr Felix Halim, Senior Software Engineer, Google (Mountain View)

CDTL TEG 1: Jul 2011-Apr 2012: Koh Zi Chun, Victor Loh Bo Huai

Jul 2012-Dec 2013: Phan Thi Quynh Trang, Peter Phandi, Albert Millardo Tjindradinata, Nguyen Hoang Duy
Jun 2013-Apr 2014 Rose Marie Tan Zhao Yun, Ivan Reinaldo

CDTL TEG 2: May 2014-Jul 2014: Jonathan Irvin Gunawan, Nathan Azaria, Ian Leow Tze Wei, Nguyen Viet Dung, Nguyen Khac Tung, Steven Kester Yuwono, Cao Shengze, Mohan Jishnu

Jun 2014-Apr 2015: Erin Teo Yi Ling, Wang Zi
Jun 2016-Dec 2017: Truong Ngoc Khanh, John Kevin Tjahjadi, Gabriella Michelle, Muhammad Rais Fathin Mudzakir
Aug 2021-Apr 2023: Liu Guangyuan, Manas Vegi, Sha Long, Vuong Hoang Long, Ting Xiao, Lim Dewen Aloysius

Optiver: Aug 2023-Oct 2023: Bui Hong Duc, Oleh Naver, Tay Ngan Lin

Aug 2023-Apr 2024: Xiong Jingya, Radian Krisno, Ng Wee Han

List of translators who have contributed ≥ 100 translations can be found at statistics page.

NUS教学与学习发展中心（CDTL）授予拨款以启动这个项目。在2023/24学年，Optiver的慷慨捐赠将被用来进一步开发 VisuAlgo。

#### 使用条款

VisuAlgo并不是一个完成的项目。Steven Halim副教授仍在积极改进VisuAlgo。如果您在使用VisuAlgo时发现任何可视化页面/在线测验工具中的错误，或者您想要请求新功能，请联系Steven Halim副教授。他的联系方式是将他的名字连接起来，然后加上gmail dot com。