Struct BTree

Source

pub struct BTree<T, const N: usize> {
    pub l_nodes: Array<isize, N>,
    pub r_nodes: Array<isize, N>,
    pub values: Array<T, N>,
}

Expand description

Statically sized binary tree representation for fast traversal, suitable for dense trees. Special implementation for binary tree is offered for faster traversal times over the generalized k tree, where an array of arrays and indices checks happen.

Fields§

§l_nodes: Array<isize, N>§r_nodes: Array<isize, N>§values: Array<T, N>

Implementations§

Source §

impl<T, const N: usize> BTree<T, N>

Source

pub fn new(l_nodes: [isize; N], r_nodes: [isize; N], values: [T; N]) -> Self

Constructs a new tree from array representation

§Examples

        use treesome::sized::BTree;
        let left = [1, 3, 5, -1, -1, -1, -1];
        let right = [2, 4, 6, -1, -1, -1, -1];
        let values = [10, 51, 36, 90, 32, 16, 5];
        let tree = BTree::new(left, right, values);

Source

pub fn is_leaf_node(&self, node_id: usize) -> bool

True if given node_id is a leaf node (no children), false otherwise.

Source

pub fn children(&self, node_id: usize) -> Children

Returns left and right child of a node. The value of -1 means no child in that direction.

§Examples

        use treesome::sized::BTree;
        let left = [1, 3, 5, -1, -1, -1, -1];
        let right = [2, 4, 6, -1, -1, -1, -1];
        let values = [10, 51, 36, 90, 32, 16, 5];
        let tree = BTree::new(left, right, values);
        assert_eq!(tree.children(0), (1, 2).into());

Source

pub fn parent(&self, node_id: isize) -> Option<isize>

Return’s node_id of its parent, if it exists. If there’s no parent (root node, non-existent node_id) for given node, None is returned. Computational complexity of the lookup is O(1), as the formula used calculates the exact position of the parent node.

§Examples

        use treesome::sized::BTree;
        let left = [1, 3, 5, -1, -1, -1, -1];
        let right = [2, 4, 6, -1, -1, -1, -1];
        let values = [10, 51, 36, 90, 32, 16, 5];
        let tree = BTree::new(left, right, values);

        assert_eq!(tree.parent(0), None);
        assert_eq!(tree.parent(3).unwrap(), 1);