Crate woodland[][src]

Expand description

Note: this project is still in development!

The API is subject to change (aka: it’ll be easier to use by the first release!)

Easy to use implementations of popular tree data structures such as binary_tree::BinaryTree, [AVLTree], [RedBlackTree], 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 an key in a std::collections::HashMap). This isn’t very interesting in other languages, but it is particularly interesting in Rust since it’s very messy and difficult to implement tree’s 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!

How to use

Each tree (such as binary_tree::BinaryTree) contains an example code block to get started

Modules

binary_tree

Implementation of a simple Binary Tree, which has no invariants to maintain.

prelude

The prelude is a collection of all the traits in this crate

Structs

NodeId

A unique identifier for any node in a tree.