2-3 tree

• 2-3 树
  • Basic Concepts
    • 二叉树
    • 有序二叉树
    • 平衡二叉树
    • 2-3 树
  • 定义
    • 2-3树的定义
    • 2-3树的性质
  • 节点结构
  • 2-3树查找
  • 2-3树插入
    • 插入的4种情况
    • 向 2- 节点中插入新节点
    • 向一棵只含 一个 3- 节点的树中插入新节点
    • 向一个父节点为2-节点的3-节点中插入新节点
    • 向一个父节点为3-节点的3-节点中插入新节点
  • 2-3 树删除
    • 删除的4种情况
    • 删除非叶子节点
    • 删除3-叶子节点中的键
    • 删除2-叶子节点的键 （复杂复杂）
      • 当前待删节点的父节点是2-节点，兄弟节点是3-节点
      • 当前待删节点的父节点是2-节点，兄弟节点是2-节点
      • 当前待删节点的父节点为3-节点（复杂）
      • 2-3树为满二叉树，删除叶子节点
  • Contact
  • License

2-3 树

Created 2021.04.09 by William Yu; Last modified: 2021.04.09-V1.0.2

Contact: windmillyucong@163.com

Copyleft! 2021 William Yu. Some rights reserved.

References

• https://zhuanlan.zhihu.com/p/92394224
• https://zhuanlan.zhihu.com/p/137076341 python Code
• https://github.com/infinityglow/Algorithm-and-Complexity/blob/master/Transform%20and%20Conquer/Two-Three%20Tree/2-3%20tree.py python code
• https://www.cs.usfca.edu/~galles/visualization/Algorithms.html 算法可视化

Basic Concepts

二叉树

有序二叉树

• 有序二叉树的缺点：
  • 当原序列本身就有序时，搜索效率降低为O(n)

平衡二叉树

• 为解决有序二叉树的搜索效率低的问题，使用平衡二叉树维护树的高度
• 性能消耗：每次插入与删除节点后，需要维护树的平衡

2-3 树

• 2-3树本质也是一种平衡搜索树，但不是二叉树
• 2-3树可以有两种节点：
  • 2-节点：拥有一个键和两个子节点
  • 3-节点：拥有两个键和三个子节点

定义

2-3树的定义

• 2-3树可以为空
• 2-节点有一个数据域和两个子节点
  • 当前节点的数值大于左子树中所有节点的数据，小于右子树中所有节点的数据
• 3-节点有两个数据域和三个子节点
  • 左子树中所有节点的数据要小于a
  • 中子树中所有节点的数据要大于a小于b
  • 右子树中所有节点的数据要大于b

2-3树的性质

• 所有叶子节点都在树的同一层
• 上面这一条性质是需要维护的

节点结构

1
2
template <class T>
//todo(congyu)

2-3树查找

太简单了，略过

2-3树插入

• 先查找，若已存在，则不插入

插入的4种情况

• 向 2- 节点中插入新节点
• 向一棵只含 3- 节点的树中插入新节点
• 向一个父节点为 2- 节点的 3- 节点中插入新节点
• 向一个父节点为 3- 节点的 3- 节点中插入新节点

向 2- 节点中插入新节点

1. 直接将2-节点变为3-节点，将新节点插入即可

向一棵只含 一个 3- 节点的树中插入新节点

1. 先临时将新键存入唯一的3-节点中，构造一个4-节点
2. 将4-节点转化为由3个2节点组成的2-3树
3. 分解后树的高度会增加1

向一个父节点为2-节点的3-节点中插入新节点

1. 先临时将新键存入3-节点中，构造一个4-节点

2. 将该 4-节点拆分

   1. 分解时将中键移动到父节点中将，父节点由2-节点变成3-节点
      1. 该中键在父节点中的位置由它和原父节点中的键的大小决定
   2. 原4节点的左右两个键变成两个2-节点

   

向一个父节点为3-节点的3-节点中插入新节点

1. 插入节点后构造临时4- 节点
2. 分解临时4- 节点，将中键向上合并
3. 重复上述步骤，构造4-节点，分解，向上合并
4. 直到遇到一个2-节点，并将其合并为一个不需要继续分解的3-节点
5. 或者遇到根节点
   1. 若根节点是2节点，变成3-节点即可
   2. 若根节点本身就已经是3-节点，合并新键之后，根节点变成4- 节点，需要继续分解根节点

分解根节点

2-3 树删除

删除之前先查找，查找成功才可以删除

删除的4种情况

• 删除非叶子节点
• 删除不为2-节点的叶子节点
• 删除 2-节点的叶子节点

删除非叶子节点

1. 使用中序遍历下的直接后继节点key 来覆盖 当前待删节点key
2. 再删除用来覆盖的后继节点key

删除3-叶子节点中的键

1. 直接删除即可

   

删除2-叶子节点的键 （复杂复杂）

当前待删节点的父节点是2-节点，兄弟节点是3-节点

1. 将父节点移动到当前待删节点位置
2. 将兄弟节点中最接近当前位置的key移动到父节点

当前待删节点的父节点是2-节点，兄弟节点是2-节点

1. 移动兄弟节点的中序遍历直接后驱到兄弟节点
2. 使兄弟节点变成3-节点
3. 变成上一种情况

当前待删节点的父节点为3-节点（复杂）

1. 将3-父节点中的一个键移动到孩子中，父节点变成2-节点

2-3树为满二叉树，删除叶子节点

1. 将2-3树的层数减少
2. 将当前删除节点的兄弟节点合并到父节点中
3. 同时将父节点的所有兄弟节点合并到父节点的父节点中
4. 如果产生了4-节点，再分解4-节点

Contact

Feel free to contact me windmillyucong@163.com anytime for anything.

License

Creative Commons BY-SA 4.0

• Previous
  平衡二叉树AVL
• Next
  B树