Please read the new rule regarding the restriction on the use of AI tools. ×

2-3 tree on Rust

Revision en1, by kobae964, 2017-04-25 19:04:02

Hi everyone!

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

Features

The current implementation supports insert() operation only.

Experiments

Two kinds of experiments were conducted. 1 million elements were inserted to a 2-3 tree, (1) in the ascending order and (2) in a random order.

(1) in the ascending order: http://ideone.com/62Seqz

(2) in a random order: http://ideone.com/6DHM21

Conclusion

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

Tags rust, b-trees, balanced, experiment

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en7 English kobae964 2017-04-25 20:22:57 43
en6 English kobae964 2017-04-25 20:20:56 15 Tiny change: 't unlike [treap](htt' -> 't unlike [experiments on treap](htt'
en5 English kobae964 2017-04-25 20:19:17 9 on Rust
en4 English kobae964 2017-04-25 20:18:12 341 Add ref to treap experiments (published)
en3 English kobae964 2017-04-25 20:07:53 420 Add graph
en2 English kobae964 2017-04-25 19:33:02 1140 Implementation details
en1 English kobae964 2017-04-25 19:04:02 1126 Skeleton (saved to drafts)