Trait outils::tree::bst::BalancedBinaryForest

pub trait BalancedBinaryForest<V, Ix = DefaultIndexType> where
    V: ValueType,
    Ix: IndexType, {
    fn insert(&mut self, value: V) -> NodeIndex<Ix>;
    fn remove(&mut self, node: NodeIndex<Ix>) -> Option<V>;
    fn split(
        &mut self, 
        node: NodeIndex<Ix>, 
        dir: BstDirection
    ) -> (Option<NodeIndex<Ix>>, Option<NodeIndex<Ix>>);
    fn split_all(
        &mut self, 
        node: NodeIndex<Ix>, 
        size_hint: Option<usize>
    ) -> Vec<NodeIndex<Ix>>;
    fn append(
        &mut self, 
        node_u: NodeIndex<Ix>, 
        node_v: NodeIndex<Ix>
    ) -> Option<NodeIndex<Ix>>;
}

This trait defines the fundamental operations of a balanced binary forest.

The main difference between a BinarySearchTree and a BalancedBinaryForest is that the order of the latter is not determined by means of search keys associated to the nodes of the tree. Rather, the order is solely determined by the in-order of the nodes which is under control of the user.

Not using dedicated search keys enables this data structure to provide efficient operations to split and concatenate the sequences represented by the forest trees. The usage of search keys would require a significant number of insert and delete operation in order to split or concatenate trees, while without search keys only re-balancing is required.

Required methods

fn insert(&mut self, value: V) -> NodeIndex<Ix>

Inserts value into the forest as a new singleton (i.e. sole leaf) node.

fn remove(&mut self, node: NodeIndex<Ix>) -> Option<V>

Removes the tree node indexed by node, returning its content in case of a valid index.

fn split(
    &mut self,
    node: NodeIndex<Ix>,
    dir: BstDirection
) -> (Option<NodeIndex<Ix>>, Option<NodeIndex<Ix>>)

Splits the sequence of tree nodes represented by the forest tree containing the tree node indexed by node.

If dir == BstDirection::Left, node will index the last tree node of the left sequence, while if dir == BstDirection::Right, node will index the first tree node of the right sequence (both with respect to in-order). The roots of the resulting sequences will be returned as a tuple.

fn split_all(
    &mut self,
    node: NodeIndex<Ix>,
    size_hint: Option<usize>
) -> Vec<NodeIndex<Ix>>

Splits the whole sequence of tree nodes represented by the forest tree containing the tree node indexed by node into singleton (i.e. sole leaf) nodes.

If the tree nodes to be split is known beforehand, it can be specified optionally as the size_hint of the returned Vec containing the split tree nodes.

Generally, this operation will be much faster than calling split on each node of the sequence separately, the reason being that no re-balancing is necessary when it is known beforehand that every tree node will be split.

fn append(
    &mut self,
    node_u: NodeIndex<Ix>,
    node_v: NodeIndex<Ix>
) -> Option<NodeIndex<Ix>>

Concatenate the sequences of tree nodes represented by the forest trees containing the tree nodes indexed by node_u and node_v, respectively.

With respect to in-order, the former sequence will represent the smaller part of the new sequence, the latter sequence the bigger part. The root of the resulting sequence will be returned.

Loading content...

Implementors

impl<V> BalancedBinaryForest<V, usize> for AaForest<V> where
    V: ValueType, 

fn insert(&mut self, value: V) -> NodeIndex

fn remove(&mut self, node: NodeIndex) -> Option<V>

Removes the tree node indexed by node from the tree if present, in this case returning the associated value.

use outils::prelude::*;                             // The resulting tree is shown below:
use outils::tree::traversal::BinaryInOrderValues;   //
                                                    //       -- (3) --
let mut aaforest = AaForest::new(10);               //      /         \
                                                    //    (1)         (5)
let mut indices = Vec::new();                       //   /   \       /   \
indices.push(aaforest.insert(0));                   // (0)   (2)    (4)   (6)

for i in 1..7 {
    indices.push(aaforest.insert(i));
    aaforest.append(indices[i-1], indices[i]);
}

assert_eq!(aaforest.remove(indices[5]), Some(5));
let seq: Vec<&usize> = BinaryInOrderValues::new(&aaforest, indices[0]).collect();
assert_eq!(seq, vec![&0, &1, &2, &3, &4, &6]);

fn split(
    &mut self,
    node: NodeIndex,
    dir: BstDirection
) -> (Option<NodeIndex>, Option<NodeIndex>)

Splits the sequence of tree nodes represented by the forest tree containing the tree node indexed by node.

If dir == BstDirection::Left, node will index the last tree node of the left sequence, while if dir == BstDirection::Right, node will index the first tree node of the right sequence (both with respect to in-order). The roots of the resulting sequences will be returned as a tuple.

use outils::prelude::*;                             // The resulting trees are shown below:
use outils::tree::traversal::BinaryInOrderValues;   //
                                                    //       -- (3) --
let mut aaforest1 = AaForest::new(10);              //      /         \
let mut aaforest2 = AaForest::new(10);              //    (1)         (5)
                                                    //   /   \       /   \
let mut indices1 = Vec::new();                      // (0)   (2)    (4)   (6)
indices1.push(aaforest1.insert(0));
let mut indices2 = Vec::new();
indices2.push(aaforest2.insert(0));

for i in 1..7 {
    indices1.push(aaforest1.insert(i));
    aaforest1.append(indices1[i-1], indices1[i]);
    indices2.push(aaforest2.insert(i));
    aaforest2.append(indices2[i-1], indices2[i]);
}

// Split the tree at 3 and keep 3 as part of the left (i.e. _smaller_) tree.
let result1 = aaforest1.split(indices1[3], BstDirection::Left);
match(result1) {
    (Some(left), Some(right)) => {
        let seq_left: Vec<&usize> = BinaryInOrderValues::new(&aaforest1, left).collect();
        assert_eq!(seq_left, vec![&0, &1, &2, &3]);
        let seq_right: Vec<&usize> = BinaryInOrderValues::new(&aaforest1, right).collect();
        assert_eq!(seq_right, vec![&4, &5, &6]);
    }
    _ => {
        panic!("3 was neither first nor last, so the returned tuple should be (Some, Some)")
    }
}

// Split the tree at 3 and keep 3 as part of the right (i.e. _bigger_) tree.
let result2 = aaforest2.split(indices2[3], BstDirection::Right);
match(result2) {
    (Some(left), Some(right)) => {
        let seq_left: Vec<&usize> = BinaryInOrderValues::new(&aaforest2, left).collect();
        assert_eq!(seq_left, vec![&0, &1, &2]);
        let seq_right: Vec<&usize> = BinaryInOrderValues::new(&aaforest2, right).collect();
        assert_eq!(seq_right, vec![&3, &4, &5, &6]);
    }
    _ => {
        panic!("3 was neither first nor last, so the returned tuple should be (Some, Some)");
    }
}

fn split_all(
    &mut self,
    node: NodeIndex,
    size_hint: Option<usize>
) -> Vec<NodeIndex>

Splits the whole sequence of tree nodes represented by the forest tree containing the tree node indexed by node into singleton (i.e. sole leaf) nodes.

If the tree nodes to be split is known beforehand, it can be specified optionally as the size_hint of the returned Vec containing the split tree nodes.

Generally, this operation will be much faster than calling split on each node of the sequence separately, the reason being that no re-balancing is necessary when it is known beforehand that every tree node will be split.

use outils::prelude::*;                // The resulting tree is shown below:
                                       //
let mut aaforest = AaForest::new(10);  //       -- (3) --
                                       //      /         \
let mut indices = Vec::new();          //    (1)         (5)
indices.push(aaforest.insert(0));      //   /   \       /   \
                                       // (0)   (2)    (4)   (6)
for i in 1..7 {
    indices.push(aaforest.insert(i));
    aaforest.append(indices[i-1], indices[i]);
}

let split_nodes = aaforest.split_all(indices[0], Some(7));
assert_eq!(split_nodes.len(), indices.len());

// After splitting the forest tree, every one of its former nodes should be a singleton:
for i in 0..7 {
    assert!(split_nodes.contains(&indices[i]));
    assert_eq!(aaforest.parent(indices[i]), None);
    assert_eq!(aaforest.child(indices[i], 0), None);
    assert_eq!(aaforest.child(indices[i], 1), None);
}

fn append(&mut self, node_u: NodeIndex, node_v: NodeIndex) -> Option<NodeIndex>

Concatenate the sequences of tree nodes represented by the forest trees containing the tree nodes indexed by node_u and node_v, respectively.

With respect to in-order, the former sequence will represent the smaller part of the new sequence, the latter sequence the bigger part. The root of the resulting sequence will be returned.

use outils::prelude::*;
use outils::tree::traversal::BinaryInOrderValues;
let mut aaforest = AaForest::new(10);

// Insert values into the forest - each value will be a single-node tree in the forest.
let mut indices = Vec::new();
for i in 0..7 {
    indices.push(aaforest.insert(i));
}

// Construct the _smaller_ tree, containing the in-order sequence 0,1,2,3
let mut left = indices[0];
left = aaforest.append(left, indices[1]).expect("Result should not be None");
left = aaforest.append(left, indices[2]).expect("Result should not be None");
left = aaforest.append(left, indices[3]).expect("Result should not be None");

{ // Restrict scope of the borrow of `aaforest`.
    let seq: Vec<&usize> = BinaryInOrderValues::new(&aaforest, left).collect();
    assert_eq!(seq, vec![&0, &1, &2, &3]);
}

// Construct the _bigger_ tree, containing the in-order sequence 4,5,6
let mut right = indices[4];
right = aaforest.append(right, indices[5]).expect("Result should not be None");
right = aaforest.append(right, indices[6]).expect("Result should not be None");

{ // Restrict scope of the borrow of `aaforest`.
    let seq: Vec<&usize> = BinaryInOrderValues::new(&aaforest, right).collect();
    assert_eq!(seq, vec![&4, &5, &6]);
}

// Link left and right, constructing the in-order sequence 0,1,2,3,4,5,6.
let root = aaforest.append(left, right).expect("Result should not be None");
let seq: Vec<&usize> = BinaryInOrderValues::new(&aaforest, root).collect();
assert_eq!(seq, vec![&0, &1, &2, &3, &4, &5, &6]);

impl<V, W> BalancedBinaryForest<V, usize> for WeightedAaForest<V, W> where
    V: ValueType,
    W: WeightType, 

fn insert(&mut self, value: V) -> NodeIndex

fn remove(&mut self, node: NodeIndex) -> Option<V>

Removes the tree node indexed by node from the tree if present, in this case returning the associated value.

use outils::prelude::*;                             // The resulting tree is shown below:
use outils::tree::traversal::BinaryInOrderValues;   //
                                                    //       -- (3) --
let mut waaforest = WeightedAaForest::new(10);      //      /         \
                                                    //    (1)         (5)
let mut indices = Vec::new();                       //   /   \       /   \
indices.push(waaforest.insert_weighted(0, 1));      // (0)   (2)    (4)   (6)

for i in 1..7 {
    indices.push(waaforest.insert_weighted(i, 1));
    waaforest.append(indices[i-1], indices[i]);
}

assert_eq!(waaforest.remove(indices[5]), Some(5));
let seq: Vec<&usize> = BinaryInOrderValues::new(&waaforest, indices[0]).collect();
assert_eq!(seq, vec![&0, &1, &2, &3, &4, &6]);

fn split(
    &mut self,
    node: NodeIndex,
    dir: BstDirection
) -> (Option<NodeIndex>, Option<NodeIndex>)

Splits the sequence of tree nodes represented by the forest tree containing the tree node indexed by node.

If dir == BstDirection::Left, node will index the last tree node of the left sequence, while if dir == BstDirection::Right, node will index the first tree node of the right sequence (both with respect to in-order). The roots of the resulting sequences will be returned as a tuple.

use outils::prelude::*;                             // The resulting trees are shown below:
use outils::tree::traversal::BinaryInOrderValues;   //
                                                    //       -- (3) --
let mut waaforest1 = WeightedAaForest::new(10);     //      /         \
let mut waaforest2 = WeightedAaForest::new(10);     //    (1)         (5)
                                                    //   /   \       /   \
let mut indices1 = Vec::new();                      // (0)   (2)    (4)   (6)
indices1.push(waaforest1.insert_weighted(0, 1));
let mut indices2 = Vec::new();
indices2.push(waaforest2.insert_weighted(0, 1));

for i in 1..7 {
    indices1.push(waaforest1.insert_weighted(i, 1));
    waaforest1.append(indices1[i-1], indices1[i]);
    indices2.push(waaforest2.insert_weighted(i, 1));
    waaforest2.append(indices2[i-1], indices2[i]);
}

// Split the tree at 3 and keep 3 as part of the left (i.e. _smaller_) tree.
// Because every node of the tree constructed above has a weight of 1, the root of the
// left tree is expected to have a subweight of 4, the root of the right a subweight of 3:
let result1 = waaforest1.split(indices1[3], BstDirection::Left);
match(result1) {
    (Some(left), Some(right)) => {
        assert_eq!(waaforest1.subweight(left), Some(&4));
        let seq_left: Vec<&usize> = BinaryInOrderValues::new(&waaforest1, left).collect();
        assert_eq!(seq_left, vec![&0, &1, &2, &3]);
        assert_eq!(waaforest1.subweight(right), Some(&3));
        let seq_right: Vec<&usize> = BinaryInOrderValues::new(&waaforest1, right).collect();
        assert_eq!(seq_right, vec![&4, &5, &6]);
    }
    _ => {
        panic!("3 was neither first nor last, so the returned tuple should be (Some, Some)")
    }
}

// Split the tree at 3 and keep 3 as part of the right (i.e. _bigger_) tree.
// Because every node of the tree constructed above has a weight of 1, the root of the
// left tree is expected to have a subweight of 3, the root of the right a subweight of 4:
let result2 = waaforest2.split(indices2[3], BstDirection::Right);
match(result2) {
    (Some(left), Some(right)) => {
        assert_eq!(waaforest2.subweight(left), Some(&3));
        let seq_left: Vec<&usize> = BinaryInOrderValues::new(&waaforest2, left).collect();
        assert_eq!(seq_left, vec![&0, &1, &2]);
        assert_eq!(waaforest2.subweight(right), Some(&4));
        let seq_right: Vec<&usize> = BinaryInOrderValues::new(&waaforest2, right).collect();
        assert_eq!(seq_right, vec![&3, &4, &5, &6]);
    }
    _ => {
        panic!("3 was neither first nor last, so the returned tuple should be (Some, Some)");
    }
}

fn split_all(
    &mut self,
    node: NodeIndex,
    size_hint: Option<usize>
) -> Vec<NodeIndex>

Splits the whole sequence of tree nodes represented by the forest tree containing the tree node indexed by node into singleton (i.e. sole leaf) nodes. The subweights of the split nodes will be adjusted accordingly.

If the tree nodes to be split is known beforehand, it can be specified optionally as the size_hint of the returned Vec containing the split tree nodes.

Generally, this operation will be much faster than calling split on each node of the sequence separately, the reason being that no re-balancing is necessary when it is known beforehand that every tree node will be split.

use outils::prelude::*;                          // The resulting tree is shown below:
                                                 //
let mut waaforest = WeightedAaForest::new(10);   //       -- (3) --
                                                 //      /         \
let mut indices = Vec::new();                    //    (1)         (5)
indices.push(waaforest.insert_weighted(0, 1));   //   /   \       /   \
                                                 // (0)   (2)    (4)   (6)
for i in 1..7 {
    indices.push(waaforest.insert_weighted(i, 1));
    waaforest.append(indices[i-1], indices[i]);
}

let split_nodes = waaforest.split_all(indices[0], Some(7));
assert_eq!(split_nodes.len(), indices.len());

// After splitting the forest tree, every one of its former nodes should be a singleton.
// In particular, we expect the subweight of every node to equals its weight.
for i in 0..7 {
    assert!(split_nodes.contains(&indices[i]));
    assert_eq!(waaforest.weight(indices[i]), waaforest.subweight(indices[i]));
    assert_eq!(waaforest.parent(indices[i]), None);
    assert_eq!(waaforest.child(indices[i], 0), None);
    assert_eq!(waaforest.child(indices[i], 1), None);
}

fn append(&mut self, node_u: NodeIndex, node_v: NodeIndex) -> Option<NodeIndex>

Concatenate the sequences of tree nodes represented by the forest trees containing the tree nodes indexed by node_u and node_v, respectively.

With respect to in-order, the former sequence will represent the smaller part of the new sequence, the latter sequence the bigger part. The root of the resulting sequence will be returned.

use outils::prelude::*;
use outils::tree::traversal::BinaryInOrderValues;
let mut waaforest = WeightedAaForest::new(10);

// Insert values into the forest - each value will be a single-node tree in the forest.
let mut indices = Vec::new();
for i in 0..7 {
    indices.push(waaforest.insert_weighted(i, 1));
}

// Construct the _smaller_ tree, containing the in-order sequence 0,1,2,3
let mut left = indices[0];
left = waaforest.append(left, indices[1]).expect("Result should not be None");
left = waaforest.append(left, indices[2]).expect("Result should not be None");
left = waaforest.append(left, indices[3]).expect("Result should not be None");

{ // Restrict scope of the borrow of `waaforest`.
    let seq: Vec<&usize> = BinaryInOrderValues::new(&waaforest, left).collect();
    assert_eq!(seq, vec![&0, &1, &2, &3]);
}

// Construct the _bigger_ tree, containing the in-order sequence 4,5,6
let mut right = indices[4];
right = waaforest.append(right, indices[5]).expect("Result should not be None");
right = waaforest.append(right, indices[6]).expect("Result should not be None");

{ // Restrict scope of the borrow of `waaforest`.
    let seq: Vec<&usize> = BinaryInOrderValues::new(&waaforest, right).collect();
    assert_eq!(seq, vec![&4, &5, &6]);
}

// Because every node of the trees constructed above has a weight of 1, the root of the
// left tree is expected to have a subweight of 4, the root of the right a subweight of 3:
assert_eq!(waaforest.subweight(left), Some(&4));
assert_eq!(waaforest.subweight(right), Some(&3));

// Link left and right, constructing the in-order sequence 0,1,2,3,4,5,6. Afterwards, we
// expect the subweight of the new root to equal 7.
let root = waaforest.append(left, right).expect("Result should not be None");
assert_eq!(waaforest.subweight(root), Some(&7));
let seq: Vec<&usize> = BinaryInOrderValues::new(&waaforest, root).collect();
assert_eq!(seq, vec![&0, &1, &2, &3, &4, &5, &6]);

Loading content...