Module charcoal::binary_tree

This is supported on crate feature binary_tree only.

Trees which allow at most two children for their nodes.

The Wikipedia article on binary trees covers their use cases and specifics in more detail.

Both full binary trees and non-full ones are supported. The former ones allow strictly either zero or two children, the latter ones also allow one child to exist without the other one. If there is only one, it’s always treated as the left one, and removing the left child for a full branch will shift the right child into the position of the left one (implemented as a simple and very inexpensive key modification and does not actually move the elements themselves around).

Example

use charcoal::binary_tree::{BinaryTree, NodeRef};

// Create the tree. The only thing we need for that is the data payload for the root node. The
// turbofish there is needed to state that we are using the default storage method instead of
// asking the compiler to infer it, which would be impossible.
let mut tree = BinaryTree::<_>::new("Welcome".to_string());

// Let's now try to access the structure of the tree and look around.
let root = tree.root();
// We have never added any nodes to the tree, so the root does not have any children, hence:
assert!(root.is_leaf());

// Let's replace our reference to the root with a mutable one, to mutate the tree!
let mut root = tree.root_mut();
// First things first, we want to change our root's data payload:
*(root.value_mut().into_inner()) = "Hello".to_string();
// While we're at it, let's add some child nodes:
root.make_branch("World".to_string(), Some( "Rust".to_string() )).unwrap();

// Let's return to an immutable reference and look at our tree.
let root = NodeRef::from(root); // Conversion from a mutable to an immutable reference
assert_eq!(root.value().into_inner(), "Hello");
let (left_child, right_child) = root.children().unwrap();
assert_eq!(left_child.value().into_inner(), "World");
assert_eq!(right_child.value().into_inner(), "Rust");

Structs

BinaryTree	A binary tree.
Node	A node of a binary tree.
NodeRef	A reference to a node in a binary tree.
NodeRefMut	A mutable reference to a node in a binary tree.

Enums

MakeFullBranchError

The error type returned by NodeRefMut::make_full_branch.

Type Definitions

SparseVecBinaryTree	alloc A binary tree which uses a sparse Vec as backing storage.
VecBinaryTree	alloc A binary tree which uses a Vec as backing storage.