DEV Community: Clement

Tree data structures in Rust with tree-ds (#3: Beyond The Basics)

Clement — Sat, 29 Jun 2024 18:08:57 +0000

In the previous parts, we went through the setup of the tree-ds crate and the features that the tree-ds crate offers out of the box when working with trees. In this section, we are going to explore the advanced features offered by the tree-ds crate as a whole.

Advanced Features

The tree-ds crate offers many more features.

Serialization and de-serialization support. The crate has a serde feature that enables serrialization and deserialization of trees and nodes. To enable the feature update the cargo dependency in Cargo.toml.

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

Hashing. The crate offers hashing support of the tree and nodes out of the box.
Thread safely. When interacting with trees across multiple threads you can enable the async feature in your Cargo.toml.

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

no_std support. You can use the tree-ds crate in environments that do not have the std library including embedded environments. To enable no-std support you can enable the no_std feature in you Cargo.toml.

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

Beyond the Basics

The tree-ds crate provides a solid foundation for working with trees in Rust. As you delve deeper, consider exploring these aspects:

Custom Data Types: Leverage the generic nature of the Tree struct to store custom data types in your nodes.
Error Handling: Integrate proper error handling for operations like insertion and searching to make your code more robust.
Advanced Implementations: Explore creating specialized trees like binary search trees (BSTs) using the functionalities offered by tree-ds as building blocks.

By understanding these concepts and leveraging the functionalities of tree-ds, you can effectively utilize trees in your Rust projects for various use cases.

Conclusion

The tree-ds crate offers a convenient and powerful way to work with trees in Rust. It provides a flexible and feature-rich foundation for building and manipulating tree structures in your applications. So, the next time you need a tree in your Rust project, consider giving tree-ds a try!

Tree data structures in Rust with tree-ds (#2: Tree Operations)

Clement — Sat, 29 Jun 2024 16:39:17 +0000

In the previous part, we explored how to get started with the tree-ds crate to work with tree data structures in rust. In this part, we are going to explore the various features and operations offered by the Tree struct.

Exploring the Features

tree-ds offers a variety of functionalities for working with your tree. Here are some key features:

Node Insertion: Insert nodes as descendants of a particular node. This is achieved by the add_node method:

use tree_ds::prelude::*;

let mut tree = Tree::new(Some("Tree Name"));
tree.add_node(Node::new(1, Some(20_000)), None)?;

The above snippet creates a tree and adds a root node.

Node(s) Removal: Remove nodes based on their node id. You can also specify how you want to handle the children of the node in question. If you decide to remove the node and its children, it is considered a pruning action. You can also decide to just remove the single node and attach the children to their grandparent.

use tree_ds::prelude::*;

let mut tree = Tree:new(Some("Tree name"));
let node_id = tree.add_node(Node::new(1, Some(20_000)), None)?;
tree.remove_node(&node_id, NodeRemovalStrategy::RemoveNodeAndChildren)?;

Traversal: The crate provides methods for in-order, pre-order, and post-order tree traversals, allowing you to visit and process nodes in a specific order.

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

let mut tree: Tree<i32, i32> = Tree::new(Some("Sample Tree"));
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_2))?;

let preordered_nodes = tree.traverse(TraversalStrategy::PreOrder, &node_1)?;

Getting a whole subsection of a tree. A subsection is a list of nodes that are descendants to a node. Think of it as a branch with nodes.

use tree_ds::prelude::{Node, Tree}

let mut tree: Tree<i32, i32> = Tree::new(Some("Sample Tree"));

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_2))?;

let subsection = tree.get_subtree(&node_2, None)?;

Grafting: Adding whole section of a tree or another tree onto a tree at a specified node.

use tree_ds::prelude::{Node, Tree, SubTree};

let mut tree: Tree<i32, i32> = Tree::new(Some("Sample Tree"));
let node_id = tree.add_node(Node::new(1, Some(2)), None)?;
let mut subtree = SubTree::new(Some("Sample Tree"));
let node_2 = subtree.add_node(Node::new(2, Some(3)), None)?;  subtree.add_node(Node::new(3, Some(6)), Some(&node_2))?;
tree.add_subtree(&node_id, subtree)?;

Searching: Search for nodes based on their value and retrieve them if found.
Enumerating the children and the ancestors of a node.
Getting the height, degree and depth of a node.

These features, along with many more, make tree-ds a well-equipped solution for building and manipulating trees in your Rust projects.

Conclusion

In this section we went through some of the features of the tree data structure offered by the tree-ds crate. The crate is actively maintained so it is a good option to consider when working with trees in rust.

Read The Next Post

Tree data structures in Rust with tree-ds (#1: Getting Started)

Clement — Sat, 22 Jun 2024 05:54:34 +0000

Trees are a fundamental data structure used across various applications. In Rust, building your own tree from scratch can be a great learning experience, but for production use, consider leveraging existing crates. In this three part series, we'll explore the tree-ds crate, a powerful tool for working with trees in your Rust projects.

Introducing `tree-ds`

The tree-ds crate, provides a versatile tree implementation in Rust. It offers a generic Tree struct that can hold any data type as its node value. The crate also supports various tree operations, making it a comprehensive solution for your tree-based needs.

Getting Started

To use tree-ds, add the following line to your Cargo.toml dependencies:

[dependencies]
tree-ds = "0.1"

Once you've added the dependency, you can start using the Tree struct in your code. The tree struct is defined as a generic type, Tree<Q, T>, where Q is the type of the node id and T is the type of the node value. Depending on your use case, you may want different types for the node Id. Optionally, trees can also be named by passing in the name when creating a new tree.

use tree_ds::prelude::*;

let mut tree = Tree::new(Some("Tree name"));

Nodes build up the tree. The Node type is a generic struct that can hold any arbitrary type of data for versatility. It is declared as Node<Q, T>. The Q and T types are passed from the tree type. You create a node by providing the node id and the optional value.

let node = Node::new("CEO", Some("John Doe"));

In some complex cases, manually specifying the id of every node becomes unfeasible especially since every node in the tree must have a unique id. In such cases, the auto_id feature flag saves the day.
In the Cargo.toml file, enable the auto_id feature.

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

To create a node with an auto generated id, you use the new_with_auto_id method:

let node = Node::new_with_auto_id(Some("Node Value"));

You then add nodes to the tree using the add_node method of the tree specifying the node to add and the optional id of the parent node. This method returns the id of the added node which makes it convenient to use.

use tree_ds::prelude::*;

let mut tree = Tree::new(Some("Corporate Structure"));
// This is the root node so we pass None to the parent_id arg.
let ceo_node = tree.add_node(Node::new("CEO", Some("John Doe")), None)?;
let cto_node = tree.add_node(Node::new("CTO", Some("Jane Doe")), Some(&ceo_node))?;
let cfo_node = tree.add_node(Node::new("CFO", Some("James Doe")), Some(&ceo_node))?;

println!("{}", tree);

This code snippet creates a new Tree with the name "Corporate Structure". We then insert three nodes, "ceo_node" as the root node, "cto_node" and "cfo_node" as children of the root node. Finally, we print the value of the tree.

Adding multiple root nodes results in an error.

Conclusion

In this section we went through getting started with the tree-ds crate, creating trees and nodes and adding nodes to the tree. In the next section we will explore the various operations you can perform on the tree.

Read The Next Post

DEV Community: Clement

Tree data structures in Rust with tree-ds (#3: Beyond The Basics)

Advanced Features

Beyond the Basics

Conclusion

Tree data structures in Rust with tree-ds (#2: Tree Operations)

Exploring the Features

Conclusion

Tree data structures in Rust with tree-ds (#1: Getting Started)

Introducing tree-ds

Getting Started

Conclusion

Introducing `tree-ds`