2-3 tree on Rust - Codeforces

#	User	Rating
1	tourist	3993
2	jiangly	3743
3	orzdevinwang	3707
4	Radewoosh	3627
5	jqdai0815	3620
6	Benq	3564
7	Kevin114514	3443
8	ksun48	3434
9	Rewinding	3397
10	Um_nik	3396

#	User	Contrib.
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

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 $\text{[math]}$ -time, because the depth of a 2-3 tree can be calculated by checking its leftmost leaf only. (Experiments of treap took O(n²)-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 $\text{[math]}$ of the depth, but also a strict upper bound $\text{[math]}$ . 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.