java数据结构和算法——2-3树的介绍

一、2-3树的图解

二、2-3树的特点

• 2-3树是最简单的B树结构，具有如下特点：
• 2-3树的所有叶子节点都在同一层。(只要是B树都满足这个条件)
• 有两个子节点的节点叫二节点。二节点要么没有子节点，要么有两个子节点。
• 有三个子节点的节点叫三节点。三节点要么没有子节点，要么有三个子节点。
• 2-3树是由二节点和三节点构成的树。

三、2-3树应用案例的需求

示例需求：将数列{16, 24, 12, 32, 14, 26, 34, 10, 8, 28, 38, 20} 构建成2-3树，并保证数据插入的大小顺序。

四、2-3树应用案例的插入规则

• 2-3树的所有叶子节点都在同一层。(只要是B树都满足这个条件)
• 有两个子节点的节点叫二节点，二节点要么没有子节点，要么有两个子节点。
• 有三个子节点的节点叫三节点，三节点要么没有子节点，要么有三个子节点。
• 当按照规则插入一个数到某个节点时，不能满足上面三个要求，就需要拆，先向上拆，如果上层满，则拆本层，拆后仍然需要满足上面3个条件。
• 对于三节点的子树的值大小仍然遵守(BST 二叉排序树)的规则。

五、2-3树应用案例的构建步骤图解

六、2-3-4树的介绍

• 2-3-4树概念和2-3树类似，也是一种B树，图解如下：