能不能变成m叉查找树？

与二叉查找树的做法一致，就是在 ( − ∞ , + ∞ ) (-\infty,+\infty) (−∞,+∞)初始范围内加断点，将其分为多个区间。如上图5叉查找树：

Notes:

现在考虑这样一个问题，如果5叉查找树中每个结点只保存一个关键字（如下图所示），那么这样一棵树相等于一颗二叉查找树，此时两者有什么不同？

若每个结点内关键字太少，导致树变高，要查更多层结点，效率低。为了解决这个问题，我们可以提出一个策略：m叉查找树中，规定除了根结点外，任何结点至少有 ⌈ m 2 ⌉ \lceil\frac{m}{2} \rceil ⌈2m​⌉个分叉，即至少含有 ⌈ m 2 ⌉ − 1 \lceil\frac{m}{2} \rceil -1 ⌈2m​⌉−1个关键字。

例如：对于一个5叉排序树，规定除了根结点外，任何结点都至少有3个分叉，2个关键字。

那么为什么规定除了根结点以外呢？

原因：如果整个树只有1个元素，根结点只有两个分叉。

如下图所示，这样一颗满足上述要求的5叉查找树是否优秀呢？

不够‘平衡’，树会很高，要查很多层结点。为了解决这样一个问题，我们添加一个策略：

那么，满足了之前提出的两个策略的树即为B树。上图为一个五阶B树。

B树,又称多路平衡查找树,B树中所有结点的孩子个数的最大值称为B树的阶,通常用m表示一棵m阶B树或为空树,或为满足如下特性的m叉树:

1)树中每个结点至多有m棵子树,即至多含有m-1个关键字。

2)若根结点不是终端结点,则至少有两棵子树。（要保证每个结点的绝对平衡）

3)除根结点外的所有非叶结点至少有 ⌈ m 2 ⌉ \lceil\frac{m}{2} \rceil ⌈2m​⌉棵子树,即至少含有 ⌈ m 2 ⌉ − 1 \lceil\frac{m}{2} \rceil-1 ⌈2m​⌉−1个关键字。

4）所有非叶结点的结构如下： 其中， K i   ( i = 1 , 2 , . . . , n ) K_i~(i = 1,2,...,n) Ki​ (i=1,2,...,n)为结点的关键字，且满足KaTeX parse error: Double subscript at position 7: K_1