2-3树，2-3-4树，B树 - sdk社区

2-3树是一种多路查找树

2和3的意思就是2-3树包含两种结点

2结点包含一个元素和两个孩子(或者没有孩子)。

① 左子树包含结点的元素值小于该结点的元素值，右子树包含的结点的元素值大于该结点的元素值

② 2结点要不有两个孩子，要不就没有孩子，不允许有一一个孩子
3结点包含一大一小两个元素和三个孩子(或者没有孩子)。(两个元素按大小顺序排列好)

①左子树包含的结点的元素值小于该结点较小的元素值，右子树包含的结点的元素值大于该结点较大
的元素值，中间子树包含的结点的元素值介于这两个元素值之间。

②3结点要不有三个孩子，要不就没有孩子，不允许有一个或两个孩子
2 -3树所有叶子结点都在同一层次

2-3-4树

2结点包含一个元素和两个孩子(或者没有孩子)。

① 左子树包含结点的元素值小于该结点的元素值，右子树包含的结点的元素值大于该结点的元素值

② 2结点要不有两个孩子，要不就没有孩子，不允许有一一个孩子
3结点包含一大一小两个元素和三个孩子(或者没有孩子)。(两个元素按大小顺序排列好)

①左子树包含的结点的元素值小于该结点较小的元素值，右子树包含的结点的元素值大于该结点较大
的元素值，中间子树包含的结点的元素值介于这两个元素值之间。

②3结点要不有三个孩子，要不就没有孩子，不允许有一个或两个孩子
2 -3-4 树所有叶子结点都在同一层次
4结点包含小中大三个元素和四个孩子(或者没有孩子)。

①最左子树包含的结点的元素值小于该结点最小的元素值，第二个子树包含的结点的元素值大于
最小的元素值小于中间元素值，第三个子树包含的结点的元素值大于中间元素值小于最大元素值，
最右子树包含的结点的元素值大于该结点最大的元素值。

②4结点要不有四个孩子，要不就没有孩子，不允许有一个或两个或三个孩子

B树

B树也是一种平衡的多路查找树，2-3树和2-3-4树都是B树的特例，我们把树中结点最大的孩子数目称
为B树的阶。通常记为m。

一棵m阶B树或为空树，或为满足如下特性的m叉树:

树中每个结点至多有m棵子树。(即至多含有m-1个关键字) (“两棵子树指针夹着一个关键字”)
若根结点不是终端结点，则至少有两棵子树。(至少一个关键字)
除根结点外的所有非叶结点至少有 $encoding="application/x-tex">\lceil m/2 \rceil</annotation></semantics></math>$ 棵子树。(即至少含有 $encoding="application/x-tex">\lceil m/2 \rceil-1</annotation></semantics></math>$ 个关键字)。判断是否需要分裂

所有非叶结点的结构如下：

n	P $encoding="application/x-tex">_0</annotation></semantics></math>$	K $encoding="application/x-tex">_1</annotation></semantics></math>$	P $encoding="application/x-tex">_1</annotation></semantics></math>$	K $encoding="application/x-tex">_2</annotation></semantics></math>$	……	K $encoding="application/x-tex">_n</annotation></semantics></math>$	P $encoding="application/x-tex">_n</annotation></semantics></math>$

其中K $encoding="application/x-tex">_i</annotation></semantics></math>$ (i=1,2,……,n)为结点的关键字，且满足K $encoding="application/x-tex">_1</annotation></semantics></math>$ <K $encoding="application/x-tex">_2</annotation></semantics></math>$ <K $encoding="application/x-tex">_3</annotation></semantics></math>$ <……K $encoding="application/x-tex">_n</annotation></semantics></math>$

其中P $encoding="application/x-tex">_i</annotation></semantics></math>$ (i=0,1,2,……,n)为指向子树根节点的指针，且指针P $encoding="application/x-tex">_{i-1}</annotation></semantics></math>$ 所指的子树的所有节点的关键字都小于K $encoding="application/x-tex">_i</annotation></semantics></math>$ ，P $encoding="application/x-tex">_{i}</annotation></semantics></math>$ 所指向子树的所有结点的关键字都小于K $encoding="application/x-tex">_{i+1}</annotation></semantics></math>$ ，n是结点中关键字的个数

所有的叶子结点出现在同一层次上，不带信息。(就像是折半查找判断树中查找失败的结点)

1.B树的查找操作

B树是多路查找树，二叉排序树是二路查找，B树是多路查找，所以它是二叉排序树的拓展。因此，B树的查找
操作和二叉排序树的查找操作非常类似。
查找过程:①先让待查找关键字key和结点的中的关键字比较，如果等于其中某个关键字，则查找成功。
②如果和所有关键字都不相等，则看key处在哪个范围内，然后去对应的指针所指向的子树中查找。
Eg:如果Key比第一个关键字K1还小，则去P0指针所指向的子树中查找，如果比最后一一个关键字Kn,还
大，则去Pn指针所指向的子树中查`找。

2.B树的插入操作

在二叉排序树中，仅需查找到需插入的终端结点的位置。但是，在B树中找到插入的位置后，并不能
简单地将其添加到终端结点位置，因为此时可能会导致整棵树不再满足B树中定义中的要求。
给定一-组关键字(20，30, 50， 52， 60, 68， 70}，给出创建一棵3阶B树的过程。

3.B树的删除操作

B树中的删除操作与插入操作类似，但要稍微复杂些，要使得删除后的结点中的关键字个数≥[m/21-1，因此
将涉及结点的“合并" 问题。由于删除的关键字位置不同，可以分为关键字在终端结点和不在终端结点上两
种情况。