Java数据结构与算法解析(十)——2-3树

逃离我推掉我的手 2022-05-29 06:13 225阅读 0赞

#                          Java数据结构与算法解析(十)——2-3树 #

二叉查找树对于大多数情况下的查找和插入在效率上来说是没有问题的，但是他在最差的情况下效率比较低。平衡查找树的数据结构能够保证在最差的情况下也能达到lgN的效率，要实现这一目标我们需要保证树在插入完成之后始终保持平衡状态，这就是平衡查找树(Balanced Search Tree)。在一棵具有N 个节点的树中，我们希望该树的高度能够维持在lgN左右，这样我们就能保证只需要lgN次比较操作就可以查找到想要的值。不幸的是，每次插入元素之后维持树的平衡状态太昂贵。

2-3查找树(2-3 Search Tree)保证在最坏的情况下插入和查找效率都能保证在对数的时间复杂度内完成。

# 2-3查找树概述 #

2-3树是最简单的B-树（或-树）结构，其每个非叶节点都有两个或三个子女，而且所有叶都在统一层上。2-3树不是二叉树，其节点可拥有3个孩子。不过，2-3树与满二叉树相似。

和二叉树不一样，2-3树运行每个节点保存1个或者两个的值。对于普通的2节点(2-node)，他保存1个key和左右两个自己点。对应3节点(3-node)，保存两个Key，2-3查找树的定义如下：

1.  对于2节点，该节点保存一个key及对应value，以及两个指向左右节点的节点，左节点也是一个2-3节点，所有的值都比key要小，有节点也是一个2-3节点，所有的值比key要大。
2.  对于3节点，该节点保存两个key及对应value，以及三个指向左中右的节点。左节点也是一个2-3节点，所有的值均比两个key中的最小的key还要小；中间节点也是一个2-3节点，中间节点的key值在两个跟节点key值之间；右节点也是一个2-3节点，节点的所有key值比两个key中的最大的key还要大。
3.  一棵2-3查找树或为一颗空树，或由以下节点组成：   
    1)2-节点：含有一个键和两条链接，左链接指向的2-3树中的键都小于该节点，右链接指向的2-3树中的键都大于该节点。   
    2)3-节点：含有两个键和三条链接，左链接指向的2-3树中的键都小于该节点，中链接指向的2-3树中的键都位于该节点的两个键之间，右链接指向的2-3树中的键都大于该节点。

如果中序遍历2-3查找树，就可以得到排好序的序列。在一个完全平衡的2-3查找树中，根节点到每一个为空节点的距离都相同。   
![这里写图片描述][SouthEast]

# 查找 #

在进行2-3树的平衡之前，我们先假设已经处于平衡状态，我们先看基本的查找操作。

2-3树的查找和二叉查找树类似，要确定一个树是否属于2-3树，我们首先和其跟节点进行比较，如果相等，则查找成功；否则根据比较的条件，在其左中右子树中递归查找，如果找到的节点为空，则未找到，否则返回。查找过程如下图：

![这里写图片描述][SouthEast 1]

# 插入 #

对于2-3树的插入操作一般分为以下几种情况：   
1.往一个2-node节点插入新键。（树的初始态）   
2.向一棵只含有一个3-节点的树中插入新键。（树的初始态）   
3.向一个父节点为2-节点的3-节点中插入新键。（子树的分裂1）   
4.向一个父节点为3-节点的3-节点中插入新建。（子树的分类2）   
5.分解根节点。（树的向上生长态）

## 往一个2-node节点插入 ##

往2-3树中插入元素和往二叉查找树中插入元素一样，首先要进行查找，然后将节点挂到未找到的节点上。2-3树之所以能够保证在最差的情况下的效率的原因在于其插入之后仍然能够保持平衡状态。如果查找后未找到的节点是一个2-node节点，那么很容易，我们只需要将新的元素放到这个2-node节点里面使其变成一个3-node节点即可。但是如果查找的节点结束于一个3-node节点，那么可能有点麻烦。

![这里写图片描述][SouthEast 2]

## 往一个3-node节点插入 ##

往一个3-node节点插入一个新的节点可能会遇到很多种不同的情况，下面首先从一个最简单的只包含一个3-node节点的树开始讨论。

操作1：只包含一个3-node节点   
![这里写图片描述][SouthEast 3]

如上图，假设2-3树只包含一个3-node节点，这个节点有两个key，没有空间来插入第三个key了，最自然的方式是我们假设这个节点能存放三个元素，暂时使其变成一个4-node节点，同时他包含四个子节点。然后，我们将这个4-node节点的中间元素提升，左边的节点作为其左节点，右边的元素作为其右节点。插入完成，变为平衡2-3查找树，树的高度从0变为1。

操作2：父节点：2-节点，子节点：3-节点   
和第一种情况一样，我们也可以将新的元素插入到3-node节点中，使其成为一个临时的4-node节点，然后，将该节点中的中间元素提升到父节点即2-node节点中，使其父节点成为一个3-node节点，然后将左右节点分别挂在这个3-node节点的恰当位置。操作如下图：

![这里写图片描述][SouthEast 4]

操作3：父节点：3-节点，子节点：3-节点   
当我们插入的节点是3-node的时候，我们将该节点拆分，中间元素提升至父节点，但是此时父节点是一个3-node节点，插入之后，父节点变成了4-node节点，然后继续将中间元素提升至其父节点，直至遇到一个父节点是2-node节点，然后将其变为3-node，不需要继续进行拆分。

![这里写图片描述][SouthEast 5]

此处子节点分裂后，把一个元素加入到了它的父节点，但也超过了父节点的存储能力，所以还要继续向上分裂，直到有容下它的父节点。

上述操作2和操作3是不会影响树的深度的，正影响树的深度的情况是：只有当根节点为3-节点时，此时有元素插入沉底后，不断向上裂变，很不幸如果影响到根节点。也就是下面根节点分裂的情况。

根节点分裂   
当根节点到子节点都是3-node节点的时候，这是如果我们要在字节点插入新的元素的时候，会一直查分到跟节点，在最后一步的时候，跟节点变成了一个4-node节点，这个时候，就需要将跟节点查分为两个2-node节点，树的高度加1，这个操作过程如下：

![这里写图片描述][SouthEast 6]

本地转换   
将一个4-node拆分为2-3node涉及到6种可能的操作。这4-node可能在跟节点，也可能是2-node的左子节点或者右子节点。或者是一个3-node的左，中，右子节点。所有的这些改变都是本地的，不需要检查或者修改其他部分的节点。所以只需要常数次操作即可完成2-3树的平衡。

![这里写图片描述][SouthEast 7]

性质   
这些本地操作保持了2-3树的平衡。对于4-node节点变形为2-3节点，变形前后树的高度没有发生变化。只有当跟节点是4-node节点，变形后树的高度才加一。如下图所示：

![这里写图片描述][SouthEast 8]

## 分析 ##

完全平衡的2-3查找树如下图，每个根节点到叶子节点的距离是相同的：   
![这里写图片描述][SouthEast 9]

2-3树的查找效率与树的高度是息息相关的:   
1.在最坏的情况下，也就是所有的节点都是2-node节点，查找效率为lgN   
2.在最好的情况下，所有的节点都是3-node节点，查找效率为log3N约等于0.631lgN

距离来说，对于1百万个节点的2-3树，树的高度为12-20之间，对于10亿个节点的2-3树，树的高度为18-30之间。

对于插入来说，只需要常数次操作即可完成，因为他只需要修改与该节点关联的节点即可，不需要检查其他节点，所以效率和查找类似。下面是2-3查找树的效率：

![这里写图片描述][SouthEast 10]

最后贴上一张2-3树的构造过程：   
![这里写图片描述][SouthEast 11]

[SouthEast]: /images/20220529/71fab53f857a4f07ab50e13ee6753ae4.png
[SouthEast 1]: /images/20220529/26dbc1124e79495090028680b2687779.png
[SouthEast 2]: /images/20220529/d84d11ef49894ba0bdb057acf835b353.png
[SouthEast 3]: /images/20220529/e8a6ad2af6804c53840e20baf8a2d862.png
[SouthEast 4]: /images/20220529/51ce1393aff54238ba002cbaf22f72c7.png
[SouthEast 5]: /images/20220529/97666f171ebe43f1a662c606b2f200fe.png
[SouthEast 6]: /images/20220529/699e489e72394ce9b958150b615fd317.png
[SouthEast 7]: /images/20220529/c98331fda4db4bd49532c6d33843e699.png
[SouthEast 8]: /images/20220529/2562f465f5bb4ab4a264994a0fb16f25.png
[SouthEast 9]: /images/20220529/2cf60d8efa9446d1a14651f7396ef095.png
[SouthEast 10]: /images/20220529/2f4f6a36160347f0a4447553283ecf1e.png
[SouthEast 11]: /images/20220529/980bae1543de42879c51c0213223315d.png