二叉搜索树

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

二叉搜索树
类型	树
发明时间	1960年
发明者	P.F.温德利、安德鲁·唐纳德·布思、安德鲁·科林、托马斯·N·希巴德
用大O符号表示的时间复杂度 算法 平均 最差 搜索 O(log n) O(n) 插入 O(log n) O(n) 删除 O(log n) O(n) 寻找最小值 O(log n) O(n) 删除最小值 O(log n) O(n) 用大O符号表示的空间复杂度 空间 O(n) O(n)

“binary search tree”的各地常用译名
中国大陆	二叉搜索树[1]:163、二叉查找树[2]:250
港澳	二叉搜寻树[3]
台湾	二元搜寻树[4]:6-11

一棵二叉搜索树，其节点数为9，高度为3，根节点为8

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

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

历史

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

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

性质

二叉搜索树为有根的二叉树，其节点顺序为严格全序关系，每个节点都满足：左子树上所有节点的键值都小于该节点，右子树上所有节点的键值都大于该节点。这一结构保证可以在对数时间内定位任意键值。^{[15]:298[16]:287[1]:161-162}除查找外，其也常用于排序，但性能取决于节点的插入和删除顺序——在最坏情况（英语：Best, worst and average case）下，连续操作可能使树退化为类似单链表的结构，这时的查找复杂度与链表相同。^{[15]:299-302[17]}

遍历

主条目：树的遍历

参见：线索二叉树

二叉搜索树的遍历有三种基本方法：前序、中序、后序。^{[16]:287[1]:162}

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

以下是递归实现的遍历伪代码：^{[16]:287–289[1]:162}

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

操作

搜索

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

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

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

重复上述步骤，直到找到该键，或者剩余子树为空。若到达空子树仍未找到，说明该键不存在于树中。^{[16]:290-291[1]:163}

递归搜索

以下伪代码展示递归方式实现的查找过程：^{[16]:290[1]:163}

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

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

迭代搜索

递归过程也可展开为循环形式，一般情况下循环版本的效率更高。其伪代码如下：^{[16]:291[1]:163}

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

由于查找可能会一直到叶节点，因此时间复杂度为树的高度${\displaystyle O(h)}$（${\displaystyle h}$为树的高度）。^{[16]:290[1]:163}在最坏情况下，一棵严重不平衡的二叉搜索树可能退化成单链表，这时复杂度会达到${\displaystyle O(n)}$（${\displaystyle n}$为树中节点总数）。但对于高度平衡的二叉搜索树而言，复杂度为${\displaystyle O(\log n)}$。^{[10]:458–459[18]:403[2]:255}

后继与前驱

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

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

寻找树中键值最大或最小的节点，是寻找后继与前驱过程中的重要环节。其伪代码如下：^{[16]:291–292[1]:163–164}

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

选择与排名

若在节点中维护以之为根节点的子树的节点总数，则可实现选择与排名操作。选择操作用于在树中直接定位排名为${\displaystyle k}$的节点，即第${\displaystyle k}$小的键。^{[18]:406–407[2]:257–258}排名操作则与之相对，给定指定键后，其会返回小于该键的节点数。^{[18]:408[2]:258–259}这两种操作的伪代码如下：^{[18]:409[2]:258–259}

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 Rank(key, x.left) else if cmp > 0 then return 1 + size(x.left) + Rank(key, x.right) else return size(x.left) end if

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

范围查找

利用中序遍历，可以实现范围查找（英语：Range query (computer science)），即查询两个给定值之间的元素数量。其伪代码如下：^{[18]:412–413[2]:261–262}

Range-Query(x, lo, hi, list) if x = NIL then return end if if lo < x.key then Range-Query(x.left, lo, hi, list) end if if lo ≤ x.key ≤ hi then list.append(x.key) end if if hi > x.key then Range-Query(x.right, lo, hi, list) end if

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

插入

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

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

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

删除

二叉搜索树删除节点的过程

从树中删除某个节点${\displaystyle {\text{Z}}}$时，需分三种情况处理：^{[16]:295-297[1]:166-167}

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

以下伪代码实现删除操作：^{[16]:296-298[1]:167-168}

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

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

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

平衡树

主条目：平衡树

普通的二叉搜索树中，若不加以平衡，插入或删除操作可能会导致树退化。^[21]若是使用随机键值构建二叉搜索树，那么平均高度仍能维持在对数级别（当节点数${\displaystyle n}$足够大时，高度趋近于${\displaystyle 2.99\lg n}$）；^{[18]:413[2]:263}但在最坏情况（英语：Best, worst and average case）下，高度会达到节点数${\displaystyle n}$，查找性能退化至线性搜索的水平。^[21]要保持二叉搜索树的高效，关键在于通过“自平衡”机制，使树的高度始终维持在${\displaystyle O(\log n)}$级别。^{[10]:458–459[22]:50[18]:414[2]:263}

高度平衡树

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

加权平衡树

主条目：加权平衡树

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

其他类型

常见的自平衡二叉搜索树包括：T树（英语：T-tree）^[24]、树堆^[25]、红黑树^{[16]:273[1]:174}、B树^[26]、2-3树^[10]:483、伸展树^[27]。

应用

排序

主条目：树排序（英语：Tree sort）

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

优先队列

主条目：优先队列

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

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

参见

• 搜索树
• 最优二叉搜索树
• 二叉搜索树的几何性质（英语：Geometry of binary search trees）
• 三叉搜索树

脚注