2-3 树

二叉树又叫 2-树

2- 节点
3- 节点

• 2- 节点：一个键，两条链接
• 3- 节点：两个键，三条链接（中间链接的子节点大小在两个键之间）

所有节点都是 2- 节点的树叫 2- 树，即普通的二叉树；节点由 2- 节点或 3- 节点组成的树叫 2-3 树

2-3 树的插入操作

总的来说: 就是将新节点放入其父节点中（树中最底层的节点，2-节点变成3-节点；3-节点变成需要分解的4-节点）

• 如果对于 2- 节点，直接将新键放入 2- 节点，使其变成 3- 节点
• 对于 3- 节点：（不断将临时 4- 节点的中间键推入父节点）
  • 将键放入 3- 节点，使其变成临时的 4- 节点（3个键），将中间键翻入父节点，并将 4- 节点分解成两个 2- 节点；如果父节点成为 4- 节点，重复 放入-分解 操作，直到遇到一个父节点是 2- 节点
  • 如果树的根节点变成 4- 节点，将节点分解成 三个 2- 节点，新的根节点为中间键（树的高度 +1）