2-3查找树简介

在查找操作中,经常会用到二叉查找树,其最好的性能是O(logN),但是,由于输入的不同,所以一个查找二叉树会有各种不同的高度,最坏会导致查找退化到O(N),所以我们要想构造一种,无论输入是什么,都可以确保其运行时间是对数级别的二叉查找树.我们称其为平衡查找树,我们用得最多的是一种叫做红黑树,而2-3结点查找树也是一种平衡查找树,其思想与红黑树十分类似,概念上很好理解.

为了要保证树的平衡性,我们做出了一些妥协,允许一个节点有多个键.在2-3树中,一个节点最多可以有两个键,三个链接.每一个链接都对应其中保存的键所分割出来的一个区间.比如说我们有一个节点,键为 10 20 , 那么三个链接的区间就是x=20.其严格的定义如下

一颗完美平衡的2-3查找树中,所有叶子节点到根节点的距离都是相同的.

树的查找

我们首先来看一下这样的树是怎么进行查找的.根据定义,我们知道2-3树的每个节点要么有2个键,要么有一个键,当我们开始查找时,首先会与根节点的值进行比较,根据大小来确定往左节点还是右节点向下比较,当只有一个键时,比较过程与一般的二叉查找树一样,当有两个键的时候,会对这两个键进行两次比较以确定查找节点的区间,然后再根据对应的链接查找下一层的节点.如图所示

树的插入

对于这样的一颗树来说,根据当前节点和父节点的键数量不同,有几种插入的方法

向2-节点中插入

如果当前节点只有一个键的话,那么插入就十分简单,我们直接将这个新值作为当前节点的一个键加入进去,使这个节点成为3-节点即可.

向只有3-节点的树插入

如果有一个3-节点没有父节点,我们要向其插入新的节点时,会比上面的情况复杂一点.由于这个节点已经有两个键了,所以没有给其拓展的空间,我们可以为了方便,先将其插入到这个节点,使其变成一个4-节点.创建这个节点的原因是,4-节点很容易可以变成3个2-节点,中间的键作为两边的键的父节点即可.这样整个树的高度就会增加.这个插入的方法向我们说明了2-3树是怎么生长的

向父节点为2-节点的3-节点的树插入

这种情况又复杂了一点.这个情况下,如果我们想要插入的话,可以先将当前节点变为一个4-节点,然后将其中心键上移,使父节点变成了一个3-节点,左键为父节点的中间链接,右键为父节点的右链接

向父节点为3-节点的3-节点的树插入

遇到这种情况无疑是最复杂的了,无论是当前节点还是父节点,都已经没有了拓展的空间.所以我们只好从父节点的根节点继续向上找,直到遇到树的根节点或者一个2-结点为止.并且我们向上一层,就要重新对键的排布以及链接的指向进行重新排列.如果树的根节点是2-节点,并且之前都没有2-节点,那么我们最终会将键放入根节点,使其成为一个3-节点

如果树的根节点是一个3-节点,那么我们最终会将这个键放到根节点处,让根节点成为一个临时的4-节点,并使其生长,整个树的高度加一

分解4-节点

在2-3树中,最复杂的变换莫过于将临时的4-节点分解为2-节点和3-节点了.我们知道,将一个4-节点分解为2-3树可能会有6种情况,分别是当其为根节点,2-节点的左右节点和3-节点的左中右节点的时候.好在的是,分解4-节点是一种局部的操作,其分解不会影响全局树的结构.即不会影响树的全局有序和完美平衡性.如图所示,分解4-节点一般来说,就是向其父节点插值

当完成变换之后,并不会影响树的高度(根节点变换除外)

我们来看一下分解的6种情况分别是怎么做的

当然了,如果父节点是3-节点并且我们对其插值使其变成了4-节点后,它也要向上继续分解这个4-节点,但是依然在这6种情况以内,所以我们可以看到,2-3树与普通的二叉查找树不同的就是,2-3树其实是从下往上来生长的.由于其完美平衡的特性,确保了2-3树即使在最坏的输入下,也会有比较好的性能,并且每次插入中操作的节点数目都是一个比较小的常数,而且插入时,最多只会修改一条路径,确保了时间复杂度不超过O(logN).

一颗由随机键所构造的2-3树形状如下