#tree #binary-search #indextree #memory-arena

woodland

Easy to use implementations of popular tree data structures such as Binary, Binary Search, AVL, Red-Black, and more

4 releases

0.0.4 May 13, 2021
0.0.3 May 13, 2021
0.0.2 May 8, 2021
0.0.1 May 8, 2021

#1216 in Data structures

MIT license

18KB
236 lines

woodland

Easy to use implementations of popular tree data structures such as Binary, Binary Search, AVL, Red-Black, and more.

All implementations use Arena based tree structures in order to avoid the mess that is accompanied when implementing graph-like structures in Rust. Not only is this mess avoided, but all of the tree implementations in woodland can be used in multi-threaded contexts.

The inner workings are heavily inspired by saschagrunert's indextree

What is an Arena / Index tree?

Instead of linking nodes together using pointers, we instead use an identifier (in our case, NodeId which references a key in a HashMap). This isn't very interesting in other languages, but it is particular interesting in Rust since it's very messy and difficult to implement a Tree using traditional design patterns.

The result is a faster and concurrent tree data structure, with a slightly different API that is still easy to use!

License

woodland uses the MIT license.

Attributions

Icons made by Freepik from www.flaticon.com

No runtime deps