二叉搜索树

2025年3月17日 | 阅读 7 分钟

二叉搜索树以二叉树的形式组织。这样的树可以通过链接的数据结构定义，其中特定节点是一个对象。除了键字段外，每个节点还包含字段 left、right 和 p，分别指向对应于其左子节点、右子节点及其父节点的节点。如果缺少子节点或父节点，则相应的字段包含值 NIL。根节点是树中父字段为 Nil 的唯一节点。

二叉搜索树属性

设 x 是二叉搜索树中的一个节点。

如果 y 是 x 的左子树中的一个节点，那么 key [y] ≤ key [k]。
如果 z 是 x 的右子树中的一个节点，那么 key [x] ≤ key [y]。

在本树中，key [x] = 15

如果 y 是 x 的左子树中的一个节点，那么 key [y] = 5。

如果 y 是 x 的右子树中的一个节点，那么 key [y] = 20。

二叉搜索树的遍历

1. In-Order-Tree-Walk (x): 始终按排序顺序打印二叉搜索树中的键。

INORDER-TREE-WALK (x) - Running time is θ(n)
 1. If x ≠ NIL.
 2. then INORDER-TREE-WALK (left [x])
 3. print key [x]
 4. INORDER-TREE-WALK (right [x])

2. PREORDER-TREE-WALK (x): 在其中我们在任一子树中的节点之前访问根节点。

PREORDER-TREE-WALK (x): 
 1. If x ≠ NIL.
 2. then print key [x]
 3. PREORDER-TREE-WALK (left [x]).
 4. PREORDER-TREE-WALK (right [x]).

3. POSTORDER-TREE-WALK (x): 在其中我们在子树中的节点之后访问根节点。

POSTORDER-TREE-WALK (x): 
 1. If x ≠ NIL.
 2. then POSTORDER-TREE-WALK (left [x]).
 3. POSTORDER-TREE-WALK (right [x]).
 4. print key [x]

查询二叉搜索树

1. 搜索： TREE-SEARCH (x, k) 算法搜索节点 x 的树节点，该节点的键值等于 k。如果存在则返回指向该节点的指针，否则返回 NIL。

TREE-SEARCH (x, k)
 1. If x = NIL or k = key [x].
 2. then return x.
 3. If k < key [x].
 4. then return TREE-SEARCH (left [x], k)
 5. else return TREE-SEARCH (right [x], k)

显然，该算法在 O (h) 时间内运行，其中 h 是树的高度。上述算法的迭代版本很容易实现

ITERATIVE-TREE- SEARCH (x, k)
 1. while x ≠ NIL and k ≠ key [k].
 2. do if k < key [x].
 3. then x ← left [x].
 4. else x ← right [x].
 5. return x.

2. 最小和最大值： 键为最小值的二叉搜索树中的一个项目可以通过从根节点开始遵循左子节点指针直到遇到 NIL 来找到。以下过程返回指向以给定节点 x 为根的子树中的最小元素的指针。

TREE- MINIMUM (x)
 1. While left [x] ≠ NIL.
 2. do x←left [x].
 3. return x.

TREE-MAXIMUM (x)
 1. While left [x] ≠ NIL
 2. do x←right [x].
 3. return x.

3. 后继者和前驱者： 给定二叉搜索树中的一个节点，有时我们用来找到其在由中序树遍历确定的排序形式中的后继者。如果所有键都是特定的，则节点 x 的后继者是键大于 key[x] 的最小键的节点。二叉搜索树的结构允许我们无需比较键即可推断节点的后继者。以下操作返回二叉搜索树中节点 x 的后继者（如果存在），如果 x 具有树中最大的键，则返回 NIL

TREE SUCCESSOR (x)
 1. If right [x] ≠ NIL.
 2. Then return TREE-MINIMUM (right [x]))
 3. y←p [x]
 4. While y ≠ NIL and x = right [y]
 5. do x←y
 6. y←p[y]
 7. return y.

TREE-SUCCESSOR 的代码分为两种情况。如果节点 x 的右子树不为空，那么 x 的后继者就是右子树中最左边的节点，我们通过调用 TREE-MINIMUM (right [x]) 在第 2 行中找到它。另一方面，如果节点 x 的右子树为空，并且 x 有后继者 y，那么 y 是 x 的最低祖先，其左子节点也是 x 的祖先。为了找到 y，我们快速从 x 向上遍历树，直到我们遇到一个节点，该节点是其父节点的左子节点； TREE-SUCCESSOR 的第 3-7 行处理这种情况。

TREE-SUCCESSOR 在高度为 h 的树上的运行时间为 O (h)，因为我们要么沿树向上的一条简单路径，要么沿树向下的一条简单路径。过程 TREE-PREDECESSOR 与 TREE-SUCCESSOR 对称，也在 O (h) 时间内运行。

4. 在二叉搜索树中插入： 要将新值插入到二叉搜索树 T 中，我们使用过程 TREE-INSERT。该过程采用一个节点，其中 key [z] = v, left [z] NIL, and right [z] = NIL。它修改 T 和 z 的某些属性，以便将其插入到树中的适当位置。

TREE-INSERT (T, z)
 1. y ←NIL.
 2. x←root [T]
 3. while x ≠ NIL.
 4. do y←x
 5. if key [z]< key [x]
 6. then x←left [x].
 7. else x←right [x].
 8. p [z]←y
 9. if y = NIL.
 10. then root [T]←z
 11. else if key [z] < key [y]
 12. then left [y]←z

例如

图： TREE-INSERT 的工作原理

假设我们要将一个键为 13 的项目插入到二叉搜索树中。

  x = 1
  y = 1 as x ≠ NIL.
  Key [z] < key [x]
      13 < not equal to 12.
  x ←right [x].
  x ←3
Again x ≠ NIL
  y ←3
  key [z] < key [x]
      13 < 18
  x←left [x]
  x←6
Again x ≠ NIL, y←6
  13 < 15
  x←left [x]
  x←NIL
  p [z]←6

现在我们的节点 z 将是其父节点 (y) 的左子节点或右子节点。

  key [z] < key [y]
     13 < 15
  Left [y] ← z
  Left [6] ← z

因此，在索引为 6 的节点的左侧插入一个节点。

5. 在二叉搜索树中删除： 从树中删除一个节点时，维护树中隐含的任何关系至关重要。将考虑从二叉搜索树中删除节点

有三种不同的情况

没有子节点的节点： 这种情况很简单。只需将父节点的指向要删除的节点的指针设置为 nil 并删除该节点即可。
有一个子节点的节点： 当 z 没有左子节点时，我们用其右子节点（可能或可能不是 NIL）替换 z。当 z 没有右子节点时，我们用其右子节点替换 z。
有两个子节点的节点： 当 z 同时具有左子节点和右子节点时。我们找到 z 的后继者 y，它位于右侧 z 的右子树中，并且没有左子节点（z 的后继者将是右子树的最小值节点，因此它没有左子节点）。
- 如果 y 是 z 的右子节点，那么我们替换 z。
- 否则，y 位于 z 的右子树中，但不是 z 的右子节点。在这种情况下，我们首先用自己的右子节点替换 z，然后用 y 替换 z。

TREE-DELETE (T, z)
 1. If left [z] = NIL or right [z] = NIL.
 2. Then y ← z
 3. Else y  ← TREE- SUCCESSOR (z)
 4. If left [y] ≠ NIL.
 5. Then x ← left [y]
 6. Else x ← right [y]
 7. If x ≠NIL
 8. Then p[x] ← p [y]
 9. If p[y] = NIL.
 10. Then root [T] ← x
 11. Else if y = left [p[y]]
 12. Then left [p[y]] ← x
 13. Else right [p[y]] ← y
 14. If y ≠ z.
 15. Then key [z] ← key [y]
 16. If y has other fields, copy them, too.
 17. Return y

该过程在高度为 h 的树上运行 O (h) 时间。

例如： 从二叉搜索树中删除节点 z。节点 z 可能是根节点、节点 q 的左子节点或 q 的右子节点。