Hi, everyone!

I recently implemented 2-3 tree, a balanced tree data structure, on Rust. The key feature of this tree is, that all the leaves are at the same depth. The implementation is available here: GitHub

## Implementation Details

2-3 tree data structure is represented by an enum with three constructors: `Tip`

, `Two`

and `Three`

. `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 `insert_sub()`

. `tree.insert_sub(x)`

inserts an element `x`

to a tree `tree`

, and returns either:

(1) `Ok(ret)`

, meaning `ret`

is the resulting tree, or

(2) `Err((t1, t2, val))`

, meaning that the resulting tree has an overcrowded node, so it must be split into two trees `t1`

, `t2`

, with the middle element `val`

moved up.

`insert()`

invokes `insert_sub()`

, and

(1) if the result was `Ok(ret)`

, returns `ret`

, or

(2) if the result was `Err((t1, t2, val))`

, returns `Two(_, val, t1, t2)`

.

## Experiments

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*(*n*^{2})-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 2^{d} - 1 nodes.) It is also worth noting that unlike experiments on treap, there is no decrease of depth in the random case.

## Conclusion

We have the 2-3 tree data structure, implemented on Rust!

## References

The code is available here: https://github.com/koba-e964/contest/blob/61af81645a9c1287e3302642696f4fb5e5db47fb/comm/TwoThreeTree.rs

http://ideone.com/62Seqz

http://ideone.com/6DHM21

The implementation was done with the aid of this slide: https://www.slideshare.net/sandpoonia/23-tree