ca.pfv.spmf.datastructures.redblacktree

Class RedBlackTree<T extends java.lang.Comparable<T>>

java.lang.Object

ca.pfv.spmf.datastructures.redblacktree.RedBlackTree<T>

All Implemented Interfaces:

java.lang.Iterable<T>

public class RedBlackTree<T extends java.lang.Comparable<T>>
extends java.lang.Object
implements java.lang.Iterable<T>

This is an implementation of a "red-black tree" based on the chapter 13 of the book: "Introductions to algorithms" by Cormen et al. (2001). Most of the code is based on the pseudo-code from this book. To understand the details of this implementation, please refer to the book.

Elements inserted in the tree have to extend the Comparable class.

The tree provides these operations: add, remove, size, contains, minimum, maximum, popMinimum, popMaximum, lower, higher.

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
class	RedBlackTree.Node Inner class representing a node of a red-black tree.
class	RedBlackTree.RedBlackTreeIterator<S> This is an iterator for traversing the red-black tree

Constructor Summary

Constructors

Constructor and Description
RedBlackTree() Default constructor
RedBlackTree(boolean allowSameElementMultipleTimes) Constructor

Method Summary

Modifier and Type	Method and Description
void	add(T element) Add an element to the tree (see the book for details).
boolean	contains(T k) Check if an element is contained in the tree
T	higher(T k) Return the largest element having a value lower than a given element k.
boolean	isEmpty() Is this tree empty?
java.util.Iterator<T>	iterator()
T	lower(T k) Return the largest element having a value lower than a given element k.
RedBlackTree.Node	lowerNode(T k) Return the node having the largest element having a value lower than a given element k.
T	maximum() Get the maximum element in the tree
T	minimum() Get the minimum element in the tree
T	popMaximum() Get the maximum element in the tree and remove it from the tree
T	popMinimum() Get the minimum element in the tree and remove it from the tree
void	remove(T element) Remove an element from the tree
int	size() Get the number of elements stored in this red-black tree.
java.lang.String	toString() Method toString that returns a string with all the elements in the tree according to the ascending order.

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, wait, wait, wait

Methods inherited from interface java.lang.Iterable

forEach, spliterator

Constructor Detail

RedBlackTree

public RedBlackTree(boolean allowSameElementMultipleTimes)

Constructor

Parameters:

allowSameElementMultipleTimes - if set to true, this allows the tree to contains the same element multiple times. To check if an element is the same, this class use the compareTo method

RedBlackTree

public RedBlackTree()

Default constructor

Method Detail

size

public int size()

Get the number of elements stored in this red-black tree.

Returns:

the number of elements.

isEmpty

public boolean isEmpty()

Is this tree empty?

Returns:

true if yes.

add

public void add(T element)

Add an element to the tree (see the book for details).

Parameters:

element - the element to be added

remove

public void remove(T element)

Remove an element from the tree

Parameters:

element - the element to be removed

lower

public T lower(T k)

Return the largest element having a value lower than a given element k.

lowerNode

public RedBlackTree.Node lowerNode(T k)

Return the node having the largest element having a value lower than a given element k.

higher

public T higher(T k)

Return the largest element having a value lower than a given element k.

popMinimum

public T popMinimum()

Get the minimum element in the tree and remove it from the tree

Returns:

the minimum element in the tree

popMaximum

public T popMaximum()

Get the maximum element in the tree and remove it from the tree

Returns:

the maximum element in the tree

minimum

public T minimum()

Get the minimum element in the tree

Returns:

the minimum element in the tree

maximum

public T maximum()

Get the maximum element in the tree

Returns:

the maximum element in the tree

contains

public boolean contains(T k)

Check if an element is contained in the tree

Parameters:

k - the element.

Returns:

true if the element is in the tree. Otherwise, false.

toString

public java.lang.String toString()

Method toString that returns a string with all the elements in the tree according to the ascending order. NOTE : could be transformed into a non recursive algorithm.

Overrides:

toString in class java.lang.Object

iterator

public java.util.Iterator<T> iterator()

Specified by:

iterator in interface java.lang.Iterable<T extends java.lang.Comparable<T>>