数据结构之 2-3 Tree

From cnblogs yangecnu / cnblogs 有心故我在 / wikipedia 2-3 tree

---

定义

The 2-3 tree is also a search tree like the binary search tree, but this tree tries to solve the problem of the unbalanced tree.
Imagine that you have a binary tree to store your data. The worst possible case for the binary tree is that all of the data is entered in order. Then the tree would look like this:

This tree has basically turned into a linked list. This is definitely a problem, for with a tree unbalanced like this, all of the advantages of the binary search tree disappear: searching the tree is slow and cumbersome, and there is much wasted memory because of the empty left child pointers.

In computer science, a 2–3 tree is a tree data structure, where every node with children internal node has either two children (2-node) and one data element or three children (3-nodes) and two data elements. According to Knuth, "a B-tree of order 3 is a 2-3 tree." Nodes on the outside of the tree leaf nodes have no children and one or two data elements. 2−3 trees were invented by John Hopcroft in 1970.

2–3 trees are balanced, meaning that each right, center, and left subtree contains the same or close to the same amount of data.

<Wikipedia>
We say that an internal node is a 2-node if it has one data element and two children.
We say that an internal node is a 3-node if it has two data elements and three children.
We say that T is a 2–3 tree if and only if one of the following statements hold:

• T is empty. In other words, T does not have any nodes.
• T is a 2-node with data element a. If T has left child L and right child R, then
  　　L and R are non-empty 2–3 trees of the same height;
  　　a is greater than each element in L; and
  　　a is less than or equal to each data element in R.
• T is a 3-node with data elements a and b, where a < b. If T has left child L, middle child M, and right child R, then
  　　L, M, and R are non-empty 2–3 trees of equal height;
  　　a is greater than each data element in L and less than or equal to each data element in M; and
  　　b is greater than each data element in M and less than or equal to each data element in R.

一棵2-3树具有下例性质：

• 一个节点包含一个或者两个关键码；
• 每个内部节点有2个子女（如果它包含一个关键码），或者3个子女（包含2个关键码）；
• 所有叶子节点在树的同一层，因此树总是高度平衡的。
• 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还要大。

如果中序遍历2-3查找树，就可以得到排好序的序列。在一个完全平衡的2-3查找树中，根节点到每一个为空节点的距离都相同。

查找

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

插入

二、往一个3-node节点插入

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

(1)只包含一个3-node节点

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

(2)节点是3-node，父节点是2-node

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

(3)节点是3-node，父节点也是3-node

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

(4)根节点分裂

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

(5)本地转换

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

(6)性质

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

分析

完全平衡的2-3查找树如下图，每个根节点到叶子节点的距离是相同的：

2-3树的查找效率与树的高度是息息相关的。

• 在最坏的情况下，也就是所有的节点都是2-node节点，查找效率为lgN

• 在最好的情况下，所有的节点都是3-node节点，查找效率为log3N约等于0.631lgN
  距离来说，对于1百万个节点的2-3树，树的高度为12-20之间，对于10亿个节点的2-3树，树的高度为18-30之间。
  　　对于插入来说，只需要常数次操作即可完成，因为他只需要修改与该节点关联的节点即可，不需要检查其他节点，所以效率和查找类似。下面是2-3查找树的效率：

  
  

实现

直接实现2-3树比较复杂，因为：
1.需要处理不同的节点类型，非常繁琐
2.需要多次比较操作来将节点下移
3.需要上移来拆分4-node节点
4.拆分4-node节点的情况有很多种

2-3查找树实现起来比较复杂，在某些情况插入后的平衡操作可能会使得效率降低。在2-3查找树基础上改进的红黑树不仅具有较高的效率，并且实现起来较2-3查找树简单。