Struct AvlTree 

pub struct AvlTree<K: Ord + AsBytes, V> {
    pub root: Option<Box<AvlNode<K, V>>>,
}

An AVL Tree that supports get and insert operation and can be used to prove existence of a given key-value couple.

Fields

root: Option<Box<AvlNode<K, V>>>

Implementations

impl<K: Ord + AsBytes, V: Borrow<[u8]>> AvlTree<K, V>

pub fn new() -> Self

Return an empty AVL tree.

pub fn root_hash(&self) -> Option<&Hash>

Return the hash of the merkle tree root, if it has at least one node.

pub fn get<Q>(&self, key: &Q) -> Option<&V>

where K: Borrow<Q>, Q: Ord + ?Sized,

Return the value corresponding to the key, if it exists.

pub fn insert(&mut self, key: K, value: V) -> Option<V>

Insert a value into the AVL tree, this operation runs in amortized O(log(n)).

pub fn remove(&mut self, key: K) -> Option<V>

Remove a value from the AVL tree, this operation runs in amortized O(log(n)).

pub fn get_proof<Q>(&self, key: &Q) -> CommitmentProof

where K: Borrow<Q>, Q: Ord + AsBytes + ?Sized,

Return an existence proof for the given element, if it exists. Otherwise return a non-existence proof.

pub fn rotate_right(root: &mut Option<Box<AvlNode<K, V>>>)

Performs a right rotation.

pub fn rotate_left(root: &mut Option<Box<AvlNode<K, V>>>)

Perform a left rotation.

pub fn get_keys(&self) -> Vec<&K>

Return a list of the keys present in the tree.

Trait Implementations

impl<K: Clone + Ord + AsBytes, V: Clone> Clone for AvlTree<K, V>

fn clone(&self) -> AvlTree<K, V>

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<K: Debug + Ord + AsBytes, V: Debug> Debug for AvlTree<K, V>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<K: Ord + AsBytes, V: Borrow<[u8]>> Default for AvlTree<K, V>

fn default() -> Self

Returns the “default value” for a type.

impl<K: PartialEq + Ord + AsBytes, V: PartialEq> PartialEq for AvlTree<K, V>

fn eq(&self, other: &AvlTree<K, V>) -> bool

Tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl<K: Eq + Ord + AsBytes, V: Eq> Eq for AvlTree<K, V>

impl<K: Ord + AsBytes, V> StructuralPartialEq for AvlTree<K, V>