56c51bd572f6fb25c5df96bd31ea17ee
数据结构与算法——2-3树

1 前言

  前面讲到了二叉搜索树(BST)和二叉平衡树(AVL),二叉搜索树在最好的情况下搜索的时间复杂度为O(logn),但如果插入节点时,插入元素序列本身就是有序的,那么BST树就退化成一个线性表了,搜索的时间复杂度为O(n)。
  如果想要减少比较次数,就需要降低树的高度。在插入和删除节点时,要保证插入节点后不能使叶子节点之间的深度之差大于1,这样就能保证整棵树的深度最小,这就是AVL树解决BST搜索性能降低的策略。但由于每次插入或删除节点后,都可能会破坏AVL的平衡,而要动态保证AVL的平衡需要很多操作,这些操作会影响整个数据结构的性能,除非是在树的结构变化特别少的情形下,否则AVL树平衡带来的搜索性能提升有可能还不足为了平衡树所带来的性能损耗。
  因此,引入了2-3树来提升效率。2-3树本质也是一种平衡搜索树,但2-3树已经不是一棵二叉树了,因为2-3树允许存在3这种节点,3-节点中可以存放两个元素,并且可以有三个子节点。

2 2-3树定义

2-3树的定义

(1)2-3树要么为空要么具有以下性质:
(2)对于2-节点,和普通的BST节点一样,有一个数据域和两个子节点指针,两个子节点要么为空,要么也是一个2-3树,当前节点的数据的值要大于左子树中所有节点的数据,要小于右子树中所有节点的数据。
(3)对于3-节点,有两个数据域a和b和和三个子节点指针,左子树中所有的节点数据要小于a,中子树中所有节点数据要大于a而小于b,右子树中所有节点数据要大于b。

例如:图2.1所示的树为一棵2-3树,树中共有5个2-节点和3个3-节点。
图2.1

图2.1

3 2-3树性质

性质:

(1)对于每一个结点有1或者2个关键码。
(2)当节点有1个关键码的时,节点有2个子树。
(3)当节点有2个关键码时,节点有3个子树。
(4)所有叶子点都在树的同一层。

4 2-3树查找

2-3树的查找类似二叉搜索树的查找过程,根据键值的比较来决定查找的方向。

例如:在图2.1所示的2-3树中查找键为H的节点:

例如:在图2.1所示的2-3树中查找键为B的节点:

5 2-3树插入

5.1 插入

  在树的插入之前需要对待插入的节点key进行一次查找操作,若树中已经有此节点则不予插入,若没有查找到此节点,则记录未命中查找结束时访问的最后一个节点。空树的插入最简单,直接创建一个2-节点即可,这里不予赘述。
  对于非空树插入主要分为以下4种情况:

(1)向2-节点中插入新节点
(2)向一棵只含3-节点的树中插入新节点
(3)向一个父节点为2-节点的3-节点中插入新节点
(4)向一个父节点为3-节点的3-节点中插入新节点

5.2 向2-节点中插入新节点

  操作步骤:如果未命中查找结束于一个2-节点,直接将2-节点替换为一个3-节点,并将要插入的键保存在其中。
  例如:在图2.1所示的2-3树中插入K。
图解过程:
  (1)插入数据K,需要在树中查找是否包含K值。查找过程按照类似二叉搜索树的查找方式进行。

  (2)树中不包含数据K,查找失败,并记录查找结束位置为L节点,L节点为2-节点,直接插入数据K,并将2-节点变为3-节点,插入完成。

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

  操作步骤:向一棵只含3-节点的树中插入新节点,先临时将新键存入唯一的3-节点中,使其成为一个4-节点,再将它转化为一颗由3个2-节点组成的2-3树,分解后树高会增加1。
  例如:在3-节点中插入D。
图解过程:
  (1)图中的节点为3-节点,节点中包含A和F两个key,若要向节点中插入D,则需要创建临时4-节点,4-节点中包含A、D、F三个key。由于4-节点是不符合2-3树定义,因此需要执行节点分裂。

  (2)选择中间值D为父节点,小于D的key值A作为D的左子树,F作为右子树,执行节点分裂。

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

  操作步骤:先构造一个临时的4-节点并将其分解,分解时将中键移动到父节点中(中键移动后,其父节点中的位置由键的大小确定)
  例如:在图2.1所示2-3树中插入Z。
图解过程:
  (1)执行数据Z的查找过程,并记录最终的查找结束位置。查找结束位置为键值S和X所在节点,此节点为3-节点。

  (2)键值S和X构成的节点为3-节点,插入Z后构造临时4-节点,然后选择X为中间值,执行节点分裂。

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

  操作步骤:插入节点后一直向上分解构造的临时4-节点并将中键移动到更高层双亲节点,直到遇到一个-2节点并将其替换为一个不需要继续分解的3-节点,或是到达树根(3-节点)。
  例如:在图2.1所示的2-3树中插入D。
图解过程:

top Created with Sketch.