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:

2-3 tree使用

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.

浪费了存储空间。

The 2-3 tree tries to solve this by using a different structure and slightly different adding and removing procedure to help keep the tree more or less balanced. The biggest drawback with the 2-3 tree is that it requires more storage space than the normal binary search tree.

The 2-3 tree is called such because the maximum possible number of children each node can have is either 2 or 3. This makes the tree a bit more complex, so I will try to explain as much as possible.

One big difference with the 2-3 tree is that each node can have up to two data fields. You can see the three children extending from between the two data fields.

2-3 tree使用

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

一个节点包含一个或者两个关键码；

每个内部节点有2个子女（如果它包含一个关键码），或者3个子女（包含2个关键码）；

所有叶子节点在树的同一层，因此树总是高度平衡的。

2-3树每一个节点的左子树中所有后继节点的值都小于其父节点第一个关键码的值；

而中间子树所有后继节点的值都大于或等于其父节点第一个关键码的值而小于第二个关键码的值；

如果有右子树，则右子树所有后继节点都大于或等于其父节点第二个关键码的值。

2-3树节点定义：

struct node {

int lkey,rkey,Numkeys;

struct node *left,*center,*right;

};

（转自http://baike.baidu.com/link?url=uLn9rjdrcao-itw7tbYdsExJCnmvVXaSxhjYrxSMq4azcDtc39EWYizn03ZUADfqCTq6MzjrASVaI7tRL5wI6K）

Thus, the tree is set up in the following manner:

The node must always have a first field (data 1 in the diagram ), but not necessarily a second field (data 2). If both fields are present in a node, the first (or left) field of the node is always less than the second (or right) field of the node.
Each node can have up to three child nodes, but if there is only one data field in the node, the node cannot have more than two children.
The child nodes are set so that data in the first sub-tree is less than the first data field, the data of the second sub-tree is greater than the first data field and less than the second data field, and the data of the third sub-tree is greater than the second data field. If there is only one data field in the node, use the first and second children only.
All leaf nodes appear on the last level.

Now, take a look at the implementation of a 2-3 tree:

class twoThreeTree {

  public:

    twoThreeTree(void);      // Constructor

    ~twoThreeTree(void);     // Destructor

    void add(int item);      // Adds an item

    void search(int item);   //

    Searches for an item

  private:

    twoThreeNode *root;      // Pointer to root node

    // Private helper functions go here

};

class twoThreeNode {

  public:

    int firstData, secondData; // Two data fields

    // The three child nodes

    twoThreeNode *first, *second, *third;

    // This next one is quite useful. It aids

    // moving around the tree. It is a pointer

    // to the parent of the current node.

    twoThreeNode *parent;

};

You can see that this tree, unlike the binary search tree or the heap tree, has no remove() function. It is possible to program a remove function, but it generally isn't worth the time or the effort.

This tree will be a bit harder to implement than the binary search tree just because of the complexity of the node. Still, the add() function algorithm isn'tthat difficult, and a step-by-step progression through the algorithm helps enormously.

First, to add an item, find the place in the tree for it. This is very much the same as in the binary search tree: just compare and move down the correct link until leaf node is reached.

Once at the leaf node, there are three basic cases for the add() function:

The leaf node has only one data item: this case is very simple. Just insert the new item after this item or shift the old item forward and insert the new item before the old one, depending on the situation.
The leaf node is full and the parent node has only one data item: this case is also quite simple. Compare the three values: the two leaf node items and the new item. Choose the middle one and insert it in the parent node where appropriate.
If the leaf node is the left child, shift the old data in the parent node to the right and insert the middle value in the parent node before the old data.Make sure to shift the pointers to the children in the parent node! If the leaf is the right child, just insert the middle value to the right of the old value in the parent node. The two left-over values from the comparison become two leaf nodes, one as the second child, and one as the first or third child depending on the situation.
Both the leaf node and the parent node are full: this situation is the most complex of all. In the same manner as Case 2, promote the middle value of the leaf node. Then, continue doing the same thing with the parent node, and so on until the situation is resolved or the root node is reached. In this case, the middle value is promoted once again, except a new root node is created from the middle value and the two other values become the left and right subtrees of the new root. At the leaf node at which we began, the new level allows us to split the three initial values into a three node sub-tree of the parent node, and so on.

Doing a few small 2-3 trees by hand helps to understand this algorithm. Remember to check and hold to the rules governing the 2-3 tree! It can get ugly if they are ignored, especially with the last one.

Using some recursive helper functions as well as that miraculous parent variable will help ease the pain of programming this tree.

转自：http://www.cprogramming.com/tutorial/computersciencetheory/twothree.html

发现前面说的比较啰嗦，看wikipedia一目了然http://en.wikipedia.org/wiki/2%E2%80%933_tree

2-3tree有两种形式:

2-3 tree使用

查找：

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

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

2-3 tree使用

插入

往一个2-node节点插入

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

2-3 tree使用

往一个3-node节点插入

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

只包含一个3-node节点

2-3 tree使用

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

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

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

2-3 tree使用