树形查找

基于BST的查找

BST, AVL, 红黑树定义

使用BST、AVL或红黑树来存储数据，查询方式如下：

1. 从根节点开始。
2. 如果查询的值等于当前节点的值，返回当前节点。
3. 如果查询的值小于当前节点的值，向左子树查询。
4. 如果查询的值大于当前节点的值，向右子树查询。
5. 如果到达空节点，则查询失败，返回NULL。

对于BST，如果树是极度不平衡的（例如，成为链状结构），查询的最坏时间复杂度为 O(n)。

B树

定义

B树，也叫做多路平衡查找树，B树中所有结点的孩子个数的最大值称为B树的阶，通常用 $m$ 表示。一颗 $m$ 阶B树，满足如下特性：

• 树中每个结点最多有 $m$ 棵子树，最多有 $m-1$ 个关键字。
• 若根节点不是叶子结点，至少有两个子树
• 除了根节点外的所有非叶结点最少有 $\lceil m / 2 \rceil$ 棵子树，即最少有 $\lceil m/2 \rceil - 1$ 个关键字。

结点结构如下：

其中

• $n$ 为结点中关键字的个数
• $K_i (i = 1,2,\cdots,n)$ 为接点中存储的关键字，且满足 $K_1 \lt K_2 \lt \cdots \lt K_n$
• $P_i (i = 0,1,\cdots,n)$ 为指向子树根结点的指针，且指针 $P_{i-1}$ 所指子树中所有结点的关键字均小于 $K_i$，$P_i$ 所指子树中所有结点的关键字均大于 $K_i$

以上图中的5阶B树为例，说明B树的性质：

• 结点中的孩子个数等于结点中关键字的个数加1。
• 除根节点外所有非叶子结点最少有 $\lceil m / 2 \rceil = \lceil 5 / 2 \rceil = 3$ 棵子树（2个关键字），最多有5颗子树（4个关键字）。
• 结点中关键字从左到右递增有序，关键字左侧指针所指子树的所有关键字均小于该关键字，右侧正直镇所指子树的所有关键字均大于该关键字。

查找

B树查找与普通二叉查找树相似，但在每个节点上，需要进行多次比较。

1. 从根节点开始。
2. 在当前节点中，从左到右搜索一个关键字 $k$ ，直到找到一个关键字 $x$ 满足 $k \le x$ 或者已检查完所有关键字。
3. 如果找到的关键字 $x$ 等于 $k$ ，则查找成功并返回该节点。
4. 如果没找到关键字 $x$ 或者 $x$ 不等于 $k$ ，则根据 $x$ 的位置，进入对应的子节点继续查找。
5. 重复上述步骤，直到找到关键字或达到叶子节点。

插入

1. 查找关键字位置：首先在 $B$ 树中查找要插入的关键字位置，但停在最后的叶子节点上，而不是回退。
2. 插入关键字：在找到的叶子节点中插入新关键字。
3. 节点分裂：如果该叶子节点关键字数超过了最大值（通常表示为 $2t-1$ ，其中 $t$ 是树的最小度数），则需要分裂该节点： $- $ 把节点分成两部分。 $- $ 上升中间的关键字到父节点。 $- $ 分裂后的两部分成为新的子节点。
4. 递归分裂：如果因为上升的关键字导致父节点也超过了最大关键字数，那么继续递归分裂。
5. 新的根节点：如果根节点分裂，则其中间关键字上升为新的根节点。

删除

删除操作较为复杂，需要考虑多种情况。

1. 查找关键字：首先查找要删除的关键字 $k$ 。
2. 叶子节点中的关键字：如果关键字 $k$ 在叶子节点中，直接删除。
3. 内部节点中的关键字： $- $ 如果 $k$ 的前驱关键字在叶子节点中，找到 $k$ 的前驱关键字，删除它，并在内部节点中用它替换 $k$ 。 $- $ 否则，使用类似的方法与 $k$ 的后继关键字。 $- $ 如果都不行，必须合并节点并递归地删除 $k$ 。
4. 合并节点：如果一个节点在删除后少于 $t-1$ 个关键字，那么它就太小了，需要进行合并或关键字借用操作： $- $ 从兄弟节点借用一个关键字。 $- $ 如果无法借用，就和兄弟节点合并。
5. 递归删除：合并操作可能需要递归到树的上一层。
6. 更新根节点：如果根节点没有关键字，且只有一个子节点，那么那个子节点成为新的根节点。

B+树

B+树是B树的一种扩展。

一颗m阶B+树满足如下条件：

• 每个分支结点最多有m颗子树
• 结点的子树个数和关键字个数相同
• 所有的值都出现在叶子节点，内部节点只包含键不包含实际的数据。
• 叶子节点通过指针相互连接，这为范围查询提供了高效性。
• 由于内部节点不存储数据，因此每个内部节点可以存储更多的键，从而增加树的扇出，减少树的高度。