2-3 tree on Rust - Codeforces

#	User	Rating
1	tourist	4009
2	jiangly	3831
3	Radewoosh	3646
4	jqdai0815	3620
4	Benq	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	gamegame	3386
10	ksun48	3373

#	User	Contrib.
1	cry	164
1	maomao90	164
3	Um_nik	163
4	atcoder_official	160
5	-is-this-fft-	158
6	awoo	157
7	adamant	156
8	TheScrasse	154
8	nor	154
10	Dominater069	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.