平衡搜索树与有序查询
维护一组不断增删的键时，查询往往不止是“有没有 26”，还包括“比 26 小的最大键是什么”“列出 25 到 60 之间的键”。平衡搜索树同时保留键的顺序和较短的搜索路径，适合这类动态有序集合。若数据很少更新，可以先看二分查找；按工作负载选容器，见数据结构和搜索算法。
搜索树的顺序覆盖整棵子树
Open Data Structures 的二叉搜索树定义要求键来自一个全序：对任意节点，左子树的所有键都小于该节点的键，右子树的所有键都大于它。下面采用集合语义，重复插入同一个键不增加节点；若用树存映射，重复键可以更新其值。
只比较父子还不够：根为 40、左孩子为 20 时，20 的右孩子可以是 30，不能是 50。后者虽然大于 20，却仍在 40 的左子树里。按“左子树、节点、右子树”做中序遍历，便会得到递增的键序列。
最小堆只要求父节点的键不大于孩子的键。根为 10、左孩子为 70、右孩子为 20 就满足堆序；它没有搜索树那种左右分区，不能凭一次大小比较选定一条搜索路径。堆适合反复取最小值，搜索树则支持按键定位和有序查询。
沿一条路径查询，再按顺序输出
依次插入 40、20、60、10、30、50、70、55，得到：
L、R 分别表示左、右孩子。查找 55 时依次访问 40、60、50、55，共访问 4 个节点；走到空孩子仍未相等，就说明键不存在。插入 25 时访问 40、20、30，把新节点接在 30 的空左孩子位置。
有序查询在下降过程中保留一个候选答案：
前驱和下界都能在目标键不存在时给出答案；没有满足条件的键时返回 None。严格前驱会排除等于目标的键，下界则会包含它。数组中相应的边界语义见二分查找的下界。
范围查询要保留中序遍历的栈或父指针，连续走到下一个键。下面的递归实现用调用栈，并根据上下界剪枝。若输出 个键、树高为 ，单次定位为 ，范围查询为 ，辅助栈为 。在平衡树上，这就是 ；输出本身也要花 。若对每个结果都重新从根搜索，会多付重复定位的成本。
顺序插入为什么会变慢
按 Open Data Structures 的高度定义，高度数的是从根到最深真实节点的边数，单节点树的高度为 0。依次插入 1、2、3、4、5、6、7 时，每个新键都向右走，形成高度为 6 的链。查找 7 要访问 7 个节点。一般地， 个递增键会产生高度 ，末尾查找变成线性时间；建树时访问旧节点的总数是 。
搜索顺序正确，并不保证树高是对数级。平衡算法还需要一个约束形状的不变量，并在每次更新后恢复它。
旋转改变连接，保留键序
旋转的定义与指针操作见 Open Data Structures 第 7.2 节。右旋把左孩子提升为局部根，把旧根降为右孩子。图中 1 是旋转前，2 是旋转后：
中间子树 30 必须从 20 的右边接到 40 的左边。它的键介于 20 和 40 之间，所以两种接法都符合搜索顺序；中序序列始终是 10、20、30、40、60。一般形式也是如此：左侧子树的键小于 20，中间子树的键介于 20 和 40，右侧子树的键大于 40。左旋把这组操作反过来。
一次旋转只改常数个连接，成本为 。调用者必须把返回的新局部根接回父节点或整棵树的根；维护父指针、子树大小等字段的实现，还要同步更新这些字段。旋转能保持搜索顺序，至于怎样恢复平衡，要由具体不变量决定。
红黑树用颜色约束高度
红黑树能保证查找、插入、删除的最坏时间为 ，这里讨论非空树。第 9.2 节的红黑不变量给出了检查方法：
- 每个真实节点为红或黑，根为黑；空孩子视为黑色
NIL。 - 红节点的孩子必须为黑，不能连续出现两个红节点。
- 从任意节点到其后代
NIL的每条路径，黑节点数量相同。
为了算例计数，令 为根到 NIL 路径上真实黑节点的数量，包括根、不计 NIL。禁止相邻红节点使最长路径最多交替红黑；相同的黑节点数又要求所有分支具备相应深度。递归计数可得至少 个真实节点，而根到最深节点最多经过 个真实节点。因此，一个便于使用的高度界为：
这是上界，不要求左右子树节点数相等。书中的实现另外维护“左倾”条件：左孩子为黑时，右孩子也必须为黑；上面三个条件是这里检查的通用红黑约束。
插入时先按搜索顺序添加红色叶节点，保留各路径的黑节点数，再修复可能出现的红红相连，最后把根设为黑色。向空树插入第一个键时，也要把新根改黑；这会让所有路径的黑节点数同时增加 1。比如 30 为黑根、20 为其红色左孩子，再插入红色 10：20—10 违反约束。对 30 右旋，把 20 改黑、30 改红，就得到黑根 20 和两个红孩子 10、30。各条路径都有 1 个真实黑节点，高度从 2 降到 1。后面的代码执行这一个修复情形并检查结果。
删除两个孩子的节点
普通搜索树的删除规则分为三种：叶节点直接断开；只有一个孩子时让孩子接替它；有两个孩子时，用右子树的最小键，也就是严格后继，替换待删键，再删除后继原来的节点。
在前面的树里，插入 25 后删除 40：右子树中最小键是 50，所以把根的键换成 50。原来的 50 没有左孩子，但有右孩子 55；删除它时，必须把 60 的左孩子改为 55。最后的中序序列为 10、20、25、30、50、55、60、70，只少了 40。若存的是键值对，需要连同值一起替换；只换键会错配记录。
红黑树还要恢复颜色约束。若实际移除的是黑节点，某些路径会少一个黑节点；修复过程需要根据替代孩子和兄弟的颜色重新着色、旋转，必要时把缺失向根传递。判断依据是实际移除的后继节点的颜色，不能只看最初要删除的键所在节点。搜索顺序恢复与红黑平衡恢复是删除的两个步骤。
可运行的查询与删除
这段程序用整数键实现普通二叉搜索树的结构操作，重复插入不增加节点，删除不存在的键不改变集合。颜色字段留给下一段修复示例；这里的 insert、delete 不做红黑平衡。递归操作需要调用栈容纳整条路径；长链超过 Python 的递归深度限制时，会抛出 RecursionError。
from dataclasses import dataclass
@dataclass
class Node:
key: int
left: 'Node | None' = None
right: 'Node | None' = None
red: bool = False
def insert(t, x):
if t is None:
return Node(x)
if x < t.key:
t.left = insert(t.left, x)
elif x > t.key:
t.right = insert(t.right, x)
return t
def search(t, x):
path = []
while t is not None:
path.append(t.key)
if x == t.key:
return True, path
t = t.left if x < t.key else t.right
return False, path
def predecessor(t, x):
best = None
while t is not None:
if t.key < x:
best, t = t.key, t.right
else:
t = t.left
return best
def lower_bound(t, x):
best = None
while t is not None:
if t.key >= x:
best, t = t.key, t.left
else:
t = t.right
return best
def between(t, lo, hi):
if t is None:
return
if lo < t.key:
yield from between(t.left, lo, hi)
if lo <= t.key < hi:
yield t.key
if t.key < hi:
yield from between(t.right, lo, hi)
def delete(t, x):
if t is None:
return None
if x < t.key:
t.left = delete(t.left, x)
elif x > t.key:
t.right = delete(t.right, x)
else:
if t.left is None:
return t.right
if t.right is None:
return t.left
successor = t.right
while successor.left is not None:
successor = successor.left
t.key = successor.key
t.right = delete(t.right, successor.key)
return t
def height(t):
return -1 if t is None else 1 + max(height(t.left), height(t.right))
root = None
for x in [40, 20, 60, 10, 30, 50, 70, 55]:
root = insert(root, x)
print('search 55:', search(root, 55))
root = insert(root, 25)
print('predecessor 26:', predecessor(root, 26))
print('lower_bound 26:', lower_bound(root, 26))
print('range [25, 60):', list(between(root, 25, 60)))
root = delete(root, 40)
print('after delete 40:', list(between(root, 0, 100)))
print('replacement:', root.key, root.right.left.key)
chain = None
for x in range(1, 8):
chain = insert(chain, x)
print('sorted insertion:', height(chain), len(search(chain, 7)[1]))
输出：
search 55: (True, [40, 60, 50, 55])
predecessor 26: 25
lower_bound 26: 30
range [25, 60): [25, 30, 40, 50, 55]
after delete 40: [10, 20, 25, 30, 50, 55, 60, 70]
replacement: 50 55
sorted insertion: 6 7
继续在同一个 Python 文件末尾加入下面的代码。check_rb 检查整棵子树的搜索顺序、红红相连以及黑节点数量，返回从当前节点开始、不计 NIL 的黑节点数；根为黑由调用处单独检查。
def rotate_right(t):
pivot = t.left
assert pivot is not None
t.left = pivot.right
pivot.right = t
return pivot
def check_rb(t, lo=float('-inf'), hi=float('inf')):
if t is None:
return 0
assert lo < t.key < hi
if t.red:
assert t.left is None or not t.left.red
assert t.right is None or not t.right.red
left = check_rb(t.left, lo, t.key)
right = check_rb(t.right, t.key, hi)
assert left == right
return left + int(not t.red)
rb = Node(30, Node(20, Node(10, red=True), red=True))
before = list(between(rb, 0, 100))
try:
check_rb(rb)
except AssertionError:
print('before: invariant fails')
rb = rotate_right(rb)
rb.red = False
rb.right.red = True
assert not rb.red
black_count = check_rb(rb)
assert list(between(rb, 0, 100)) == before
print('after:', rb.key, rb.left.key, rb.right.key)
print('order:', before)
print('height / black count:', height(rb), black_count)
追加部分的输出：
before: invariant fails
after: 20 10 30
order: [10, 20, 30]
height / black count: 1 1
树、排序数组与哈希表如何选
Python bisect 文档指出，定位插入位置为对数时间，实际插入列表仍为线性时间。链式哈希表的分析则把查找和删除的期望成本与扩容的摊还成本分开。下面令 为键数、 为范围结果数、 为哈希表的桶数；比较、哈希和移动一个元素按常数成本计，范围端点满足 。扩容的摊还界针对从空表开始、按倍数扩容的更新序列。
哈希表的期望界依赖合适的哈希方案和受控的装载率；一次扩容仍可能花 。扫描要经过所有桶，包括空桶；当桶数与当前键数同阶时，才可简写为 。只扩容、不缩容的表在大量删除后可能保留远多于键数的桶。树的界统计比较和连接操作，昂贵的字符串比较也要单独计入。数组的移动与局部性见数组与动态数组。
只做频繁的精确查找时，哈希表通常合适；批量排好序、很少更新时，排序数组能直接做边界和范围查询；需要持续增删，又要前驱、下界或有序范围时，平衡搜索树把这些操作放在同一个表示里。