Package com.puresoltechnologies.graphs.trees

Class RedBlackTree<Key extends Comparable<Key>,Value>

java.lang.Object

com.puresoltechnologies.graphs.trees.BinarySearchTree<RedBlackTreeNode<Key,Value>,Key,Value>

com.puresoltechnologies.graphs.trees.RedBlackTree<Key,Value>

Type Parameters:

Key - is the property key type.

Value - is the property value type.

All Implemented Interfaces:

Graph<Key,Value>, Tree<RedBlackTreeNode<Key,Value>>, Iterable<Key>

public class RedBlackTree<Key extends Comparable<Key>,Value>
extends BinarySearchTree<RedBlackTreeNode<Key,Value>,Key,Value>
implements Tree<RedBlackTreeNode<Key,Value>>

This is a RedBlackTree implementation based on BinarySearchTree. see: http://algs4.cs.princeton.edu/33balanced/RedBlackBST.java.html This implementation is not thread-safe.

Author:

Rick-Rainer Ludwig

Field Summary

Fields inherited from class com.puresoltechnologies.graphs.trees.BinarySearchTree

root

Constructor Summary

Constructors

Constructor	Description
RedBlackTree()

Method Summary

Modifier and Type	Method	Description
Key	ceiling(Key key)	Returns the smallest key in the symbol table greater than or equal to key.
RedBlackTreeNode<Key,Value>	ceilingNode(Key key)	Returns the smallest key in the symbol table greater than or equal to key.
void	delete(Key key)	Removes the specified key and its associated value from this symbol table (if the key is in this symbol table).
void	deleteMax()	Removes the largest key and associated value from the symbol table.
void	deleteMin()	Removes the smallest key and associated value from the symbol table.
Key	floor(Key key)	Returns the largest key in the symbol table less than or equal to key.
RedBlackTreeNode<Key,Value>	floorNode(Key key)	Returns the largest node with key in the symbol table less than or equal to key.
int	height()	Returns the height of the BST (for debugging).
Iterable<Key>	keys()	Returns all keys in the symbol table as an Iterable.
Iterable<Key>	keys(Key lo, Key hi)	Returns all keys in the symbol table in the given range, as an Iterable.
Key	max()	Returns the largest key in the symbol table.
Key	min()	Returns the smallest key in the symbol table.
void	put(Key key, Value value)	Inserts the specified key-value pair into the symbol table, overwriting the old value with the new value if the symbol table already contains the specified key.
int	rank(Key key)	Return the number of keys in the symbol table strictly less than key.
Key	select(int k)	Return the kth smallest key in the symbol table.
int	size()
int	size(Key low, Key high)	Returns the number of keys in the symbol table in the given range.

Methods inherited from class com.puresoltechnologies.graphs.trees.BinarySearchTree

clear, contains, get, getRootNode, getVertices, isEmpty, iterator, iterator

Methods inherited from interface com.puresoltechnologies.graphs.graph.Graph

getVertices

Methods inherited from interface java.lang.Iterable

forEach, spliterator

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Methods inherited from interface com.puresoltechnologies.graphs.trees.Tree

getRootNode

Constructor Detail

RedBlackTree

public RedBlackTree()

Method Detail

size

public int size()

put

public void put(Key key,
                Value value)

Inserts the specified key-value pair into the symbol table, overwriting the old value with the new value if the symbol table already contains the specified key. Deletes the specified key (and its associated value) from this symbol table if the specified value is null.

Specified by:

put in class BinarySearchTree<RedBlackTreeNode<Key extends Comparable<Key>,Value>,Key extends Comparable<Key>,Value>

Parameters:

key - the key

value - the value

deleteMin

public void deleteMin()

Removes the smallest key and associated value from the symbol table.

Throws:

NoSuchElementException - if the symbol table is empty

deleteMax

public void deleteMax()

Removes the largest key and associated value from the symbol table.

Throws:

NoSuchElementException - if the symbol table is empty

delete

public void delete(Key key)

Removes the specified key and its associated value from this symbol table (if the key is in this symbol table).

Specified by:

delete in class BinarySearchTree<RedBlackTreeNode<Key extends Comparable<Key>,Value>,Key extends Comparable<Key>,Value>

Parameters:

key - the key

height

public int height()

Returns the height of the BST (for debugging).

Returns:

the height of the BST (a 1-node tree has height 0)

min

public Key min()

Returns the smallest key in the symbol table.

Returns:

the smallest key in the symbol table

Throws:

NoSuchElementException - if the symbol table is empty

max

public Key max()

Returns the largest key in the symbol table.

Returns:

the largest key in the symbol table

Throws:

NoSuchElementException - if the symbol table is empty

floor

public Key floor(Key key)

Returns the largest key in the symbol table less than or equal to key.

Parameters:

key - the key

Returns:

the largest key in the symbol table less than or equal to key

Throws:

NoSuchElementException - if there is no such key

floorNode

public RedBlackTreeNode<Key,Value> floorNode(Key key)

Returns the largest node with key in the symbol table less than or equal to key.

Parameters:

key - the key

Returns:

the largest key in the symbol table less than or equal to key

Throws:

NoSuchElementException - if there is no such key

ceiling

public Key ceiling(Key key)

Returns the smallest key in the symbol table greater than or equal to key.

Parameters:

key - the key

Returns:

the smallest key in the symbol table greater than or equal to key

Throws:

NoSuchElementException - if there is no such key

ceilingNode

public RedBlackTreeNode<Key,Value> ceilingNode(Key key)

Returns the smallest key in the symbol table greater than or equal to key.

Parameters:

key - the key

Returns:

the smallest key in the symbol table greater than or equal to key

Throws:

NoSuchElementException - if there is no such key

select

public Key select(int k)

Return the kth smallest key in the symbol table.

Parameters:

k - the order statistic

Returns:

the kth smallest key in the symbol table

Throws:

IllegalArgumentException - unless k is between 0 and N − 1

rank

public int rank(Key key)

Return the number of keys in the symbol table strictly less than key.

Parameters:

key - the key

Returns:

the number of keys in the symbol table strictly less than key

keys

public Iterable<Key> keys()

Returns all keys in the symbol table as an Iterable. To iterate over all of the keys in the symbol table named st, use the foreach notation: for (Key key : st.keys()).

Returns:

all keys in the sybol table as an Iterable

keys

public Iterable<Key> keys(Key lo,
                          Key hi)

Returns all keys in the symbol table in the given range, as an Iterable.

Parameters:

lo - is the lower border.

hi - is the upper border.

Returns:

all keys in the sybol table between lo (inclusive) and hi (exclusive) as an Iterable

size

public int size(Key low,
                Key high)

Returns the number of keys in the symbol table in the given range.

Parameters:

low - is the lower border.

high - is the upper border.

Returns:

the number of keys in the symbol table between low (inclusive) and high (exclusive)