2-3 tree data structure is represented by an enum with three constructors:
Tip is a leaf, with no elements inside.
Two is a node with one element and two children, and
Three is a node with two elements and three children.
The current implementation supports
insert() operation only. It uses a helper function, named
tree.insert_sub(x) inserts an element
x to a tree
tree, and returns either:
ret is the resulting tree, or
Err((t1, t2, val)), meaning that the resulting tree has an overcrowded node, so it must be split into two trees
t2, with the middle element
val moved up.
(1) if the result was
(2) if the result was
Err((t1, t2, val)), returns
Two(_, val, t1, t2).
Two kinds of experiments were conducted. 1 million elements were inserted into a 2-3 tree, (1) in the ascending order and (2) in a random order. In each iteration, the depth of the 2-3 tree is checked, and if there is a change, the new depth is displayed. The experiment itself took -time, because the depth of a 2-3 tree can be calculated by checking its leftmost leaf only. (Experiments of treap took O(n2)-time.)
(1) in the ascending order: http://ideone.com/62Seqz
(2) in a random order: http://ideone.com/6DHM21
Here is a graph that illustrates how the depth grows as elements are inserted. The horizontal line shows the number of nodes in the 2-3 tree and the vertical one shows the depth of the 2-3 tree.
Note that one has not only an asymptotic upper bound of the depth, but also a strict upper bound . That is because all the leaves of the 2-3 tree are at the same depth. (From this property, it can be shown that a 2-3 tree of depth d has at least 2d - 1 nodes.) It is also worth noting that unlike experiments on treap, there is no decrease of depth in the random case.
We have the 2-3 tree data structure, implemented on Rust!
The implementation was done with the aid of this slide: https://www.slideshare.net/sandpoonia/23-tree