二元搜寻树

二叉搜索树（binary search tree，简称BST）又称有序二叉树（ordered binary tree）或排序二叉树（sorted binary tree）。是一种有根二叉树数据结构。它要求每个内部节点的键值都大于其左子树中所有节点的键值，且都小于其右子树中所有节点的键值。该树各项操作时间复杂度均与树的高度成线性关系。

二叉搜索树每次比较都能排除大约一半的剩余节点，故能以对数时间查找、插入、删除数据。但其性能依赖于节点的插入顺序，插入随机键值时仍能维持对数级别，但在最好、最坏、平均情况下会退化成链表。为保证效率，研究者发明了多种平衡树，能将最坏查找复杂度维持在$O(\log n)$。

二叉搜索树最早由多位研究者独立提出，1960年被用来解决带标签数据的存储问题。其还可用来实现树排序及优先队列。

## 历史

二叉搜索树最早由多位研究者独立提出，包括P.F.温德利、安德鲁·唐纳德·布思、安德鲁·科林、托马斯·N·希巴德。这种数据结构常被归功于康威·柏纳-李及大卫·惠勒，他们在1960年将之用于磁带上带标签数据的存储。希巴德实现二叉搜索树的方法也是最早广为流传的一种。

若按任意顺序插入节点，树的高度可能接近节点数，导致操作效率急剧下降。研究者们发明了平衡树（即能够自平衡的二叉搜索树），将树的高度限制在$O(\log n)$以内。同时，相关人员也提出了多种高度平衡的二叉搜索树结构，例如AVL树、树堆、红黑树等。其中，AVL树是首类平衡树，由格奥尔吉·阿杰尔松-韦利斯基及叶夫根尼·兰迪斯于1962年发明，用于高效组织信息。

## 性质

二叉搜索树为有根节点的二叉树，其节点顺序为严格全序关系，每个节点都满足：左子树上所有节点的键值都小于该节点，右子树上所有节点的键值都大于该节点。这一结构保证可以在对数时间内定位任意键值。除查找外，其也常用于排序，但性能取决于节点的插入和删除顺序——在最好、最坏、平均情况下，连续操作可能使树退化为类似单链表的结构，这时的查找复杂度与链表相同。

## 遍历

二叉搜索树的遍历有三种基本方法：前序、中序、后序。

- 中序遍历：依次遍历左子树、根节点、右子树。遍历结果为键值递增顺序。
- 前序遍历：依次遍历根节点、左子树、右子树。
- 后序遍历：依次遍历左子树、右子树、根节点。

以下是递归实现的遍历伪代码：

Inorder-Tree-Walk(x) if x ≠ NIL then Inorder-Tree-Walk(x.left) visit node Inorder-Tree-Walk(x.right) end if｜Preorder-Tree-Walk(x) if x ≠ NIL then visit node Preorder-Tree-Walk(x.left) Preorder-Tree-Walk(x.right) end if｜Postorder-Tree-Walk(x) if x ≠ NIL then Postorder-Tree-Walk(x.left) Postorder-Tree-Walk(x.right) visit node end if

## 操作

### 搜索

在二叉搜索树中查找某个特定的键，可以使用递归或迭代方式实现。

查找过程从树的根节点开始：

- 如果根节点为空（$\text{nil}$），说明该键不存在。
- 如果根节点的键值与目标键值相等，返回该节点，表示查找成功。
- 如果目标键值小于根节点的键值，则继续在左子树中查找。
- 如果目标键值大于根节点的键值，则继续在右子树中查找。

重复上述步骤，直到找到该键，或者剩余子树为空。若到达空子树仍未找到，说明该键不存在于树中。

#### 递归搜索

以下伪代码展示递归方式实现的查找过程：

Recursive-Tree-Search(x, key) if x = NIL or key = x.key then return x if key < x.key then return Recursive-Tree-Search(x.left, key) else return Recursive-Tree-Search(x.right, key) end if

递归会一直进行，直到遇到$\text{nil}$或是找到目标键$\text{key}$。

#### 迭代搜索

递归过程也可展开为循环形式，一般情况下循环版本的效率更高。其伪代码如下：

Iterative-Tree-Search(x, key) while x ≠ NIL and key ≠ x.key do if key < x.key then x := x.left else x := x.right end if repeat return x

由于查找可能会一直到叶节点，因此时间复杂度为树的高度$O(h)$（$h$为树的高度）。在最坏情况下，一棵严重不平衡的二叉搜索树可能退化成单链表，这时复杂度会达到$O(n)$（$n$为树中节点总数）。但对于高度平衡的二叉搜索树而言，复杂度为$O(\log n)$。

#### 后继与前驱

在某些场景下，需要查找给定节点的“后继”或“前驱”。后继节点是大于该节点键值的节点中，键值最小的那一个；前驱节点是小于该节点键值的节点中，键值最大的那一个。以下伪代码给出求节点$\text{x}$的后继与前驱方法：

BST-Successor(x) if x.right ≠ NIL then return BST-Minimum(x.right) end if y := x.parent while y ≠ NIL and x = y.right do x := y y := y.parent repeat return y｜BST-Predecessor(x) if x.left ≠ NIL then return BST-Maximum(x.left) end if y := x.parent while y ≠ NIL and x = y.left do x := y y := y.parent repeat return y

寻找树中键值最大或最小的节点，是寻找后继与前驱过程中的重要环节。其伪代码如下：

BST-Maximum(x) while x.right ≠ NIL do x := x.right repeat return x｜BST-Minimum(x) while x.left ≠ NIL do x := x.left repeat return x

#### 选择与排名

若在节点中维护以之为根节点的子树的节点总数，则可实现选择与排名操作。选择操作用于在树中直接定位排名为$k$的节点，即第$k$小的键。排名操作则与之相对，给定指定键后，其会返回小于该键的节点数。这两种操作的伪代码如下：

Select‑By‑Rank(T, k) return Select(T.root, k) Select(x, k) if x = NIL then return NIL end if t := size(x.left) if t > k then return Select(x.left, k) else if t < k then return Select(x.right, k − t − 1) else return x end if

Rank-In-Tree(T, key) return Rank(key, T.root) Rank(key, x) if x = NIL then return 0 cmp := compare(key, x.key) if cmp 0 then return 1 + size(x.left) + Rank(key, x.right) else return size(x.left) end if

其中`size`表示子树规模信息，即子树中节点数量。

#### 范围查找

利用中序遍历，可以实现范围查找 (计算机科学)，即查询两个给定值之间的元素数量。其伪代码如下：

Range-Query(x, lo, hi, list) if x = NIL then return end if if lo x.key then Range-Query(x.right, lo, hi, list) end if

其中`list`是用来收集结果的列表（也可视作队列）。上述过程将所有符合条件的值加入列表中，并跳过不可能含有目标值的子树。

### 插入

二叉搜索树的数据结构会随插入和删除操作而变化。插入操作须保证二叉搜索树的性质不会遭到破坏，且插入的节点总是作为叶节点加入。以下伪代码给出迭代形式的插入过程：

1 BST-Insert(T, z) 2 y := NIL 3 x := T.root 4 while x ≠ NIL do 5 y := x 6 if z.key < x.key then 7 x := x.left 8 else 9 x := x.right 10 end if 11 repeat 12 z.parent := y 13 if y = NIL then 14 T.root := z 15 else if z.key < y.key then 16 y.left := z 17 else 18 y.right := z 19 end if

过程使用变量$\text{y}$作为遍历节点$\text{x}$的父节点（追踪指针）。初始时如果$\text{y}$为$\text{nil}$，说明树为空，新节点$\text{z}$即作为树的根；否则，需根据节点键值大小关系插入对应位置。

### 删除

<image>

从树中删除某个节点$\text{Z}$时，需分三种情况处理：

- $\text{Z}$是叶节点：直接用空指针替换即可。（如图中(a)）
- $\text{Z}$仅有一个子节点：用$\text{Z}$的子节点替换$\text{Z}$。（如图中(b)、(c)）
- $\text{Z}$有两个子节点：用$\text{Z}$的中序遍历所得到的后继或前驱$\text{Y}$代替$\text{Z}$。此处以后继为例：
- 如果$\text{Y}$恰好是$\text{Z}$的右子节点：直接用$\text{Y}$取代$\text{Z}$，$\text{Y}$的右子树保持不变。（如图中(d)）
- 如果$\text{Y}$位于$\text{Z}$的右子树内部：先用$\text{Y}$的右子节点替换$\text{Y}$，再用$\text{Y}$替代$\text{Z}$。（如图中(e)）

以下伪代码实现删除操作：

1 BST-Delete(BST, z) 2 if z.left = NIL then 3 Shift-Nodes(BST, z, z.right) 4 else if z.right = NIL then 5 Shift-Nodes(BST, z, z.left) 6 else 7 y := BST-Successor(z) 8 if y.parent ≠ z then 9 Shift-Nodes(BST, y, y.right) 10 y.right := z.right 11 y.right.parent := y 12 end if 13 Shift-Nodes(BST, z, y) 14 y.left := z.left 15 y.left.parent := y 16 end if 1 Shift-Nodes(BST, u, v) 2 if u.parent = NIL then 3 BST.root := v 4 else if u = u.parent.left then 5 u.parent.left := v 5 else 6 u.parent.right := v 7 end if 8 if v ≠ NIL then 9 v.parent := u.parent 10 end if

$\text{BST-Delete}$过程根据上述3种情况处理节点删除：第1种情况（叶节点）对应第2—3行；第2种情况（单个子节点）对应第4—5行；第3种情况（有两个子节点）对应第6—16行。辅助函数$\text{Shift-Nodes}$用于把节点$\text{u}$替换成$\text{v}$。

若在第3种情况中，仅选用后继或前驱节点中的一种，则并未考虑到树的对称性，可能会导致性能问题。若要避免此问题，可以随机选择使用后继或前驱。

## 平衡树

普通的二叉搜索树中，若不加以平衡，插入或删除操作可能会导致树退化。若是使用随机键值构建二叉搜索树，那么平均高度仍能维持在对数级别（当节点数$n$足够大时，高度趋近于$2.99 \lg n$）；但在最好、最坏、平均情况下，高度会达到节点数$n$，查找性能退化至线性搜索的水平。要保持二叉搜索树的高效，关键在于通过“自平衡”机制，使树的高度始终维持在$O(\log n)$级别。

### 高度平衡树

若一棵树的任意节点，其左右子树高度之比都被某个常数所限制，就称其为高度平衡树。这一思想最早在AVL树中使用，后续的红黑树也沿用了类似机制。每次执行插入或删除操作后，需要沿着从根到修改节点的路径，检查并修正各节点的高度，以维持平衡。

### 加权平衡树

在加权平衡树中，平衡条件不再以高度衡量，而是以子树的叶节点数量为准。叶节点数量即代表权重，左右子树的权重差最多为常数$1$。但单纯依靠差值，难以在插入和删除时用$O(\log n)$的代价维护，因此引入比例因子$\alpha$，要求左右子树的权重各自至少占整棵子树权重的$\alpha$比例，由此形成$\alpha$-权重平衡树族。

### 其他类型

常见的自平衡二叉搜索树包括：T树、树堆、红黑树、B树、2-3树、伸展树。

## 应用

### 排序

二叉搜索树可用于树排序：先将所有元素插入二叉搜索树中，然后对树做中序遍历，即可得到有序序列。在快速排序的某些实现中，也可借助二叉搜索树来提高性能。

### 优先队列

二叉搜索树也可用来实现优先队列，借助节点的键值来表示优先级。插入操作与普通的二叉搜索树相同，但删除操作取决于优先队列的类型：

- 升序优先队列：移除最低优先级元素时，从根节点向左一路遍历即可找到最小键。
- 降序优先队列：移除最高优先级元素时，从根节点向右一路遍历即可找到最大键。

## 外部链接

- 哈尔沙·苏利亚纳拉亚纳的教学视频：pYT9F8_LFTM
- Ben Pfaff: An Introduction to Binary Search Trees and Balanced Trees. (PDF; 1675 kB) 2004.

## 基本资料

- 日语原文：二叉搜索树
- 类型：树
- 算法：1960年