2-3 Trees in C and C++By Eric Suh 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. 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. Thus, the tree is set up in the following manner:
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't that 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:
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. |