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:
tree = ^node; node = record info1, info2 : char; left, middle, right : tree endEach leaf has three nil 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 uIf the e is inserted, the left descendant of kt would contains 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 midlle item, k. becomes the parent of the other two:
k / \ c t / \ / \ a e r uWhen the m and d are inserted, the tree becomes:
k / \ c t / \ / \ a de mr u