2-3-4树

2-3-4树的定义

• 所有叶子节点都有相同的深度。(插入都在叶节点,叶节点的高度都是等高的)
• 是一颗满树(不是满二叉树)
• 2节点：值为一个元素，有左右，两个子节点
• 3节点：值为两个元素，有左中右，3个子节点
• 4节点：值为三个元素，有左1左2右1右2，4个子节点

---

2-3-4树的添加过程,(也是有序树,左子树小于右子树)

• 添加一个2 。(此时类似存在一个2节点)

  
  image.png

• 再添加一个3，直接放到2的旁边和2合并在一起。(此时类似存在一个3节点)

  
  image.png

• 再添加一个4，直接放到3的旁边和3合并在一起。(此时类似存在一个4节点)

  
  image.png

• 再添加一个5节点。由于234树中，值最多为3，所以此时需要将节点234的中间3挤出去，并将24作为3的左右子节点。

  
  image.png

• 然后再将5和4放在一起。

  
  image.png

• 再添加一个6，直接和45合并。

  
  image.png

• 再添加一个7，此时456被拎出去分裂，同上5被挤出去。

  
  image.png

• 5再找节点合并，如图和3合并

  
  image.png

• 再添加7

  
  image.png

• 再添加一个8，9

  
  添加8
  拎出去分裂，并且添加9
  7寻找节点合并
• ...

---

2-3-4树的查找

1. 与结点中的数从左到右相比较，若不存在
2. 根据左小右大，选择查找子结点的区间
3. 若找到了，则直接返回该结点，否则，在其子女中继续递归寻找

---

2-3-4树的插入

• 根据上面的示意图可知一般的插入操作:
  1. 第一个节点不需要合并
  2. 新的数据项一般要插在叶节点里
  3. 新增一个节点，根据查找的方式。应该合并的节点，进行合并
  4. 超过4节点时，发生拎出去裂变，裂变出来的父节点再次进行合并

---

2-3-4树的删除

• 删除的是叶子节点：
  直接删除
• 删除的节点有子节点：

  1. 将2-3-4树往x轴压平

     
     image.png
     image.png
  2. 那么节点前面的节点叫前驱节点，后面的节点叫后继节点