[−][src]Struct outils::tree::bst::aatree::AaTree
AaTree<K, V>
is a balanced binary search tree data structure. Its tree nodes
are held in a memory arena and are addressed through their associated NodeIndex
.
The balancing method for maintaining a tree height of log(n) where n is the number nodes in the tree is described here: AA tree.
AaTree
is parameterized over:
- Search keys of type
K
, whereK
must implement the traitKeyType
- Associated values of type
V
, whereV
must implement the traitValueType
The usage of AaTree
resembles that of BTreeMap
from the standard library:
use std::collections::BTreeMap; use outils::prelude::*; let mut btreemap = BTreeMap::new(); let mut aatree = AaTree::new(10); btreemap.insert("DE", "Germany"); btreemap.insert("FR", "France"); btreemap.insert("IT", "Italy"); aatree.insert("DE", "Germany"); aatree.insert("FR", "France"); aatree.insert("IT", "Italy"); assert_eq!(btreemap.get(&"DE"), Some(&"Germany")); assert_eq!(aatree.get(&"DE"), Some(&"Germany")); assert_eq!(btreemap.remove(&"FR"), Some("France")); assert_eq!(aatree.remove(&"FR"), Some("France")); assert_eq!(btreemap.get(&"FR"), None); assert_eq!(aatree.get(&"FR"), None);
For most use cases, it is recommended to simply use BTreeMap
, as it is considerably
faster (appr. 50%). However, if information on parent and child relations between tree nodes,
or custom traversal of the tree as such, are needed, AaTree
has an advantage over BTreeMap
.
Implementations
impl<K, V> AaTree<K, V> where
K: KeyType,
V: ValueType,
[src]
K: KeyType,
V: ValueType,
Trait Implementations
impl<K, V> BinarySearchTree<K, V, usize> for AaTree<K, V> where
K: KeyType,
V: ValueType,
[src]
K: KeyType,
V: ValueType,
fn insert_pos(&self, key: K) -> Option<(NodeIndex, Ordering)>
[src]
fn insert(&mut self, key: K, value: V) -> Option<V>
[src]
Inserts a key-value pair into the AaTree
. If the tree did not have this key
present, None
is returned. If the tree did have this key
present, the value is updated, and the old
value is returned. Note that in this situation, the key is left unchanged.
use outils::prelude::*; let mut aatree = AaTree::new(10); assert_eq!(aatree.insert("KEY-1", "VALUE-1"), None); assert_eq!(aatree.insert("KEY-2", "VALUE-2"), None); assert_eq!(aatree.insert("KEY-1", "VALUE-3"), Some("VALUE-1")); assert_eq!(aatree.get(&"KEY-1"), Some(&"VALUE-3")); assert_eq!(aatree.get(&"KEY-2"), Some(&"VALUE-2"));
fn remove(&mut self, key: K) -> Option<V>
[src]
Removes a key
from the tree if present, in this case returning the associated value.
use outils::prelude::*; let mut aatree = AaTree::new(10); aatree.insert("KEY-1", "VALUE-1"); assert_eq!(aatree.remove(&"KEY-1"), Some("VALUE-1")); assert_eq!(aatree.remove(&"KEY-2"), None);
fn get(&self, key: K) -> Option<&V>
[src]
Returns an immutable reference to the associated value of the specified key
.
fn get_mut(&mut self, key: K) -> Option<&mut V>
[src]
Returns a mutable reference to the associated value of the specified key
.
fn index(&self, key: K) -> Option<NodeIndex>
[src]
Returns the index of the tree node holding the specified key
.
fn contains_key(&self, key: K) -> bool
[src]
Returns true
if the map contains a value for the specified key
.
fn key(&self, node: NodeIndex) -> Option<&K>
[src]
Returns the key held by the tree node indexed by node
.
use outils::prelude::*; let mut aatree = AaTree::new(10); aatree.insert("KEY-1", "VALUE-1"); let index = aatree.index(&"KEY-1").expect("KEY-1 should be present"); assert_eq!(aatree.key(index), Some(&"KEY-1"));
impl<K: Clone, V: Clone> Clone for AaTree<K, V> where
K: KeyType,
V: ValueType,
[src]
K: KeyType,
V: ValueType,
impl<K: Debug, V: Debug> Debug for AaTree<K, V> where
K: KeyType,
V: ValueType,
[src]
K: KeyType,
V: ValueType,
impl<K, V> Index<NodeIndex<usize>> for AaTree<K, V> where
K: KeyType,
V: ValueType,
[src]
K: KeyType,
V: ValueType,
impl<K, V> IndexMut<NodeIndex<usize>> for AaTree<K, V> where
K: KeyType,
V: ValueType,
[src]
K: KeyType,
V: ValueType,
impl<'slf, K, V> Keys<'slf, K, usize> for AaTree<K, V> where
K: 'slf + KeyType,
V: ValueType,
[src]
K: 'slf + KeyType,
V: ValueType,
fn keys(&'slf self) -> Box<dyn Iterator<Item = (NodeIndex, &'slf K)> + 'slf>
[src]
Returns a boxed iterator over the search keys and their corresponding
tree node indices held by self
. The keys are returned in the order
of the search keys.
impl<K, V> OrderedTree<usize> for AaTree<K, V> where
K: KeyType,
V: ValueType,
[src]
K: KeyType,
V: ValueType,
fn sub_predecessor(&self, node: NodeIndex) -> Option<NodeIndex>
[src]
Returns the biggest node of the left subtree of the tree node indexed by node
.
use outils::prelude::*; // The resulting tree is shown below: // let mut aatree = AaTree::new(10); // -- (3) -- // / \ for i in 0..7 { // (1) (5) aatree.insert(i, i); // / \ / \ } // (0) (2) (4) (6) let n2 = aatree.index(2).expect("Key '2' should be present"); let n3 = aatree.index(3).expect("Key '3' should be present"); let n4 = aatree.index(4).expect("Key '4' should be present"); assert_eq!(aatree.sub_predecessor(n3), Some(n2)); // 2 is biggest key in left subtree of 3. assert_eq!(aatree.sub_predecessor(n4), None); // 4 is a leaf and thus has no subtrees.'
fn sub_successor(&self, node: NodeIndex) -> Option<NodeIndex>
[src]
Returns the smallest node of the right subtree of the tree node indexed by node
.
Usage is analogous to sub_predecessor
fn predecessor(&self, node: NodeIndex) -> Option<NodeIndex>
[src]
Returns the biggest node of the whole tree which is smaller than the tree node
indexed by node
.
use outils::prelude::*; // The resulting tree is shown below: // let mut aatree = AaTree::new(10); // -- (3) -- // / \ for i in 0..7 { // (1) (5) aatree.insert(i, i); // / \ / \ } // (0) (2) (4) (6) let n0 = aatree.index(0).expect("Key '0' should be present"); let n3 = aatree.index(3).expect("Key '3' should be present"); let n4 = aatree.index(4).expect("Key '4' should be present"); assert_eq!(aatree.predecessor(n4), Some(n3)); // 3 is the biggest key of the whole tree // smaller than 4. assert_eq!(aatree.predecessor(n0), None); // 0 is globally the smallest key of the // whole tree and thus has no predecessor.
fn successor(&self, node: NodeIndex) -> Option<NodeIndex>
[src]
Returns the smallest node of the whole tree which is bigger than the tree node
indexed by node
.
Usage is analogous to predecessor
fn first(&self, node: NodeIndex) -> Option<NodeIndex>
[src]
Returns the smallest node of the left subtree of the tree node indexed by node
.
use outils::prelude::*; // The resulting tree is shown below: // let mut aatree = AaTree::new(10); // -- (3) -- // / \ for i in 0..7 { // (1) (5) aatree.insert(i, i); // / \ / \ } // (0) (2) (4) (6) let n0 = aatree.index(0).expect("Key '0' should be present"); let n1 = aatree.index(1).expect("Key '1' should be present"); let n3 = aatree.index(3).expect("Key '3' should be present"); assert_eq!(aatree.first(n3), Some(n0)); // 0 is the smallest key of the left subtree of 3 assert_eq!(aatree.first(n1), Some(n0)); // 0 is the smallest key of the left subtree of 1
fn last(&self, node: NodeIndex) -> Option<NodeIndex>
[src]
Returns the biggest node of the right subtree of the tree node indexed by node
.
Usage is analogous to first
fn is_smaller(&self, node_u: NodeIndex, node_v: NodeIndex) -> bool
[src]
Returns true
if the tree node indexed by node_u
is smaller than the tree node
indexed by node_v
. Otherwise, and in particular if one of the specified indices
is invalid, false
is returned.
Panics if the path to the root from either of the tree nodes to be compared contains
more than 64 nodes. This is because the directions (i.e. left or right) on the path are
encoded in a bitmap of type u64
. In practice it is next to impossible for this method to
panic because the number of tree nodes needs to be close to 2^64 for the above condition to occur.
use outils::prelude::*; // The resulting tree is shown below: // let mut aatree = AaTree::new(10); // -- (3) -- // / \ for i in 0..7 { // (1) (5) aatree.insert(i, i); // / \ / \ } // (0) (2) (4) (6) let n0 = aatree.index(0).expect("Key '0' should be present"); let n1 = aatree.index(1).expect("Key '1' should be present"); let n3 = aatree.index(3).expect("Key '3' should be present"); assert!(aatree.is_smaller(n0, n3)); assert!(!aatree.is_smaller(n3, n1));
impl<K, V> Tgf for AaTree<K, V> where
K: KeyType,
V: ValueType,
[src]
K: KeyType,
V: ValueType,
impl<K, V> Traversable<V, usize> for AaTree<K, V> where
K: KeyType,
V: ValueType,
[src]
K: KeyType,
V: ValueType,
fn root(&self, _node: NodeIndex) -> Option<NodeIndex>
[src]
Returns the index of the root node of the AaTree
. Since the tree can only have one root
the parameter node
is not used.
use outils::prelude::*; let mut aatree = AaTree::new(10); assert_eq!(aatree.root(NodeIndex(0)), None); // The parameter to root() doesn't matter! aatree.insert("KEY-1", "VALUE-1"); // The solitary key in the tree must be the root let index = aatree.index(&"KEY-1").expect("KEY-1 should be present"); assert_eq!(aatree.root(index), Some(index)); assert_eq!(aatree.root(NodeIndex(0)), Some(index)); // The parameter to root() doesn't matter!
fn value(&self, node: NodeIndex) -> Option<&V>
[src]
Immutably access the value stored in the AaTree
indexed by node
.
fn value_mut(&mut self, node: NodeIndex) -> Option<&mut V>
[src]
Mutably access the value stored in the AaTree
indexed by node
.
fn parent(&self, node: NodeIndex) -> Option<NodeIndex>
[src]
Returns the index of parent node tree node indexed by node
.
fn child(&self, node: NodeIndex, pos: usize) -> Option<NodeIndex>
[src]
Returns the index of the child node at position pos
of the tree node indexed by node
.
Note that a binary search tree node will always have two children, i.e. that even if the
left child (pos == 0
) is empty, the right child (pos == 1
) might contain a value.
In case of a leaf node, both children will be empty:
use outils::prelude::*; let mut aatree = AaTree::new(10); aatree.insert(1, "1"); aatree.insert(2, "2"); // At this point, the AA algorithm has not had to rotate the tree, so that // the key `2` will be the right child of the key `1`: let parent = aatree.index(1).expect("Key '1' should be present"); assert_eq!(aatree.child(parent, 0), None); assert_eq!(aatree.child(parent, 1), aatree.index(2));
fn child_count(&self, node: NodeIndex) -> usize
[src]
Returns the number of child nodes of the tree node indexed by node
.
Note that a binary search tree node will always have two children, i.e. that even if the left child is empty, the right child might contain a value. In case of a leaf node, both children will be empty, but the number of (empty) children will still be 2:
use outils::prelude::*; let mut aatree = AaTree::new(10); aatree.insert(1, "1"); aatree.insert(2, "2"); // At this point, the AA algorithm has not had to rotate the tree, so that // the key `2` will be the right child of the key `1`: let parent = aatree.index(1).expect("Key '1' should be present"); let child = aatree.index(2).expect("Key '2' should be present"); assert_eq!(aatree.child_count(parent), 2); assert_eq!(aatree.child_count(child), 2); assert_eq!(aatree.child_count(NodeIndex(999)), 0); // Invalid index => no children
fn node_count(&self) -> usize
[src]
Returns the total number of tree nodes of the tree self
.
impl<'slf, K, V> Values<'slf, V, usize> for AaTree<K, V> where
K: KeyType,
V: 'slf + ValueType,
[src]
K: KeyType,
V: 'slf + ValueType,
Auto Trait Implementations
impl<K, V> RefUnwindSafe for AaTree<K, V> where
K: RefUnwindSafe,
V: RefUnwindSafe,
K: RefUnwindSafe,
V: RefUnwindSafe,
impl<K, V> Send for AaTree<K, V> where
K: Send,
V: Send,
K: Send,
V: Send,
impl<K, V> Sync for AaTree<K, V> where
K: Sync,
V: Sync,
K: Sync,
V: Sync,
impl<K, V> Unpin for AaTree<K, V> where
K: Unpin,
V: Unpin,
K: Unpin,
V: Unpin,
impl<K, V> UnwindSafe for AaTree<K, V> where
K: UnwindSafe,
V: UnwindSafe,
K: UnwindSafe,
V: UnwindSafe,
Blanket Implementations
impl<T> Any for T where
T: 'static + ?Sized,
[src]
T: 'static + ?Sized,
impl<T> Borrow<T> for T where
T: ?Sized,
[src]
T: ?Sized,
impl<T> BorrowMut<T> for T where
T: ?Sized,
[src]
T: ?Sized,
fn borrow_mut(&mut self) -> &mut T
[src]
impl<T> From<T> for T
[src]
impl<T, U> Into<U> for T where
U: From<T>,
[src]
U: From<T>,
impl<T> ToOwned for T where
T: Clone,
[src]
T: Clone,
type Owned = T
The resulting type after obtaining ownership.
fn to_owned(&self) -> T
[src]
fn clone_into(&self, target: &mut T)
[src]
impl<T, U> TryFrom<U> for T where
U: Into<T>,
[src]
U: Into<T>,
type Error = Infallible
The type returned in the event of a conversion error.
fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>
[src]
impl<T, U> TryInto<U> for T where
U: TryFrom<T>,
[src]
U: TryFrom<T>,
type Error = <U as TryFrom<T>>::Error
The type returned in the event of a conversion error.
fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>
[src]
impl<V, T> VZip<V> for T where
V: MultiLane<T>,
V: MultiLane<T>,