Enum treers::rbtree::RedBlackTree

pub enum RedBlackTree<K: Ord + Clone, V: Clone> {
    Node {
        k: K,
        v: V,
        color: bool,
        size: usize,
        left: Box<RedBlackTree<K, V>>,
        right: Box<RedBlackTree<K, V>>,
    },
    NIL,
}

3.3 Balanced Search Trees: Red-Black BST

Red-Black BST implementation from Robert Sedgewick book, "Algorithms" 4th edition

Examples

use treers::SedgewickMap;
use treers::rbtree::RedBlackTree;

let mut rbtree: RedBlackTree<char, i32> = RedBlackTree::new();
rbtree.put('a', 1);
rbtree.put('b', 2);
rbtree.put('c', 3);
rbtree.put('d', 4);
rbtree.put('e', 5);
rbtree.put('f', 6);

// Generate a balanced Red-Black Binary Search Tree
//          d(B)           <-- height: 0
//        /      \
//     (R)b       f(B)     <-- height: 1
//      / \      /    \
//   (B)a  c(B) e(R)       <-- height: 2
// Note -The Height of binary tree with single node is taken as zero.
assert_eq!(rbtree.get(&'a'), Some(&1_i32));
assert_eq!(rbtree[&'a'], 1_i32);
assert_eq!(rbtree.height(), Some(2_usize));
assert_eq!(rbtree.size(), 6_usize);

Variants

Node

Fields of Node

k: Kv: Vcolor: boolsize: usizeleft: Box<RedBlackTree<K, V>>right: Box<RedBlackTree<K, V>>

NIL

Trait Implementations

impl<K: Clone + Ord, V: Clone> Clone for RedBlackTree<K, V>

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

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<K: Debug + Ord + Clone, V: Debug + Clone> Debug for RedBlackTree<K, V>

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

Formats the value using the given formatter.

impl<K: Ord + Clone, V: Clone> Default for RedBlackTree<K, V>

fn default() -> RedBlackTree<K, V>

Creates an empty RedBlackTree<K, V>.

impl<K: Ord + Clone, V: Clone, '_> Index<&'_ K> for RedBlackTree<K, V>

type Output = V

The returned type after indexing.

fn index(&self, index: &K) -> &V

Returns a reference to the value corresponding to the supplied key.

Panics

Panics if the key is not present in the RedBlackTree.

impl<K: Ord + Clone, V: Clone> SedgewickMap<K, V> for RedBlackTree<K, V>

fn new() -> Self

Inits a new instance of Red-Black Tree.

Examples

Basic usage:

use treers::rbtree::RedBlackTree;
use treers::SedgewickMap;

let rbtree: RedBlackTree<char, i32> = RedBlackTree::new();
assert_eq!(rbtree.is_empty(), true);

fn size(&self) -> usize

Returns a size of elements in Red-Black Tree.

Examples

Basic usage:

use treers::rbtree::RedBlackTree;
use treers::SedgewickMap;

let mut rbtree: RedBlackTree<char, i32> = RedBlackTree::new();
assert_eq!(rbtree.size(), 0_usize);
rbtree.put('a', 1);
rbtree.put('b', 2);
rbtree.put('c', 3);
rbtree.put('d', 4);
assert_eq!(rbtree.size(), 4_usize);

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

Returns a reference to optional reference to value.

Examples

Basic usage:

use treers::rbtree::RedBlackTree;
use treers::SedgewickMap;

let mut rbtree: RedBlackTree<char, i32> = RedBlackTree::new();
rbtree.put('a', 1);
assert_eq!(rbtree.get(&'a'), Some(&1));
assert_eq!(rbtree[&'a'], 1);
assert_eq!(rbtree.get(&'b'), None);

fn put(&mut self, key: K, value: V)

Insert a key-value pair into the Red-Black Tree.

Examples

Basic usage:

use treers::rbtree::RedBlackTree;
use treers::SedgewickMap;

let mut rbtree: RedBlackTree<char, i32> = RedBlackTree::new();
assert_eq!(rbtree.is_empty(), true);

rbtree.put('a', 1_i32);
assert_eq!(rbtree.is_empty(), false);
assert_eq!(rbtree.get(&'a'), Some(&1_i32));
assert_eq!(rbtree[&'a'], 1_i32);

fn height(&self) -> Option<usize>

Get height of Red-Black Tree.

Red-Black Tree is a balanced tree.

Examples

Basic usage:

use treers::rbtree::RedBlackTree;
use treers::SedgewickMap;

let mut rbtree: RedBlackTree<char, i32> = RedBlackTree::new();
rbtree.put('a', 1);
rbtree.put('b', 2);
rbtree.put('c', 3);
rbtree.put('d', 4);
//   b         <-- height: 0
//  / \
// a   d       <-- height: 1
//    / \
//   c         <-- height: 2
// Note -The Height of red-black tree with single node is taken as zero.
assert_eq!(rbtree.get(&'a'), Some(&1_i32));
assert_eq!(rbtree.height(), Some(2_usize));
assert_eq!(rbtree.size(), 4_usize);

fn is_empty(&self) -> bool

Checks if Red-Black Tree node is empty.

Examples

Basic usage:

use treers::rbtree::RedBlackTree;
use treers::SedgewickMap;

let mut rbtree: RedBlackTree<char, i32> = RedBlackTree::new();
assert_eq!(rbtree.is_empty(), true);
rbtree.put('a', 2);
assert_eq!(rbtree.is_empty(), false);

fn min(&self) -> Option<&K>

Returns a optional reference to minimal key

Examples

Basic usage:

use treers::rbtree::RedBlackTree;
use treers::SedgewickMap;

let mut rbtree: RedBlackTree<char, i32> = RedBlackTree::new();
assert_eq!(rbtree.min(), None);
rbtree.put('c', 1);
rbtree.put('a', 2);
rbtree.put('b', 3);
rbtree.put('d', 4);
assert_eq!(rbtree.min(), Some(&'a'));

fn max(&self) -> Option<&K>

Returns a optional reference to maximum key

Examples

Basic usage:

use treers::rbtree::RedBlackTree;
use treers::SedgewickMap;

let mut rbtree: RedBlackTree<char, i32> = RedBlackTree::new();
assert_eq!(rbtree.max(), None);
rbtree.put('c', 1);
rbtree.put('a', 2);
rbtree.put('b', 3);
rbtree.put('d', 4);
assert_eq!(rbtree.max(), Some(&'d'));

fn contains(&self, key: &K) -> bool

Checks if key exists in Tree

impl<K: Ord + Clone, V: Clone> TreeTraversal<K, V> for RedBlackTree<K, V>

fn pre_order<'a>(&'a self, vec: &mut Vec<(&'a K, &'a V)>)

Returns traverse post ordered

Examples

Basic usage:

use treers::rbtree::RedBlackTree;
use treers::{SedgewickMap, TreeTraversal, Traversals};

let mut rbtree: RedBlackTree<char, i32> = RedBlackTree::new();
rbtree.put('a', 1);
rbtree.put('b', 2);
rbtree.put('c', 3);
rbtree.put('d', 4);
rbtree.put('e', 5);
rbtree.put('f', 6);
// Generate a balanced Red-Black Binary Search Tree
//          d(B)           <-- height: 0
//        /      \
//     (R)b       f(B)     <-- height: 1
//      / \      /    \
//   (B)a  c(B) e(R)       <-- height: 2
assert_eq!(rbtree.traverse(&Traversals::PreOrder).as_slice(),
      &[(&'d', &4), (&'b', &2), (&'a', &1),
        (&'c', &3), (&'f', &6), (&'e', &5)]);

fn in_order<'a>(&'a self, vec: &mut Vec<(&'a K, &'a V)>)

Returns traverse in ordered

Examples

Basic usage:

use treers::rbtree::RedBlackTree;
use treers::{SedgewickMap, TreeTraversal, Traversals};

let mut rbtree: RedBlackTree<char, i32> = RedBlackTree::new();
rbtree.put('a', 1);
rbtree.put('b', 2);
rbtree.put('c', 3);
rbtree.put('d', 4);
rbtree.put('e', 5);
rbtree.put('f', 6);
// Generate a balanced Red-Black Binary Search Tree
//          d(B)           <-- height: 0
//        /      \
//     (R)b       f(B)     <-- height: 1
//      / \      /    \
//   (B)a  c(B) e(R)       <-- height: 2
assert_eq!(rbtree.traverse(&Traversals::InOrder).as_slice(),
      &[(&'a', &1), (&'b', &2), (&'c', &3),
        (&'d', &4), (&'e', &5), (&'f', &6)]);

fn post_order<'a>(&'a self, vec: &mut Vec<(&'a K, &'a V)>)

Returns traverse post ordered

Examples

Basic usage:

use treers::rbtree::RedBlackTree;
use treers::{SedgewickMap, TreeTraversal, Traversals};

let mut rbtree: RedBlackTree<char, i32> = RedBlackTree::new();
rbtree.put('a', 1);
rbtree.put('b', 2);
rbtree.put('c', 3);
rbtree.put('d', 4);
rbtree.put('e', 5);
rbtree.put('f', 6);
// Generate a balanced Red-Black Binary Search Tree
//          d(B)           <-- height: 0
//        /      \
//     (R)b       f(B)     <-- height: 1
//      / \      /    \
//   (B)a  c(B) e(R)       <-- height: 2
assert_eq!(rbtree.traverse(&Traversals::PostOrder).as_slice(),
      &[(&'a', &1), (&'c', &3), (&'b', &2),
        (&'e', &5), (&'f', &6), (&'d', &4)]);

fn level_order<'a>(&'a self, vec: &mut Vec<(&'a K, &'a V)>, level: usize)

Returns traverse level ordered

Examples

Basic usage:

use treers::rbtree::RedBlackTree;
use treers::{SedgewickMap, TreeTraversal, Traversals};

let mut rbtree: RedBlackTree<char, i32> = RedBlackTree::new();
rbtree.put('a', 1);
rbtree.put('b', 2);
rbtree.put('c', 3);
rbtree.put('d', 4);
rbtree.put('e', 5);
rbtree.put('f', 6);
// Generate a balanced Red-Black Binary Search Tree
//          d(B)           <-- height: 0
//        /      \
//     (R)b       f(B)     <-- height: 1
//      / \      /    \
//   (B)a  c(B) e(R)       <-- height: 2
assert_eq!(rbtree.traverse(&Traversals::LevelOrder).as_slice(),
      &[            (&'d', &4),               // <-- height: 0
               (&'b', &2), (&'f', &6),        // <-- height: 1
        (&'a', &1), (&'c', &3), (&'e', &5)]); // <-- height: 2

fn traverse(&self, traverse: &Traversals) -> IntoIter<(&K, &V)>