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²)-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

UPD: Fixed the code (insertion in a random order), based on the comment.

I recently implemented Treap, one of various kinds of binary search trees (BSTs), on Rust. It is a balanced BST, which means that it ensures that tree depth is always where n =  (the number of items in a tree). That is achieved by using randomisation. (For more details see Treap — Wikipedia.)

Experiments

Here are results of some experiments (UPD: these experiments themselves take O(n²)-time, because function depth() takes O(n)-time, which is called in each iteration.):

(1) Insertion of 10000 elements in the ascending order:
http://ideone.com/tSrw7u
It took 11.7 seconds to insert 30000 elements in the ascending order, and it got Time Limit Exceeded (>15.0sec) when the number of elements is >100000. You'll see that the depth of the treap increases in logarithmic speed.

(2) Insertion of 10000 elements in a random order:
http://ideone.com/pW7sBf
It took 15.011.8 seconds to insert 30000 elements in a random order. Like (1), the depth of the treap increases in logarithmic speed, too.

Here is a graph that indicates how the depth of the treap grows as the number of elements increases. The horizontal line shows the number of nodes in the treap and the vertical one shows the depth of the treap.

Conclusion

We have a balanced BST, whose depth is bounded by !
Unfortunately, a solution (25637342) to 785E - Anton and Permutation that uses this treap, which should work in -time, got the Time limit exceeded verdict. That seems because of its heavy constant factor, but I'm not sure.

References

The code I used in these experiments is avaliable at: https://github.com/koba-e964/contest/blob/906fcb07057b72496407b3c6e6a422e48e60dc6f/comm/Treap.rs
http://ideone.com/tSrw7u
http://ideone.com/pW7sBf

This implementation of treap largely depends on the slide (https://www.slideshare.net/iwiwi/2-12188757, written in Japanese) by iwiwi. This implementation of treap is verified by http://arc061.contest.atcoder.jp/submissions/1172709 (AtCoder ARC 061 D, problem statement is avaliable at http://arc061.contest.atcoder.jp/tasks/arc061_b ).