算法学习----2-3-4树原理演示

目标

理解2-3-4树概念，并用图展示插入流程

概念和规则

2-3-4树和红黑树一样，也是平衡树。只不过不是二叉树，它的子节点数目可以达到4个，有如下规则：

• 若父节点中存有1个数据项，则必有2个子节点。
• 若父节点中存有2个数据项，则必有3个子节点。
• 若父节点中存有3个数据项，则必有4个子节点。
• 新的数据项总是插入在叶结点中，在树的最底层
• 在插入新数据时，从根节点找寻位置的过程中遇到任何一个满节点，都要先进行分裂
• 分裂规则：

  1. 如果待分裂为根节点，则第一个和第三个数据变成两个字节点，当前根节点只留中间的数据

  2. 待分裂不是根节点，则当前节点中间数据上升到父节点，第一盒第三数据分裂成两个节点

效果演示

演示插入数据62、31、5、88、99、21、18、4、100、111、112

1. 插入62、31、5没有任何冲突满值，直接插入顶层

   
   image.png

2. 插入88，遇到第一个满节点，先进行分裂，留下31，5、62分到两个子节点，此时再插入88

   
   image.png

3. 插入99，直接插入

   
   image.png

4. 插入21、18，都没有遇到满节点，直接插入

   
   image.png

5. 插入4，左节点已满，进行分裂：18上升到父节点，当前节点分成两个节点

   
   image.png

6. 插入100，右节点已满，进行分裂，逻辑如上，结果如下：

   
   image.png

7. 插入111，根节点以满，先进行分裂，再插入

   
   image.png

8. 同理插入最后一个112

   
   image.png

完工！