蓬安网站建设,做软件需要网站,wordpress基本教程,网站需要建手机版的吗注#xff1a;本文同步发布于稀土掘金。
7 多路查找树 多路查找树#xff08;multi-way search tree#xff09;#xff0c;其每个结点的孩子可以多于两个#xff0c;且每一个结点处可以存储多个元素。由于它是查找树#xff0c;所有元素之间存在某种特定的排序关系。
…注本文同步发布于稀土掘金。
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上多了一个指针指向元素88是如何来的呢是其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所在的结点originalLeftBrothernulloriginalRightBrothernulloriginalNextElementnull (2) 重新生成树后第一个孩子是4所在的结点因originalLeftBrother为null因此不用处理 (3) 重新生成树后最后一个孩子是12因originalRightBrother和originalNextElement为null直接设置结点12的nextElement为nullrightBrother为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]结点originalRightBrothernulloriginalNextElementnull (2) 重新生成树后第一个孩子是9所在的结点因此令originalLeftBrother即[1,4]结点的rightBrother为结点9 (3) 重新生成树后最后一个孩子是13因originalRightBrother和originalNextElement为null直接设置结点13的nextElement为nullrightBrother为null (4) 除最后一个孩子13外只有一个新孩子即结点9它在所有孩子中索引是0因此设置其nextElement为parent.elements[0]即12设置其rightBrother为下一个孩子即结点13这个孩子 (5) 新生成的树的根结点是结点[12]令其nextElement和rightBrother都为null 然后进行二次变形把元素12插入结点8同样的规则 (1) 被插入的结点是8所在的结点originalLeftBrothernulloriginalRightBrothernulloriginalNextElementnull (2) 重新生成树后第一个孩子是[1,4]结点因originalLeftBrother为null因此不需要处理 (3) 重新生成树后最后一个孩子是13因originalRightBrother和originalNextElement为null直接设置结点13的nextElement为nullrightBrother为null (4) 除最后一个孩子13外有两个孩子[1,4]和[9]在孩子数组中索引分别是0和1因此child[1,4].nextElementparent.elements[0]8child[1,4].rightBrotherparent.children[01]child[9]child[9].nextElementparent.elements[1]12child[9].rightBrotherparent.children[11]child[13] (5) 新生成的树的根结点是结点[8,12]令其nextElement和rightBrother都为null 元素10和15是直接插入无需进行任何变更 来看元素6的插入首先按插入规则进行处理 (1) 被插入的结点是[1,4]结点originalLeftBrothernulloriginalRightBrother[9,10]结点originalNextElement8 (2) 重新生成树后第一个孩子是[1]结点因originalLeftBrother为null因此不需要处理 (3) 重新生成树后最后一个孩子是[6]结点令其nextElementoriginalNextElement8令其rightBrotheroriginalRightBrother[9,10]结点 (4) 除最后一个孩子6外只有一个孩子[1]在孩子数组中索引是0因此child[1].nextElementparent.elements[0]4child[1].rightBrotherparent.children[01]child[6] (5) 新生成的树的根结点是结点[4]令其nextElement和rightBrother都为null 然后继续插入被插入的结点为[8,12] (1) 被插入的结点是[8,12]结点originalLeftBrothernulloriginalRightBrothernulloriginalNextElementnull (2) 重新生成树后第一个孩子是[4]结点因originalLeftBrother为null因此不需要处理 (3) 重新生成树后最后一个孩子是[12]结点令其nextElementoriginalNextElementnull令其rightBrotheroriginalRightBrothernull (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]结点因此originalLeftBrothernulloriginalNextElement8originalRightBrother[9,10]结点 (2) 重新生成树后第一个孩子结点是结点[1,2]因originalLeftBrothernull因此不进行处理 (3) 重新生成树后最后一个孩子结点是[4,5,6]因此令其nextElementoriginalNextElement8令其rightBrotheroriginalRightBrother[9,10]结点 (4) 然后迭代新孩子除最后一个新孩子外只有一个孩子[1,2]于是child[1,2].nextElementchild[1,2].parent.elements[0]3child[1,2].rightBrotherchild[1,2].parent.children[01]child[4,5,6] (5) 最后设置新生成树的根结点的rightBrother和nextElement为null。 然后删除元素21根据规则直接与元素20替换即可不需要进行其他变更 然后删除结点20用元素19替换然后按上述规则处理 (1) 被删除的结点是结点[20]其父是[19]结点因此originalLeftBrother[16,17]结点originalNextElementnulloriginalRightBrothernull (2) 重新生成树后该树没有孩子因此令originalLeftBrother.rightBrother重新生成的树的根结点即结点[19,22] (3) 重新生成树后该树没有孩子因此令node[19,22].nextElementoriginalNextElementnullnode[19,22].rightBrotheroriginalRightBrothernull (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 MultiWaySearchTreeNodeT extends ComparableT {/*** 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 MultiWaySearchTreeNodeT[] 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 MultiWaySearchTreeNodeT leftBrother;/*** next element value for inorder traversal**/private T nextElement;/*** parent node**/private MultiWaySearchTreeNodeT parent;/*** right brother**/private MultiWaySearchTreeNodeT rightBrother;/*** add an child**/SuppressWarnings(unchecked)public void addChild(MultiWaySearchTreeNodeT child) {if (null children) {children (MultiWaySearchTreeNodeT[]) Array.newInstance(child.getClass(), 0);}MultiWaySearchTreeNodeT[] 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(MultiWaySearchTreeNodeT child) {if (this.children.length 1) {this.children null;} else {MultiWaySearchTreeNodeT[] newChildren Arrays.copyOf(children, children.length - 1);ListMultiWaySearchTreeNodeT childList new ArrayList();for (MultiWaySearchTreeNodeT 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);ListT 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(MultiWaySearchTreeNodeT rightBrother) {if (null ! rightBrother) {rightBrother.setLeftBrother(this);}this.rightBrother rightBrother;}Overridepublic 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 MultiWaySearchTreeT extends ComparableT {/*** root node**/private MultiWaySearchTreeNodeT 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(MultiWaySearchTreeNodeT node, MultiWaySearchTreeNodeT newNode,int maxChildrenNumber, boolean isBPlusTree) {MultiWaySearchTreeNodeT parent node.getParent();node.addElement(newNode.getElements()[0]);// if new nodes elements length little or equals than maxChildrenNumber - 1, then just only add newNodes// children into nodeif (null ! newNode.getChildren()) {for (MultiWaySearchTreeNodeT child : newNode.getChildren()) {node.addChild(child);}}if (node.getElements().length maxChildrenNumber - 1) {// if new nodes elements length greater than maxChildrenNumber - 1// 会影响parent的第一个孩子的leftBrother的leftBrother和最后一个孩子的rightBrotherMultiWaySearchTreeNodeT originalLeftBrother node.getLeftBrother();MultiWaySearchTreeNodeT 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 nodeparent.removeChild(node);// check and move upcheckAndMoveUp(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 rootT[] 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) {MultiWaySearchTreeNodeT node root;while (null ! node) {MultiWaySearchTreeNodeT[] children node.getChildren();elements node.getElements();if (null children) {// has to move up// find the element which index is length - 2MultiWaySearchTreeNodeT 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) {MultiWaySearchTreeNodeT node root;while (null ! node null ! node.getElements()) {ListT elementList Arrays.asList(node.getElements());if (elementList.contains(element)) {int elementsLength elementList.size();MultiWaySearchTreeNodeT[] children node.getChildren();if (null children) {// if this node is leaf nodeif (elementsLength 1) {// if nodes elements length greater than 1node.removeElement(element);} else {// if nodes elements length equals 1MultiWaySearchTreeNodeT parent node.getParent();if (null parent) {// if this node is root nodenode.removeElement(element);} else {// if this node is not root node// delete this nodemoveAndMerge(node, maxChildrenNumber, isBPlusTree);}}} else {// find the index of elementT[] 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 treeMultiWaySearchTreeNodeT 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 nullbreak;}T toReplaceElement toReplaceNode.getMaxElement();// use the max value of the number delIndex child tree to replace this elementnode.removeElement(element);node.addElement(toReplaceElement);if (isBPlusTree) {toReplaceNode.setNextElement(toReplaceElement);}// if childs elements length greater than 1if (toReplaceNode.getElements().length 1) {toReplaceNode.removeElement(toReplaceElement);} else {// if childs elements length equals 1moveAndMerge(toReplaceNode, maxChildrenNumber, isBPlusTree);}}break;} else if (element.compareTo(node.getMinElement()) 0) {// if element little than nodes first element, than node change to nodes first childif (null node.getChildren()) {break;} else {node node.getChildren()[0];}} else if (null ! node.getChildren()) {// find from last element to first elementfor (int j elementList.size() - 1; j 0; j--) {// if element greater than element[j], than node change to nodes j1 childif (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 MultiWaySearchTreeNodeT findNodeByElement(T element) {MultiWaySearchTreeNodeT 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;}}MultiWaySearchTreeNodeT[] children node.getChildren();if (null ! children) {if (element.compareTo(node.getMinElement()) 0) {node children[0];} else {// find from last element to first elementfor (int j elements.length - 1; j 0; j--) {// if element greater than element[j], than node change to nodes j1 childif (element.compareTo(node.getElements()[j]) 0) {node node.getChildren()[j 1];break;}}}}}return null;}/*** reset left brothers 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(MultiWaySearchTreeNodeT node, int maxChildrenNumber, boolean isBPlusTree) {MultiWaySearchTreeNodeT parent node.getParent();// if is a B tree, then parents first childs leftBrothers rightBrother has to reset, rebuild trees new// last childs nextElement and rightBrother has to resetMultiWaySearchTreeNodeT[] parentChildren parent.getChildren();MultiWaySearchTreeNodeT originalLeftBrother parentChildren[0].getLeftBrother();MultiWaySearchTreeNodeT 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 parents all children but not node into parent, add all children of parents* 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(MultiWaySearchTreeNodeT parent, MultiWaySearchTreeNodeT node, int maxChildrenNumber) {MultiWaySearchTreeNodeT[] children parent.getChildren();if (null ! children) {for (MultiWaySearchTreeNodeT child : children) {if (null node || child.getMinElement().compareTo(node.getMinElement()) ! 0) {for (T element : child.getElements()) {// add all childrens element into parentparent.addElement(element);}if (null ! child.getChildren()) {// add all grand children into parentfor (MultiWaySearchTreeNodeT grandChild : child.getChildren()) {parent.addChild(grandChild);}}// remove this childparent.removeChild(child);}}T[] elements parent.getElements();int elementsLength elements.length;// rebuild this treeif (elementsLength maxChildrenNumber - 1) {if (elementsLength 3) {// if elements length is 3, just need to build tree use these three elementsrebuildTree(parent, 3);} else {// iterate grand parentMultiWaySearchTreeNodeT grandParent parent.getParent();if (null ! grandParent) {// if grand parent is not nullmoveAndMerge(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(MultiWaySearchTreeNodeT node, int maxChildrenNumber) {MultiWaySearchTreeNodeT[] children node.getChildren();T[] elements node.getElements();int elementsLength elements.length;int shardNumber (elementsLength % (maxChildrenNumber - 1) 0 ? elementsLength / (maxChildrenNumber - 1) :elementsLength / (maxChildrenNumber - 1) 1);ListMultiWaySearchTreeNodeT rebuildNodeList new ArrayList();for (int i 0; i shardNumber; i) {MultiWaySearchTreeNodeT 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) {MultiWaySearchTreeNodeT 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 childif (null ! children) {for (MultiWaySearchTreeNodeT 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 nodes parent* param originalLeftBrother nodes or first child of its parents left brother* param originalRightBrother nodes or last child of its parents right brother* param originalNextElement nodes or last child of its parents next element* author Korbin* date 2023-12-04 15:40:09**/private void resetIndex(MultiWaySearchTreeNodeT node, MultiWaySearchTreeNodeT originalLeftBrother,MultiWaySearchTreeNodeT originalRightBrother, T originalNextElement) {MultiWaySearchTreeNodeT[] newParentChildren node.getChildren();if (null ! newParentChildren) {// rebuild tree has childrenif (null ! originalLeftBrother) {// set right brother of original first childs left brother as new parent childrens first nodeoriginalLeftBrother.setRightBrother(newParentChildren[0]);}if (null newParentChildren[newParentChildren.length - 1].getChildren()) {// set right brother of new parent childrens last child as original last childs right brothernewParentChildren[newParentChildren.length - 1].setRightBrother(originalRightBrother);// set next element of new parent childrens last child as original last childs next elementnewParentChildren[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 parents childrens next element and right brotherT[] 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 childrenif (null ! originalLeftBrother) {originalLeftBrother.setRightBrother(node);}// set right brother of new parent as original last childs right brothernode.setRightBrother(originalRightBrother);// set next element of new parent as original last childs next elementnode.setNextElement(originalNextElement);}}/*** set root** param root root node* author Korbin* date 2023-11-27 16:20:42**/public void setRoot(MultiWaySearchTreeNodeT root) {this.root root;}}
