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 { char info1, info2; Node left, middle, right; }Each leaf has three null pointers.

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 tuIf the r is inserted, the right descendant would contain three items:

k / \ a r tuHowever, 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 uThe insertion of the c makes it:

k t / | \ ac r uWhen the e is inserted, the left descendant of kt would contain three items:

k t / | \ ace r uso 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 middle item, k, becomes the parent of the other two:

k / \ c t / \ / \ a e r uWhen the m and d are inserted, the final tree becomes:

k / \ c t / \ / \ a de mr u

Click here for original reference.