2019/11/21

B树，又称多路平衡查找树，B树中所有结点的孩子结点数的最大值称为B树的阶。

　　一颗m阶B树或是空树，或是满足如下特性的m叉树：

---

 

　　1）树中每个结点至多有m棵子树、m-1个关键字。

　　2）若根节点不是终端节点（非叶子节点），则至少有两棵子树、1个关键字（由  1）得到：2阶-1=1个关键字）。

　　3）除根节点外的所有非叶结点（除去第一行和最后一行元素），

　　至少有${\left \lceil m/2 \right \rceil}$棵子树、${\left \lceil m/2 \right \rceil}$-1个关键字。

　　

　　给出阶数m和关键字n→求树的最大高度和最小高度，背住以下公式，很快求出：

　　$\log _{m}(n+1)\leqslant \log_{\left \lceil m/2 \right \rceil}(\frac{n+1}{2})+1$

　　

注：背住以上三条性质+最后一条公式，答题无惑矣