Search Trees, AVL, B-Tree, B+Tree
查找树用结构约束换取更快查找。
| 结构 | 约束 | 目标 |
|---|---|---|
| BST | 左小右大 | 平均 \(O(\log n)\) 查找 |
| Indexed BST | 每个结点记录左子树规模 | 支持第 \(k\) 小查询 |
| AVL | 左右子树高度差不超过 1 | 保证高度 \(O(\log n)\) |
| m-way search tree | 每个结点保存多个 key | 降低树高 |
| B-tree | 平衡的多路搜索树 | 降低磁盘 I/O |
| B+ tree | 数据全在叶子，叶子有序链接 | 范围查询和数据库索引 |
leftSize 思想二叉搜索树可以为空。
非空二叉搜索树满足：
中序遍历 BST 会得到递增序列。
每一步只进入一个子树，因此时间复杂度是：
\[ O(h) \]
其中 \(h\) 是树高。
template <class Key>
Node<Key>* findMin(Node<Key>* root) {
if (root == nullptr) return nullptr;
while (root->left != nullptr) {
root = root->left;
}
return root;
}
template <class Key>
Node<Key>* findMax(Node<Key>* root) {
if (root == nullptr) return nullptr;
while (root->right != nullptr) {
root = root->right;
}
return root;
}最小值一路向左，最大值一路向右。
重复 key 可以选择忽略、计数或放入重复链表，必须在接口中明确。
| 情况 | 处理 |
|---|---|
| 删除叶结点 | 直接删除 |
| 只有一个非空子树 | 用非空子树替代该结点 |
| 有两个非空子树 | 用左子树最大值或右子树最小值替代，再删除替代结点 |
删除后必须保持中序递增。
template <class Key>
Node<Key>* remove(Node<Key>* root, const Key& x) {
if (root == nullptr) return nullptr;
if (x < root->key) {
root->left = remove(root->left, x);
} else if (root->key < x) {
root->right = remove(root->right, x);
} else if (root->left != nullptr && root->right != nullptr) {
Node<Key>* successor = findMin(root->right);
root->key = successor->key;
root->right = remove(root->right, successor->key);
} else {
Node<Key>* old = root;
root = (root->left != nullptr) ? root->left : root->right;
delete old;
}
return root;
}若按递增顺序插入：
\[ 1,2,3,\ldots,n \]
BST 会退化成链表。
查找、插入、删除从期望的 \(O(\log n)\) 退化为 \(O(n)\)。
平衡树的目标是控制高度。
Indexed BST 在每个结点增加 leftSize：
\[ leftSize = |leftSubtree| + 1 \]
用途：
每一步进入一个子树，复杂度为 \(O(h)\)。
AVL 树是二叉搜索树，并且对任意结点：
\[ |height(left)-height(right)|\le 1 \]
平衡因子常定义为：
\[ bf(x)=height(right)-height(left) \]
因此合法值是 \(-1,0,1\)。
插入后只需要在最小失衡子树处旋转一次。
| 类型 | 插入位置 | 调整 |
|---|---|---|
| LL | 左子树的左侧 | 右单旋 |
| RR | 右子树的右侧 | 左单旋 |
| LR | 左子树的右侧 | 先左旋左孩子，再右旋根 |
| RL | 右子树的左侧 | 先右旋右孩子，再左旋根 |
旋转必须同时保持 BST 的中序顺序不变。
左单旋是对称操作。
LR 和 RL 失衡需要双旋，因为中间子树必须先被转到外侧。
设 \(N_h\) 是高度为 \(h\) 的 AVL 树最少结点数。
最坏形态的一侧高度为 \(h-1\)，另一侧高度为 \(h-2\)：
\[ N_h=N_{h-1}+N_{h-2}+1 \]
这与 Fibonacci 数同阶，因此：
\[ h=O(\log n) \]
AVL 的查找、插入、删除最坏都是 \(O(\log n)\)。
m 路搜索树的每个内部结点最多有 \(m\) 个孩子，最多有 \(m-1\) 个 key。
若某结点有 key：
\[ k_1<k_2<\cdots<k_p \]
则孩子区间为：
结点内用顺序或二分查找定位区间。
一棵阶为 \(m\) 的 B-tree 是平衡 m 路搜索树，满足：
查找过程：
B-tree 的高度很小，适合磁盘或 SSD 页式访问。
插入总是先定位到叶子。
若叶子未满：
若叶子已满：
若 key 在叶结点：
若 key 在内部结点：
删除可能一路向上合并，根可能变矮。
B+ tree 与 B-tree 不同。
B+ tree 满足：
| 维度 | B-tree | B+ tree |
|---|---|---|
| 数据记录位置 | 内部结点和叶子都可存 | 只在叶子 |
| 查找是否可能在内部结点结束 | 可以 | 不可以 |
| 叶子链表 | 不是定义要求 | 是核心特征 |
| 范围查询 | 需要中序遍历式访问 | 叶子链表顺序扫描 |
| 数据库索引 | 可用 | 更常用 |
数据库索引关注：
B+ tree 内部结点只放 key 和孩子指针，同一页能放更多分支，树更矮。
叶子链表让范围查询只需定位起点后顺序向后扫。
| 结构 | 查找 | 插入 | 删除 | 空间/工程特征 |
|---|---|---|---|---|
| BST | \(O(h)\) | \(O(h)\) | \(O(h)\) | 简单但可能退化 |
| Indexed BST | \(O(h)\) | \(O(h)\) | \(O(h)\) | 支持排名和选择 |
| AVL | \(O(\log n)\) | \(O(\log n)\) | \(O(\log n)\) | 旋转维护高度 |
| m-way Tree | \(O(h\cdot m)\) 或 \(O(h\log m)\) | 依实现 | 依实现 | 降低高度 |
| B-tree | \(O(\log_m n)\) 页访问 | 分裂 | 借/合并 | 外存友好 |
| B+ tree | \(O(\log_m n)\) 页访问 | 分裂 | 借/合并 | 范围查询强 |
依次插入：
\[ 3,1,4,6,9,2,5,7 \]
得到：
template <class Key>
bool isBST(Node<Key>* node, const Key* low, const Key* high) {
if (node == nullptr) return true;
if (low != nullptr && !( *low < node->key )) return false;
if (high != nullptr && !( node->key < *high )) return false;
return isBST(node->left, low, &node->key) &&
isBST(node->right, &node->key, high);
}每个结点携带合法区间，避免只比较父子导致的错误。
在有序集 \(S\) 的 BST 中，任意根到叶路径把 \(S\) 分为：
不一定对任意 \(a\in S_1,b\in S_2,c\in S_3\) 都有 \(a\le b\le c\)。
原因：路径上不同祖先产生的左右区间不同，不能把所有左侧结点和所有右侧结点分别合并成全局小于/大于路径的集合。
设 \(N_h\) 是高度为 \(h\) 的 AVL 树最少结点数：
\[ N_{-1}=0,\quad N_0=1 \]
\[ N_h=N_{h-1}+N_{h-2}+1 \]
因此 \(N_h\) 与 Fibonacci 数同阶。
对于 \(n\) 个结点的 AVL 树：
\[ h=O(\log n) \]
题目：内部结点只存索引、所有数据都在叶子、叶子按 key 链接，这是什么树？
答案：B+ tree。
B-tree 不要求所有数据都在叶子，也不要求叶子之间有顺序链表。