TREE-INSERT

概述

TREE-INSERT 是向二叉搜索树中插入一个新节点的操作。算法从根节点出发，沿着树向下搜索合适的叶位置，将新节点作为某个已有节点的子节点挂载上去。利用 BST 性质，搜索路径的长度不超过树高 $h$，因此运行时间为 $O(h)$。插入操作保持 BST 性质不变。

定义

TREE-INSERT

给定一棵二叉搜索树 $T$ 和一个待插入节点 $z$（$z.key$ 已设定，$z.left=z.right=z.p=NIL$），TREE-INSERT(T, z) 将 $z$ 插入到树中的正确位置，使 BST 性质保持不变。

伪代码

TREE-INSERT(T, z)
1  y = NIL
2  x = T.root
3  while x ≠ NIL
4      y = x
5      if z.key < x.key
6          x = x.left
7      else x = x.right
8  z.p = y
9  if y == NIL
10     T.root = z          // 树为空，z 成为根
11 elseif z.key < y.key
12     y.left = z
13 else y.right = z

逐步执行示例

向以下 BST 中插入 $z.key=7$：

初始树：        插入后：
    6              6
   / \            / \
  2   8    →     2   8
 / \   \        / \ / \
1   4   9      1  4 7  9

步骤	x	y	z.key 与 x.key 比较	操作
1	6	NIL	$7>6$	y=6, x=x.right=8
2	8	6	$7<8$	y=8, x=x.left=NIL
3	NIL	8	—	退出循环
4	—	—	—	z.p = 8
5	—	—	$7<8$	y.left = z

新节点 7 成为节点 8 的左子节点。

核心性质

循环不变式

循环不变式

对于 TREE-INSERT 中第 3-7 行的 while 循环：

不变式：在每次循环迭代开始时，

• $y$ 是 $x$ 的父节点（或 $y=NIL$ 当 $x$ 为根时）
• 若 $z.key$ 存在于树中，则 $z$ 应该被插入的位置是以 $x$ 为根的子树中

初始化：第一次迭代前，$y=NIL$，$x=T.root$。$y$ 是 $x$ 的”父节点”（根无父节点，用 NIL 表示），不变式成立。

保持：每次迭代中，先令 $y=x$（$y$ 成为当前 $x$ 的父节点），然后根据比较结果将 $x$ 移动到左子节点或右子节点。由 BST 性质，$z$ 的正确插入位置一定在新的 $x$ 子树中。不变式保持。

终止：循环终止时 $x=NIL$，说明已经到达了叶节点的空子指针位置。此时 $y$ 指向新节点的父节点，$z$ 应该作为 $y$ 的左子节点或右子节点插入。

时间复杂度

时间复杂度： $O(h)$

while 循环从根到叶，最多经过 $h$ 次迭代（$h$ 为树高）。循环内每次操作为 $\Theta (1)$，循环外操作也为 $\Theta (1)$，因此总时间为 $O(h)$。

• 平衡 BST：$O(\log n)$
• 退化为链：$O(n)$

插入后 BST 性质保持

正确性

插入操作完成后，BST 性质仍然成立。原因如下：

• 新节点 $z$ 被插入为某个叶节点的子节点（$z.left=z.right=NIL$）
• $z$ 的父节点 $y$ 满足：若 $z$ 是 $y$ 的左子节点，则 $z.key\le y.key$；若 $z$ 是 $y$ 的右子节点，则 $z.key\ge y.key$
• $z$ 没有子节点，因此不会违反任何以 $z$ 为根的 BST 性质
• 树中其他节点的子树结构未变，BST 性质不受影响

生活化类比

将 BST 想象为一个图书馆的分类书架：

• 每本书（节点）按编号（key）排列
• 插入一本新书时，从书架入口（根）出发，每次比较编号决定走向”编号较小的一侧”还是”编号较大的一侧”
• 一直走到书架末端（空位），把新书放在那里
• 放入新书不会打乱已有书籍的排列顺序

章节扩展

TREE-INSERT 是 BST 动态集合操作的插入部分。与之配对的是删除操作，删除操作更为复杂，需要借助 TRANSPLANT 子程序：

• TREE-DELETE：删除节点并保持 BST 性质，分为三种情况（无子节点、一个子节点、两个子节点），时间 $O(h)$
• TRANSPLANT：删除操作的核心子程序，用一棵子树替换另一棵子树在父节点中的位置

参见

• 二叉搜索树 — BST 的定义与性质
• 中序遍历 — 验证 BST 有序性的遍历方式
• TREE-SEARCH — 在 BST 中查找关键字
• TRANSPLANT — 删除操作的核心子程序
• 散列表 — 散列表的插入操作平均 $O(1)$，但不维护有序性