Tree-ds

This library provides a tree data structure that can be used to represent hierarchical data in Rust. The library allows you to perform the following operations on a tree:

• Enumerating all nodes in the tree
• Enumerating a section of the tree
• Finding a node in the tree
• Finding a section of the tree
• Adding a node to a certain position in the tree
• Removing a node from the tree
• Pruning a section of the tree
• Grafting a whole section of the tree onto another tree
• Finding the root of any node
• Finding the lowest common ancestor of two nodes

Why use this library?

There are many crates that make tree data structures available in Rust, but this library is unique in that it provides a tree data structure that is feature rich, easy to use and has a simple API. The library is also well-documented and has a comprehensive test suite that ensures that it works as expected. Most importantly, the library is designed to be fast and efficient, making it suitable for use in performance-critical applications.

Usage

Add the following to your Cargo.toml file:

[dependencies]
tree-ds = "0.1"

Nodes

The basic building block of the library is the Node struct. The Node struct is a generic struct that can hold any type of data. The Node struct can be created as follows:

use tree_ds::prelude::*;

let node: Node<String, i32> = Node::new("Root Node".to_string(), Some(100));

Optionally the crate provides an auto_id feature to automatically generate an id for the node. This is useful when you are not concerned with the id of the node, and you want to avoid the overhead of managing the Ids. To enable the auto_id feature, add the following to your Cargo.toml file:

[dependencies]
tree-ds = { version = "0.1", features = ["auto_id"] }

Then you can create a node as follows:

use tree_ds::prelude::*;

// Not that in this case, the `Q` type parameter should be of type `AutomatedId` or any other type that implements the `From<u128>` trait.
let node: Node<AutomatedId, &str> = Node::new_with_auto_id(Some("Some Node Value"));

Note: The node id generated in the no_std environment may not be unique across serializations and deserializations and disk persistence. This is because the no_std environment does not have access to the std::time module to generate unique ids. Instead it uses the SimpleGenerator from the sequential_gen crate to generate unique ids.

Trees

The Tree struct is the main struct that is used to represent a tree. The Tree struct is generic over the type of data that the nodes in the tree hold. The Tree struct can be created as follows:

use tree_ds::prelude::*;

let mut tree: Tree<String, i32> = Tree::new(Some("The Tree Name"));
// Proceed to build the tree by adding nodes to it.

A crude example of how to use the library is shown below:

use tree_ds::prelude::{Node, NodeRemovalStrategy, Result, Tree};

fn main() -> Result<()> {
	let mut tree = Tree::new(Some("Finances Tree"));
	let root = tree.add_node(Node::new("Risk".to_string(), Some(5000)), None)?;
	let fixed_income_node = tree.add_node(Node::new("Fixed Income".to_string(), Some(2000)), Some(&root))?;
	let equity_node = tree.add_node(Node::new("Equity".to_string(), Some(3000)), Some(&root))?;
	let debt_node = tree.add_node(Node::new("Debt".to_string(), Some(1000)), Some(&fixed_income_node))?;
	let mutual_funds_node = tree.add_node(Node::new("Mutual Funds".to_string(), Some(1000)), Some(&equity_node))?;
	let stocks_node = tree.add_node(Node::new("Stocks".to_string(), Some(2000)), Some(&equity_node))?;
	tree.add_node(Node::new("Debt Mutual Funds".to_string(), Some(500)), Some(&debt_node))?;
	tree.add_node(Node::new("Equity Mutual Funds".to_string(), Some(500)), Some(&mutual_funds_node))?;
	tree.add_node(Node::new("Large Cap Stocks".to_string(), Some(1000)), Some(&stocks_node))?;
	tree.add_node(Node::new("Mid Cap Stocks".to_string(), Some(1000)), Some(&stocks_node))?;
	tree.add_node(Node::new("Small Cap Stocks".to_string(), Some(1000)), Some(&stocks_node))?;

	println!("{}", tree);


	tree.remove_node(&stocks_node, NodeRemovalStrategy::RemoveNodeAndChildren)?;
	println!("After Removing The Stocks Node");
	println!("*******************");
	println!("{}", tree);


	let equity_sub_tree = tree.get_subtree(&equity_node, None)?;
	println!("{}", equity_sub_tree);
	Ok(())
}

This will output:

Finances Tree
*************
Risk: 5000
├── Fixed Income: 2000
│   └── Debt: 1000
│       └── Debt Mutual Funds: 500
└── Equity: 3000
    ├── Mutual Funds: 1000
    │   └── Equity Mutual Funds: 500
    └── Stocks: 2000
        ├── Large Cap Stocks: 1000
        ├── Mid Cap Stocks: 1000
        └── Small Cap Stocks: 1000

After Removing The Stocks Node
*******************
Finances Tree
*************
Risk: 5000
├── Fixed Income: 2000
│   └── Debt: 1000
│       └── Debt Mutual Funds: 500
└── Equity: 3000
    └── Mutual Funds: 1000
        └── Equity Mutual Funds: 500

Equity
******
Equity: 3000
└── Mutual Funds: 1000
    └── Equity Mutual Funds: 500

Traversal

You can traverse the tree using the traverse method. The traverse method returns an iterator that allows you to traverse the tree in any order you want. The following example shows how to traverse the tree in a pre-order fashion:

use tree_ds::prelude::{Node, Result, Tree, TraversalStrategy};

fn main() -> Result<()> {
	let mut tree = Tree::new(None);
	let node_1 = tree.add_node(Node::new(1, Some(2)), None)?;
	let node_2 = tree.add_node(Node::new(2, Some(3)), Some(&node_1))?;
	let node_3 = tree.add_node(Node::new(3, Some(6)), Some(&node_1))?;
	let node_4 = tree.add_node(Node::new(4, Some(5)), Some(&node_2))?;
	let node_5 = tree.add_node(Node::new(5, Some(6)), Some(&node_2))?;
	let node_6 = tree.add_node(Node::new(6, Some(7)), Some(&node_3))?;
	let preorder_nodes = tree.traverse(&node_1, TraversalStrategy::PreOrder)?;
	let expected_preorder = vec![node_1, node_2, node_4, node_5, node_3, node_6];
	assert_eq!(preorder_nodes, expected_preorder);

	let in_order_nodes = tree.traverse(&node_1, TraversalStrategy::InOrder)?;
	let expected_in_order = vec![node_4, node_2, node_5, node_1, node_3, node_6];
	assert_eq!(in_order_nodes, expected_in_order);

	let post_order_nodes = tree.traverse(&node_1, TraversalStrategy::PostOrder)?;
	let expected_post_order = vec![node_4, node_5, node_2, node_6, node_3, node_1];
	assert_eq!(post_order_nodes, expected_post_order);
	Ok(())
}

You can also perform an action on the nodes while traversing the tree on the iterator returned by the traverse method. The following example shows how to traverse the tree in a pre-order fashion and perform an action on the nodes:

let nodes = tree.traverse(&node_id, TraversalStrategy::PreOrder)?
    .iter()
    .map(|node| {
        println!("{}", node);
        node
    })
    .collect::<Vec<_>>();

no_std Environment

This crate supports no_std environments. To use this crate in a no_std environment, you need to enable the no_std feature. You can do this by adding the following to your Cargo.toml file:

[dependencies]
tree-ds = { version = "0.1", features = ["no_std"] }

All the other features are also equally supported in the no_std environment.

Roadmap

• Add support for more tree operations.
  • Add node rotation.
• Add a macro to create trees from a DSL.
• Add support for weighted nodes.

License

This project is licensed under the MIT License - see the LICENSE file for details.

Change Log

Check the CHANGELOG for the latest changes.