注：本文同步发布于稀土掘金。
7 多路查找树
多路查找树（multi-way search tree），其每个结点的孩子可以多于两个，且每一个结点处可以存储多个元素。由于它是查找树，所有元素之间存在某种特定的排序关系。
7.1 2-3树
7.1.1 生成2-3树
2-3树是这样的一棵多路查找树：其中的每一个结点都有两个孩子（我们称它为2结点）或三个孩子（我们称它为3结点）。
一个2结点包含一个元素和两个孩子（或没有孩子），且与二叉排序树类似，左子树包含的元素小于该元素，右子树包含的元素大于该元素。不过，与二叉排序树不同，这个2结点要么没有孩子，要么就有两个，不能只有一个孩子。
一个3结点包含一小一大两个元素和三个孩子（或没有孩子），一个3结点要么没有孩子，要有就有3个孩子，如果某个3结点有孩子的话，左子树包含小于较小元素的元素，右子树包含大于较大元素的元素，中间子树包含介于两元素之间的元素。
总之，2-3树有以下特性：
(1) 对于每一个结点有1或者2个元素；
(2) 当节点有1个元素时，节点有0个子树或2个子树；
(3) 当节点有2个元素时，节点有0个子树或3个子树。
(4) 所有叶子点都在树的同一层；
如下是一棵有效的2-3树：
来看2-3树的生成，假设我们要根据以下数组生成一棵2-3树：
由于2-3树的每个结点可以放置1至2个元素，因此我们使用如下结构来表示一个结点，其中x和y分别表示元素值：
然后我们来按序插入元素，由于一个结点可以存放2个元素，因此前两个元素，直接生成一个根结点：
对于第三个元素12，因为当前2-3树只有一个结点，因此只需要将元素12插入该结点即可，而由于该结点已有二个元素，因此不能直接插入，而是需要将其中一个元素顶上去作为父结点，我们把被插入的结点设为node，待插入的元素则构建一个只有一个元素的结点，如下所示：
然后 将 n e w N o d e 中的元素先插入到 n o d e 中，如果 n e w N o d e 有孩子结点，也将之作为 n o d e 的孩子 \color{red}{将newNode中的元素先插入到node中，如果newNode有孩子结点，也将之作为node的孩子} 将newNode中的元素先插入到node中，如果newNode有孩子结点，也将之作为node的孩子：
这时，根据node元素数量进行不同处理——如果node结点数量小于3个，则不进行任何处理，否则将所有元素按最大结点数量分成多段，然后从第一段开始，将每段的最后一个元素往上提，作为父结点：
然后插入元素1，直接插入即可：
接下来插入元素13：
然后是元素9，先将它插入到12、13所在的结点，然后构建子树，然后将被顶上去的元素12，插入到结点8：
为方便后续描述，我们把要插入的结点设置为newNode，被插入的结点设置为node。
然后插入元素10：
然后插入元素15：
然后插入元素6，首先插入到1、4所在的结点，并生成子树：
然后把新生成的子树当成新的newNode，把原来1、4所在的结点的父结点，当成新的node，进行处理：
这时，发现根结点有三个元素，按照规则“如果node结点数量小于3个，则不进行任何处理，否则将所有元素按最大结点数量分成多段，然后从第一段开始，将每段的最后一个元素往上提，作为父结点”进行处理，并加入新的规则“然后将所有孩子结点按每个被拆分的元素个数+1，分配到新生成的子结点上”：
如上图所示，孩子结点有四个，由于第一个新的子结点只有一个元素，因此分配两个孩子给它，另一个新子结点也只有一个元素，因此也分配两个孩子给它。
然后插入元素7：
然后插入元素14：
然后插入元素3：
然后插入元素5：
然后插入元素11，参考上述规则，得到如下结果：
然后插入元素2，参考上述规则，得到如下结果：
此时2-3树创建完成。
7.1.2 删除2-3树上的结点
为保证2-3树的特性，在2-3树上删除元素，有以下规则：
(1) 若删除的是叶子结点上的元素，且叶子结点的元素个数大于1，则直接将该元素删除；
(2) 若删除的是叶子结点上的元素，且叶子结点的元素个数等于1，则先将此结点删除，然后从parent开始按规则”将parent的所有子结点的元素添加到parent中，将parent的所有子结点的孩子也添加到parent中，然后根据parent重新构建子树“向上迭代，直到parent的元素个数大于最大孩子数量，或者parent为null时，停止迭代；
(3) 若删除的是非叶子结点上的元素，则找到该元素的下标，然后找到该下标对应的孩子树上的最大值，将孩子树上的最大值与要删除的这个元素替换，然后根据(1)、(2)相同的规则，删除新的这个叶子结点上的元素；
我们通过示例来看，假设有以下2-3树：
假设我们要删除元素1，由于要删除的是叶子结点上的元素，且该结点只有一个元素，按照上述规则，我们先删除元素1所在的结点：
然后找到parent结点，即元素为2的结点，将其所有孩子的元素和孩子的所有孩子加到parent结点上，并删除原来的孩子结点：
发现parent的元素个数仍小于最大孩子数量（2-3树的最大孩子数量是3个），因此找到parent的parent，继续按规则处理：
新结点的元素数量仍小于3，于是继续往上迭代，直到迭代到根结点，元素的数量也不超过3，这时停止迭代，树已经变成一棵正常的2-3树，操作结束：
接下来我们来删除元素20，首先，找到20所在的结点，发现它只有一个元素，因此找到此结点的第一棵树上的最大元素，将之与20替换：
然后删除替换后的结点上的元素，由于替换后的结点也只有一个元素，因此按照规则，一层层往上迭代：
迭代到根结点时，发现根结点的元素数量超过了3，于是重新生成树，规则与插入时重新生成树的方法一致——将所有结点合到一起，然后按最大结点数分成多段，然后把每一段的最大元素往上提作为父结点的元素，最后把所有孩子按新生成的结点的元素数量进行分配。
以本例为例，parent有5个元素，而每个结点最大的元素数量是2，因此将它们分成“8、12”、“16、24”和“28”三段，然后将前面两段的最大值往上提作为父结点，即得到如下结构：
然后将6个孩子结点，根据新孩子的元素数量进行分配：
而如果要删除元素18，由于它是叶子结点上的元素，且该结点有两个元素，因此直接删除即可：
我们来删除元素12，发现它不是叶子结点上的元素，且其在该结点上的索引为0，因此我们找到children[0]子树上的最大元素，即11，并将这两个元素替换：
然后删除当前元素12所在的结点，并按照规则向上迭代：
其他元素的删除，则不再演示，按规则处理即可。
7.2 2-3-4树
7.2.1 生成2-3-4树
2-3-4树是2-3树的扩展，因此2-3-4树有以下特性：
(1) 对于每一个结点有1或者2或者3个元素；
(2) 当节点有1个元素时，节点有0个子树或2个子树；
(3) 当节点有2个元素时，节点有0个子树或3个子树。
(4) 当节点有3个元素时，节点有0个子树或4个子树。
(4) 所有叶子点都在树的同一层；
我们同样用以下数组来构建2-3-4树：
对于前三个元素，因为一个结点最多可以放置三个元素，因此直接将它们依序放置到一个结点即可：
对于第四个元素1，因为当前2-3-4树只有一个结点，因此只需要将元素1插入该结点即可，而由于该结点已有三个元素，因此不能直接插入，而是需要将其中一个元素顶上去作为父结点，我们把被插入的结点设为node，待插入的元素则构建一个只有一个元素的结点，如下所示：
然后 将 n e w N o d e 中的元素先插入到 n o d e 中，如果 n e w N o d e 有孩子结点，也将之作为 n o d e 的孩子 \color{red}{将newNode中的元素先插入到node中，如果newNode有孩子结点，也将之作为node的孩子} 将newNode中的元素先插入到node中，如果newNode有孩子结点，也将之作为node的孩子：
这时，根据node元素数量进行不同处理——如果node结点数量小于4个，则不进行任何处理，否则将所有元素按每组3个，分成多组，处理方式与2-3树的插入一致：
插入元素13，根据上述规则，直接插入到12所在的结点即可：
接下来插入元素9：
接下来插入元素10，首先将元素10与元素9、12、13所在的结点，生成一棵新的子树：
接下来处理新的子树的原子树，即以下两棵子树：
我们先将原子树上，9、12、13元素所在的结点从树上去除：
然后仍按上述规则，设置node和newNode，然后把newNode的元素加入node，并把newNode的所有孩子都加入node的孩子，因新的根结点8、12的元素数量小于3，因此插入结束：
接下来插入元素15，直接插入即可：
接下来插入元素6，仍是直接插入：
接下来插入元素7，先处理元素7和元素1、4、6所在的结点，生成一棵新子树：
然后将原树中的1、4、6所在的结点删除，生成新子树，并将两棵子树合并处理：
接下来插入元素14，直接插入即可：
接下来插入元素3，直接插入即可：
接下来插入元素5，先处理元素5和元素1、3、4所在的结点，生成一棵子树：
然后将原树中的1、3、4所在的结点去除，生成新子树，将上一步生成的子树与此子树合并：
发现根结点的元素数量超过3个，于是按规则处理，即——将所有元素按每组3个分组，然后将除最后一组外的其他组的最后一个元素，提升为父结点，然后将所有孩子（现在是孙子）按新子结点元素个数进行分配，即“4、6、8”一组，“12”一组，然后将8往上提，再将五个孩子分配——“4、6”结点有两个元素，因此分配3个孩子，“12”只有一个孩子，因此分配两个：
然后插入元素11，直接插入即可：
然后插入元素2，直接插入即可：
2-3-4树创建的代码与2-3树创建代码一致。
7.2.2 删除2-3-4树上的元素
删除逻辑与2-3树一致，不再赘述。
7.3 B树
B树（B tree）是一种平衡的多路查找树，2-3树和2-3-4树都是B树的特例，结点最大的孩子数目称为B树的阶（order），因此，2-3树是3阶的B树，2-3-4树是4阶的B树。
一个m阶的B树具有如下属性：
(1) 每个结点要么是叶子结点，要么拥有2~n个孩子，孩子数量是结点中元素数量+1，即2元素的结点拥有3个孩子，5元素的结点拥有6个孩子；
(2) 所有叶子结点都在同一层次；
(3) 若结点有孩子，则结点中的每个元素，都会有对应的一个小于该结点的孩子，和一个大于该结点的孩子；
B树的元素插入和删除，与2-3树、2-3-4树一致。
7.4 B+树
B+树是应文件系统所需而出的一种B树的变形树，在B树中，每一个元素在该树中只出现一次，有可能在叶子结点上，也有可能在分支结点上，而在B+树中，出现在分支结点中的元素会被当作它们在该分支结点位置的中序后继者（叶子结点）中再次列出，另外，每一个叶子结点都会保存一个指向后一叶子结点的指针。
这样一来，一棵B+树就被分成了两部分，主要部分是叶子结点，保存了所有数据信息和指针，而除叶子结点外的其他结点，均为索引。
如下是一棵B树和其对应的B+树：
可以看到，B+树有很明确的特征：
(1) 非叶子结点与B树相同；
(2) 叶子结点除了存储元素外，还存放着中遍历的下一个结点索引，例如结点1，如果进行中序遍历的话，接下来的元素是2，因此将2的索引放在结点1上；
(3) 叶子结点除了存储元素外，还存放着后一叶子结点的指针，即其右兄弟或堂兄弟的指针；
7.4.1 B+树的插入
我们仍然按下述数组来生成B+树：
首先是第1、2个元素，直接插入：
然后是第3个元素，按照2-3树的插入方法，按如下插入：
注意看，与普通的2-3树相比，结点4上多了一个指针，指向元素8，8是如何来的呢？是其parent上，比4大的第一个元素。
另外，结点4不仅多了一个索引8，还有一个指针，指向了其兄弟结点，这个索引怎么来的呢？规则是——如果不需要重新生成树，则一般直接插入即可，若需要生成树，则：
(1) 在重新生成树前，记住被插入结点的leftBrother（记为originalLeftBrother）、rightBrother（记为originalRightBrother）和nextElement（记为originalNextElement）；
(2) 重新生成树后，再重新迭代新的孩子，若originalLeftBrother不为null，则令originalLeftBrother的rightBrother为第一个新孩子；
(3) 重新生成树后，若最后一个新孩子没有孩子，则令其nextElement和rightBrother为前面记住的originalNextElement和originalRightBrother，若最后一个新孩子有孩子，则nextElement和rightBrother都为null；
(4) 然后迭代新孩子，若这些新孩子都没有孩子结点，则除最后一个新孩子外，每一个新孩子的nextElement为新的parent的elements的同索引元素，每一个新孩子的rightBrother为下一个新孩子；若这些新孩子有孩子结点，则nextElement和rightBrother都为null；
(5) 最后设置新生成树的根结点的rightBrother和nextElement为null。
在本例中，由于原结点没有孩子，因此：
(1) 被插入的结点是4和8所在的结点，originalLeftBrother=null，originalRightBrother=null，originalNextElement=null；
(2) 重新生成树后，第一个孩子是4所在的结点，因originalLeftBrother为null，因此不用处理；
(3) 重新生成树后，最后一个孩子是12，因originalRightBrother和originalNextElement为null，直接设置结点12的nextElement为null，rightBrother为null；
(4) 除最后一个孩子12外，只有一个新孩子，即结点4，它在所有孩子中索引是0，因此设置其nextElement为parent.elements[0]，设置其rightBrother为下一个孩子，即结点12这个孩子；
(5) 新生成的树的根结点是结点[8]，令其nextElement和rightBrother都为null；
接下来插入元素1和元素13，直接插入，结点1、4对应的索引和指针不需要变更：
接下来插入元素9，按照2-3树的插入规则，首先把9插入元素12、13所在的结点，进行变换后，加上nextElement索引和rightBrother索引，按以下步骤执行：
(1) 被插入的结点是12、13所在的结点，originalLeftBrother=[1,4]结点，originalRightBrother=null，originalNextElement=null；
(2) 重新生成树后，第一个孩子是9所在的结点，因此令originalLeftBrother，即[1,4]结点的rightBrother为结点9；
(3) 重新生成树后，最后一个孩子是13，因originalRightBrother和originalNextElement为null，直接设置结点13的nextElement为null，rightBrother为null；
(4) 除最后一个孩子13外，只有一个新孩子，即结点9，它在所有孩子中索引是0，因此设置其nextElement为parent.elements[0]，即12，设置其rightBrother为下一个孩子，即结点13这个孩子；
(5) 新生成的树的根结点是结点[12]，令其nextElement和rightBrother都为null；
然后进行二次变形，把元素12插入结点8，同样的规则：
(1) 被插入的结点是8所在的结点，originalLeftBrother=null，originalRightBrother=null，originalNextElement=null；
(2) 重新生成树后，第一个孩子是[1,4]结点，因originalLeftBrother为null，因此不需要处理；
(3) 重新生成树后，最后一个孩子是13，因originalRightBrother和originalNextElement为null，直接设置结点13的nextElement为null，rightBrother为null；
(4) 除最后一个孩子13外，有两个孩子[1,4]和[9]，在孩子数组中索引分别是0和1，因此child[1,4].nextElement=parent.elements[0]=8，child[1,4].rightBrother=parent.children[0+1]=child[9]，child[9].nextElement=parent.elements[1]=12，child[9].rightBrother=parent.children[1+1]=child[13]；
(5) 新生成的树的根结点是结点[8,12]，令其nextElement和rightBrother都为null；
元素10和15是直接插入，无需进行任何变更：
来看元素6的插入，首先按插入规则进行处理：
(1) 被插入的结点是[1,4]结点，originalLeftBrother=null，originalRightBrother=[9,10]结点，originalNextElement=8；
(2) 重新生成树后，第一个孩子是[1]结点，因originalLeftBrother为null，因此不需要处理；
(3) 重新生成树后，最后一个孩子是[6]结点，令其nextElement=originalNextElement=8，令其rightBrother=originalRightBrother=[9,10]结点；
(4) 除最后一个孩子6外，只有一个孩子[1]，在孩子数组中索引是0，因此child[1].nextElement=parent.elements[0]=4，child[1].rightBrother=parent.children[0+1]=child[6]；
(5) 新生成的树的根结点是结点[4]，令其nextElement和rightBrother都为null；
然后继续插入，被插入的结点为[8,12]：
(1) 被插入的结点是[8,12]结点，originalLeftBrother=null，originalRightBrother=null，originalNextElement=null；
(2) 重新生成树后，第一个孩子是[4]结点，因originalLeftBrother为null，因此不需要处理；
(3) 重新生成树后，最后一个孩子是[12]结点，令其nextElement=originalNextElement=null，令其rightBrother=originalRightBrother=null；
(4) 除最后一个孩子[12]外，只有一个孩子[4]，由于其有孩子结点，因此设置nextElement和rightBrother都为null；
(5) 新生成的树的根结点是结点[8]，令其nextElement和rightBrother都为null；
其他元素的插入则按规则进行，不再赘述。
7.4.1 B+树的元素删除
B+树的删除逻辑与2-3树或2-3-4树的删除逻辑一致，但需要加上leftBrother、rightBrother和nextElement的处理，我们以以下B+树为例进行处理：
首先来删除元素7，由于该结点只有一个元素，相关结点的nextElement和rightElement需要进行调整，规则与新增时类似，如果不需要重新生成树，则一般直接删除元素即可，如果需要重新生成树，则
(1) 在重新生成树前，记住被删除结点父结点的第一个孩子的leftBrother（记为originalLeftBrother），和最后一个孩子的rightBrother（记为originalRightBrother）和nextElement（记为originalNextElement）；
(2) 重新生成树后，若重新生成的树有孩子，则迭代新的孩子，若originalLeftBrother不为null，则令originalLeftBrother的rightBrother为第一个新孩子；而若重新生成的树没有孩子，且originalLeftBrother不为null，则令originalLeftBrother的rightBrother为重新生成的树的根结点；
(3) 重新生成树后，若重新生成的树有孩子，且最后一个新孩子没有孩子，则令其nextElement和rightBrother为前面记住的originalNextElement和originalRightBrother，若最后一个新孩子有孩子，则nextElement和rightBrother都为null；若重新生成的树没有孩子，则直接令重新生成的树的根结点的nextElement为originalNextElement、rightBrother为originalRightBrother；
(4) 若重新生成的树有孩子，则迭代新孩子，若这些新孩子都没有孩子结点，则除最后一个新孩子外，每一个新孩子的nextElement为新的parent的elements的同索引元素，每一个新孩子的rightBrother为下一个新孩子；若这些新孩子有孩子结点，则nextElement和rightBrother都为null；
(5) 若重新生成的树有孩子，则设置新生成树的根结点的rightBrother和nextElement为null；。
对于本例，则是如下：
(1) 被删除的结点是结点[7]，其父是[4,6]结点，因此originalLeftBrother=null，originalNextElement=8，originalRightBrother=[9,10]结点；
(2) 重新生成树后，第一个孩子结点是结点[1,2]，因originalLeftBrother=null，因此不进行处理；
(3) 重新生成树后，最后一个孩子结点是[4,5,6]，因此令其nextElement=originalNextElement=8，令其rightBrother=originalRightBrother=[9,10]结点；
(4) 然后迭代新孩子，除最后一个新孩子外，只有一个孩子[1,2]，于是child[1,2].nextElement=child[1,2].parent.elements[0]=3，child[1,2].rightBrother=child[1,2].parent.children[0+1]=child[4,5,6]；
(5) 最后设置新生成树的根结点的rightBrother和nextElement为null。
然后删除元素21，根据规则，直接与元素20替换即可，不需要进行其他变更：
然后删除结点20，用元素19替换，然后按上述规则处理：
(1) 被删除的结点是结点[20]，其父是[19]结点，因此originalLeftBrother=[16,17]结点，originalNextElement=null，originalRightBrother=null；
(2) 重新生成树后，该树没有孩子，因此令originalLeftBrother.rightBrother=重新生成的树的根结点，即结点[19,22]；
(3) 重新生成树后，该树没有孩子，因此令node[19,22].nextElement=originalNextElement=null，node[19,22].rightBrother=originalRightBrother=null；
(4) 由于重新生成的树没有孩子，因此不做第四步处理；
(5) 由于新生成的树没有孩子，因此不做第五步处理。
然后继续处理，这时被插入的结点变为结点[8,18]，它没有父结点，因此只需要重新构建树即可，所有结点的nextElement和rightBrother都不需要调整：
其他元素的删除都依上述规则处理即可。
7.5 代码实现
根据上文描述，结点定义代码如下所示：
import lombok.Data;
import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
/**
* multi way search tree node
*
* @author Korbin
* @date 2023-11-21 17:42:56
**/
@Data
public class MultiWaySearchTreeNode<T extends Comparable<T>> {
/**
* children, the array length must be 2 or 3 for 2-3 tree, and must be 2 or 3 or 4 for 2-3-4 tree
**/
private MultiWaySearchTreeNode<T>[] children;
/**
* elements, the array length must be 1 or 2 for 2-3 tree, and must be 1 or 2 or 3 for 2-3-4 tree
**/
private T[] elements;
/**
* left brother
**/
private MultiWaySearchTreeNode<T> leftBrother;
/**
* next element value for inorder traversal
**/
private T nextElement;
/**
* parent node
**/
private MultiWaySearchTreeNode<T> parent;
/**
* right brother
**/
private MultiWaySearchTreeNode<T> rightBrother;
/**
* add an child
**/
@SuppressWarnings("unchecked")
public void addChild(MultiWaySearchTreeNode<T> child) {
if (null == children) {
children = (MultiWaySearchTreeNode<T>[]) Array.newInstance(child.getClass(), 0);
}
MultiWaySearchTreeNode<T>[] newChildren = Arrays.copyOf(children, children.length + 1);
newChildren[newChildren.length - 1] = child;
Arrays.sort(newChildren, (o1, o2) -> o1.getMaxElement().compareTo(o2.getMinElement()));
this.children = newChildren;
child.setParent(this);
}
/**
* add an element
**/
@SuppressWarnings("unchecked")
public void addElement(T element) {
if (null == elements) {
elements = (T[]) Array.newInstance(element.getClass(), 0);
}
T[] newE = Arrays.copyOf(elements, elements.length + 1);
newE[newE.length - 1] = element;
Arrays.sort(newE);
this.elements = newE;
}
/**
* get all element
**/
public String getData() {
if (null == elements) {
return "null";
} else {
StringBuilder builder = new StringBuilder();
builder.append("[");
for (int i = 0; i < elements.length - 1; i++) {
builder.append(elements[i]).append(",");
}
builder.append(elements[elements.length - 1]).append("]");
return builder.toString();
}
}
/**
* get max element
**/
public T getMaxElement() {
return elements[elements.length - 1];
}
/**
* get min element
**/
public T getMinElement() {
return elements[0];
}
/**
* remove an child
**/
public void removeChild(MultiWaySearchTreeNode<T> child) {
if (this.children.length == 1) {
this.children = null;
} else {
MultiWaySearchTreeNode<T>[] newChildren = Arrays.copyOf(children, children.length - 1);
List<MultiWaySearchTreeNode<T>> childList = new ArrayList<>();
for (MultiWaySearchTreeNode<T> c : children) {
boolean contains = false;
for (T t : child.getElements()) {
if (Arrays.asList(c.getElements()).contains(t)) {
contains = true;
break;
}
}
if (!contains) {
childList.add(c);
}
}
childList.sort((o1, o2) -> o1.getMaxElement().compareTo(o2.getMinElement()));
this.children = childList.toArray(newChildren);
}
}
/**
* remove an element
**/
@SuppressWarnings("unchecked")
public void removeElement(T element) {
if (this.elements.length == 1) {
this.elements = null;
} else {
T[] newE = (T[]) Array.newInstance(elements[0].getClass(), elements.length - 1);
List<T> newArray = new ArrayList<>();
for (T t : elements) {
if (t.compareTo(element) != 0) {
newArray.add(t);
}
}
this.elements = newArray.toArray(newE);
}
}
/**
* set rightBrother
*
* @param rightBrother right brother
* @author Korbin
* @date 2023-11-29 10:19:26
**/
public void setRightBrother(MultiWaySearchTreeNode<T> rightBrother) {
if (null != rightBrother) {
rightBrother.setLeftBrother(this);
}
this.rightBrother = rightBrother;
}
@Override
public String toString() {
StringBuilder builder = new StringBuilder();
builder.append("Data is ").append(getData());
if (null != parent) {
builder.append(", parent is ").append(parent.getData());
} else {
builder.append(", parent is null");
}
if (null != children) {
builder.append(", children is {");
for (int i = 0; i < children.length - 1; i++) {
builder.append(children[i].getData()).append(", ");
}
builder.append(children[children.length - 1].getData()).append("}");
} else {
builder.append(", children is null");
}
if (null != nextElement) {
builder.append(", next element is ").append(nextElement);
} else {
builder.append(", next element is null");
}
if (null != rightBrother) {
builder.append(", next brother is ").append(rightBrother.getData());
} else {
builder.append(", next brother is null");
}
return builder.toString();
}
}
而树的生成、元素的删除、元素的查找代码如下所示：
import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
/**
* multi way search way
*
* @author Korbin
* @date 2023-11-21 08:57:24
**/
public class MultiWaySearchTree<T extends Comparable<T>> {
/**
* root node
**/
private MultiWaySearchTreeNode<T> root = new MultiWaySearchTreeNode<>();
/**
* insert newNode into node
*
* @param node node to insert
* @param newNode node to be inserted
* @param isBPlusTree is to create a B plus tree
* @param maxChildrenNumber max child number, for 2-3 tree is 3, for 2-3-4 tree is 4
* @author Korbin
* @date 2023-11-22 17:58:59
**/
private void checkAndMoveUp(MultiWaySearchTreeNode<T> node, MultiWaySearchTreeNode<T> newNode,
int maxChildrenNumber, boolean isBPlusTree) {
MultiWaySearchTreeNode<T> parent = node.getParent();
node.addElement(newNode.getElements()[0]);
// if new node's elements' length little or equals than maxChildrenNumber - 1, then just only add newNode's
// children into node
if (null != newNode.getChildren()) {
for (MultiWaySearchTreeNode<T> child : newNode.getChildren()) {
node.addChild(child);
}
}
if (node.getElements().length > maxChildrenNumber - 1) {
// if new node's elements' length greater than maxChildrenNumber - 1
// 会影响parent的第一个孩子的leftBrother的leftBrother，和最后一个孩子的rightBrother
MultiWaySearchTreeNode<T> originalLeftBrother = node.getLeftBrother();
MultiWaySearchTreeNode<T> originalRightBrother = node.getRightBrother();
T originalNextElement = node.getNextElement();
rebuildTree(node, maxChildrenNumber);
if (isBPlusTree) {
resetIndex(node, originalLeftBrother, originalRightBrother, originalNextElement);
}
if (null == parent) {
root = node;
} else {
// remove old node
parent.removeChild(node);
// check and move up
checkAndMoveUp(parent, node, maxChildrenNumber, isBPlusTree);
}
}
}
/**
* create tree from array
*
* @param array array
* @param maxChildrenNumber max child number, for 2-3 tree is 3, for 2-3-4 tree is 4
* @param isBPlusTree is to create a B plus tree
* @author Korbin
* @date 2023-11-22 17:59:48
**/
@SuppressWarnings("unchecked")
public void createTreeFromArray(T[] array, int maxChildrenNumber, boolean isBPlusTree) {
int length = array.length;
if (length < maxChildrenNumber) {
Arrays.sort(array);
root.setElements(array);
return;
}
// if length little than maxElementNumber(maxChildrenNumber - 1), then copy to root
T[] elements = (T[]) Array.newInstance(array[0].getClass(), maxChildrenNumber - 1);
if (maxChildrenNumber - 1 >= 0) {
System.arraycopy(array, 0, elements, 0, maxChildrenNumber - 1);
}
Arrays.sort(elements);
root.setElements(elements);
for (int i = maxChildrenNumber - 1; i < length; i++) {
MultiWaySearchTreeNode<T> node = root;
while (null != node) {
MultiWaySearchTreeNode<T>[] children = node.getChildren();
elements = node.getElements();
if (null == children) {
// has to move up
// find the element which index is length - 2
MultiWaySearchTreeNode<T> newNode = new MultiWaySearchTreeNode<>();
newNode.addElement(array[i]);
checkAndMoveUp(node, newNode, maxChildrenNumber, isBPlusTree);
break;
} else {
// if element to be inserted little than elements[0], then use elements[0]
if (array[i].compareTo(elements[0]) < 0) {
node = node.getChildren()[0];
} else {
// find from last to first, if element to be inserted greater than elements[j], then use
// children[j + 1]
for (int j = elements.length - 1; j >= 0; j--) {
if (array[i].compareTo(elements[j]) > 0) {
node = node.getChildren()[j + 1];
break;
}
}
}
}
}
}
}
/**
* delete an element from tree
*
* @param element element to be deleted
* @param maxChildrenNumber max children number
* @param isBPlusTree is a B plus tree
* @author Korbin
* @date 2023-11-23 17:07:04
**/
public void deleteElement(T element, int maxChildrenNumber, boolean isBPlusTree) {
MultiWaySearchTreeNode<T> node = root;
while (null != node && null != node.getElements()) {
List<T> elementList = Arrays.asList(node.getElements());
if (elementList.contains(element)) {
int elementsLength = elementList.size();
MultiWaySearchTreeNode<T>[] children = node.getChildren();
if (null == children) {
// if this node is leaf node
if (elementsLength > 1) {
// if node's elements' length greater than 1
node.removeElement(element);
} else {
// if node's elements' length equals 1
MultiWaySearchTreeNode<T> parent = node.getParent();
if (null == parent) {
// if this node is root node
node.removeElement(element);
} else {
// if this node is not root node
// delete this node
moveAndMerge(node, maxChildrenNumber, isBPlusTree);
}
}
} else {
// find the index of element
T[] elements = node.getElements();
int delIndex = -1;
for (int i = 0; i < elementsLength; i++) {
if (element.compareTo(elements[i]) == 0) {
delIndex = i;
break;
}
}
// find the max value of the number delIndex child tree
MultiWaySearchTreeNode<T> toReplaceNode = children[delIndex];
while (null != toReplaceNode) {
if (null != toReplaceNode.getChildren()) {
toReplaceNode = toReplaceNode.getChildren()[toReplaceNode.getChildren().length - 1];
} else {
break;
}
}
if (null == toReplaceNode) {
// child must not be null
break;
}
T toReplaceElement = toReplaceNode.getMaxElement();
// use the max value of the number delIndex child tree to replace this element
node.removeElement(element);
node.addElement(toReplaceElement);
if (isBPlusTree) {
toReplaceNode.setNextElement(toReplaceElement);
}
// if child's elements' length greater than 1
if (toReplaceNode.getElements().length > 1) {
toReplaceNode.removeElement(toReplaceElement);
} else {
// if child's elements' length equals 1
moveAndMerge(toReplaceNode, maxChildrenNumber, isBPlusTree);
}
}
break;
} else if (element.compareTo(node.getMinElement()) < 0) {
// if element little than node's first element, than node change to node's first child
if (null == node.getChildren()) {
break;
} else {
node = node.getChildren()[0];
}
} else if (null != node.getChildren()) {
// find from last element to first element
for (int j = elementList.size() - 1; j >= 0; j--) {
// if element greater than element[j], than node change to node's j+1 child
if (element.compareTo(node.getElements()[j]) > 0) {
node = node.getChildren()[j + 1];
break;
}
}
} else {
break;
}
}
}
/**
* find node by element
*
* @param element element
* @return node
* @author Korbin
* @date 2023-11-28 15:08:35
**/
public MultiWaySearchTreeNode<T> findNodeByElement(T element) {
MultiWaySearchTreeNode<T> node = root;
while (null != node) {
T[] elements = node.getElements();
if (null == elements) {
return null;
}
for (T e : elements) {
if (element.compareTo(e) == 0) {
return node;
}
}
MultiWaySearchTreeNode<T>[] children = node.getChildren();
if (null != children) {
if (element.compareTo(node.getMinElement()) < 0) {
node = children[0];
} else {
// find from last element to first element
for (int j = elements.length - 1; j >= 0; j--) {
// if element greater than element[j], than node change to node's j+1 child
if (element.compareTo(node.getElements()[j]) > 0) {
node = node.getChildren()[j + 1];
break;
}
}
}
}
}
return null;
}
/**
* reset left brother's nextElement and rightBrother and move and merge
*
* @param node node to move
* @param maxChildrenNumber max children number
* @param isBPlusTree is a B+ tree
* @author Korbin
* @date 2023-11-30 22:53:36
**/
private void moveAndMerge(MultiWaySearchTreeNode<T> node, int maxChildrenNumber, boolean isBPlusTree) {
MultiWaySearchTreeNode<T> parent = node.getParent();
// if is a B+ tree, then parent's first child's leftBrother's rightBrother has to reset, rebuild tree's new
// last child's nextElement and rightBrother has to reset
MultiWaySearchTreeNode<T>[] parentChildren = parent.getChildren();
MultiWaySearchTreeNode<T> originalLeftBrother = parentChildren[0].getLeftBrother();
MultiWaySearchTreeNode<T> originalRightBrother = parentChildren[parentChildren.length - 1].getRightBrother();
T originalNextElement = parentChildren[parentChildren.length - 1].getNextElement();
parent.removeChild(node);
moveAndMerge(parent, null, maxChildrenNumber);
if (isBPlusTree) {
resetIndex(parent, originalLeftBrother, originalRightBrother, originalNextElement);
}
}
/**
* move and merge,add all elements of parent's all children but not node into parent, add all children of parent's
* all children but not node into parent, and then rebuild the tree
*
* @param parent parent
* @param node one child of parent or null
* @param maxChildrenNumber max children number
* @author Korbin
* @date 2023-11-27 16:17:39
**/
private void moveAndMerge(MultiWaySearchTreeNode<T> parent, MultiWaySearchTreeNode<T> node, int maxChildrenNumber) {
MultiWaySearchTreeNode<T>[] children = parent.getChildren();
if (null != children) {
for (MultiWaySearchTreeNode<T> child : children) {
if (null == node || child.getMinElement().compareTo(node.getMinElement()) != 0) {
for (T element : child.getElements()) {
// add all children's element into parent
parent.addElement(element);
}
if (null != child.getChildren()) {
// add all grand children into parent
for (MultiWaySearchTreeNode<T> grandChild : child.getChildren()) {
parent.addChild(grandChild);
}
}
// remove this child
parent.removeChild(child);
}
}
T[] elements = parent.getElements();
int elementsLength = elements.length;
// rebuild this tree
if (elementsLength <= maxChildrenNumber - 1) {
if (elementsLength == 3) {
// if elements' length is 3, just need to build tree use these three elements
rebuildTree(parent, 3);
} else {
// iterate grand parent
MultiWaySearchTreeNode<T> grandParent = parent.getParent();
if (null != grandParent) {
// if grand parent is not null
moveAndMerge(grandParent, parent, maxChildrenNumber);
}
}
} else {
rebuildTree(parent, maxChildrenNumber);
}
}
}
/**
* rebuild a tree
*
* @param node to rebuild node
* @param maxChildrenNumber max children number
* @author Korbin
* @date 2023-11-28 20:53:34
**/
private void rebuildTree(MultiWaySearchTreeNode<T> node, int maxChildrenNumber) {
MultiWaySearchTreeNode<T>[] children = node.getChildren();
T[] elements = node.getElements();
int elementsLength = elements.length;
int shardNumber = (elementsLength % (maxChildrenNumber - 1) == 0 ? elementsLength / (maxChildrenNumber - 1) :
elementsLength / (maxChildrenNumber - 1) + 1);
List<MultiWaySearchTreeNode<T>> rebuildNodeList = new ArrayList<>();
for (int i = 0; i < shardNumber; i++) {
MultiWaySearchTreeNode<T> newNode = new MultiWaySearchTreeNode<>();
for (int j = 0; j < maxChildrenNumber - 1; j++) {
int index = i * (maxChildrenNumber - 1) + j;
if (index < elementsLength) {
newNode.addElement(elements[index]);
node.removeElement(elements[index]);
}
}
rebuildNodeList.add(newNode);
}
for (int i = 0; i < rebuildNodeList.size() - 1; i++) {
MultiWaySearchTreeNode<T> newNode = rebuildNodeList.get(i);
node.addElement(newNode.getMaxElement());
newNode.removeElement(newNode.getMaxElement());
node.addChild(newNode);
}
node.addChild(rebuildNodeList.get(rebuildNodeList.size() - 1));
int startChildIndex = 0;
// rebuild child
if (null != children) {
for (MultiWaySearchTreeNode<T> newNode : rebuildNodeList) {
int childrenSize = startChildIndex + newNode.getElements().length + 1;
for (int i = startChildIndex; i < childrenSize && i < children.length; i++) {
newNode.addChild(children[i]);
node.removeChild(children[i]);
startChildIndex++;
}
}
}
}
/**
* reset next element and right brother
*
* @param node to reset node's parent
* @param originalLeftBrother node's or first child of it's parent's left brother
* @param originalRightBrother node's or last child of it's parent's right brother
* @param originalNextElement node's or last child of it's parent's next element
* @author Korbin
* @date 2023-12-04 15:40:09
**/
private void resetIndex(MultiWaySearchTreeNode<T> node, MultiWaySearchTreeNode<T> originalLeftBrother,
MultiWaySearchTreeNode<T> originalRightBrother, T originalNextElement) {
MultiWaySearchTreeNode<T>[] newParentChildren = node.getChildren();
if (null != newParentChildren) {
// rebuild tree has children
if (null != originalLeftBrother) {
// set right brother of original first child's left brother as new parent children's first node
originalLeftBrother.setRightBrother(newParentChildren[0]);
}
if (null == newParentChildren[newParentChildren.length - 1].getChildren()) {
// set right brother of new parent children's last child as original last child's right brother
newParentChildren[newParentChildren.length - 1].setRightBrother(originalRightBrother);
// set next element of new parent children's last child as original last child's next element
newParentChildren[newParentChildren.length - 1].setNextElement(originalNextElement);
} else {
newParentChildren[newParentChildren.length - 1].setNextElement(null);
newParentChildren[newParentChildren.length - 1].setRightBrother(null);
}
// set all but last child of new parent's children's next element and right brother
T[] newElements = node.getElements();
for (int i = 0; i < newParentChildren.length - 1; i++) {
if (null == newParentChildren[i].getChildren()) {
newParentChildren[i].setRightBrother(newParentChildren[i + 1]);
newParentChildren[i].setNextElement(newElements[i]);
} else {
newParentChildren[i].setNextElement(null);
newParentChildren[i].setRightBrother(null);
}
}
node.setNextElement(null);
node.setRightBrother(null);
} else {
// rebuild tree does not have children
if (null != originalLeftBrother) {
originalLeftBrother.setRightBrother(node);
}
// set right brother of new parent as original last child's right brother
node.setRightBrother(originalRightBrother);
// set next element of new parent as original last child's next element
node.setNextElement(originalNextElement);
}
}
/**
* set root
*
* @param root root node
* @author Korbin
* @date 2023-11-27 16:20:42
**/
public void setRoot(MultiWaySearchTreeNode<T> root) {
this.root = root;
}
}
