Trait outils::tree::bst::BalancedBinaryForest

source · 
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>>;
}
Expand description

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

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

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

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.

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.

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.

Implementors