2-3 Trees


(C) Samuel L. Marateck, 1998, 2008

A 2-3 tree is an ordered tree that is always balanced . All additions are made at the leaf level and all the leaves are on the same level. A node can have at most two data items. If a third item is inserted, the node splits and the middle item (in an ordered sense) is inserted into the next highest level and the remaining two items become the descendants of the elevated item. The structure is defined as follows:

class Node
{
    Comparable info1, info2;
    Node left, middle, right, parent;
}
Each leaf has three null children.

Let's see how the construction works for the following items: k, a, t, u, r, c, e, m, and d. The first node holds ak. When the t is inserted, the items in order are a, k, t. Since there are three items to be placed in the node, the middle ordered item, k, becomes the parent of the other two:

         k
       /   \
     a      t

when the u is inserted, the tree becomes:

         k
       /   \
     a      tu
If the r is inserted, the right descendant would contain three items:
         k
       /   \
     a     r tu
However, a node can only contain two items, so the t is kicked upstairs and is placed in the same node as the k.
         k t
       /   |  \
     a    r    u
The insertion of the c makes it:
         k t
       /   |  \
    ac    r    u
If the e is inserted, the left descendant of kt would contains three items:
         k t
       /   |  \
    ace    r    u
so the node is split and c is sent to the parent node. But if the c were inserted there, the parent would contain three items. So the parent node is split, and the midlle item, k. becomes the parent of the other two:
               k
           /       \
        c            t
       /   \        /   \
    a       e    r      u
When the m and d are inserted, the tree becomes:
               k
           /       \
        c            t
       /   \        /   \
    a       de  mr      u