199f5f6bd172eaa211c568b99abe6ceb
数据结构与算法——2-3-4树

1 引言

  在上一篇文章中介绍了2-3树的定义以及插入删除操作。本篇文章将在2-3树的基础上更进一步,介绍比2-3树更为复杂的数据结构2-3-4树。之所以介绍2-3-4树是因为2-3-4树与极为重要的红黑树有着等价关系,通过先学习2-3-4树为后面学习红黑树打下基础,增进对于红黑树的理解。

2 2-3-4树

  2-3树不再是单纯的二叉树了,因为2-3树中除了2-节点之外还存在3-节点。在2-3树的基础上进一步扩展,2-3-4树在2-3树的基础上添加4-节点。4-节点可以存储3个键值,最多可以拥有4棵子树。

3 定义

(1)每个节点每个节点有1、2或3个key,分别称为2-节点,3-节点,4-节点。
(2)所有叶子节点到根节点的长度一致(也就是说叶子节点都在同一层)。
(3)每个节点的key从左到右保持了从小到大的顺序,两个key之间的子树中所有的 key一定大于它的父节点的左key,小于父节点的右key。

例如:图3.1所示的一棵2-3-4树。其中,有5个2-节点,2个3-节点和1个4-节点。
图3.1

图3.1

4 查找

2-3-4树的查找类似了二叉树的查找过程,通过键值的比较来决定遍历方向。

例如:在图3.1所示树中查找key为22的节点。

例如:在图3.1所示树中查找key为15的节点。

5 插入

  如果2-3-4树中已存在当前插入的key,则插入失败,否则最终一定是在叶子节点中进行插入操作,因为查找过程的结束位置在叶子节点。节点的插入主要有以下几种情形:

5.1 非4-节点插入

  插入步骤:如果待插入的节点不是4-节点,那么直接在该节点插入。

例如:在2-节点插入key为62的节点:
图解

例如:在3-节点插入key为94的节点:
图解

5.2 4-节点插入

  插入步骤:如果待插入的节点是个4-节点,那么应该先分裂该节点然后再插入。一个4-节点可以分裂成一个根节点和两个子节点(这三个节点各含一个key)然后在子节点中插入,我们把分裂形成的根节点中的key看成向上层插入的key,然后重复5.1和5.2。

图解:

5.3 父节点分裂

  如果是在4节点中进行插入,每次插入会多出一个分支,如果插入操作导致父节点分裂。若插入节点,导致根节点发生分裂,则2-3-4树会生长一层。

图解:


top Created with Sketch.