nz.ac.waikato.jdsl.core.ref
Class RedBlackTree

java.lang.Object
  nz.ac.waikato.jdsl.core.ref.RedBlackTree

All Implemented Interfaces:

Container, Dictionary, InspectableContainer, InspectableDictionary, InspectableKeyBasedContainer, InspectableOrderedDictionary, KeyBasedContainer, OrderedDictionary

public class RedBlackTree
extends java.lang.Object
implements OrderedDictionary

A Dictionary implemented as a red-black tree. (A red-black tree is a balanced search tree that maintains its balance through coloring its nodes. See "Data Structures and Algorithms in Java", Goodrich, Tamassia, 2nd Ed., Ch.9.) The red-black tree, in turn, is implemented on top of a subclass of BinaryTree that has the ability to rotate (restructure). This RB tree begins empty, and its internal structure can be accessed with the inspectableBinaryTree method. Once the comparator is set, it can never be changed. Leaf nodes contain locators with a null key; this separates them from data nodes, which are internal and have locators with legitimate, user's keys. A position's color is represented in the locator it holds rather than through a decoration, for faster access. The iterator-returning methods are not cached. This OrderedDictionary is a multi-map, meaning that it is possible for two elements to have the same key. Currently has RestructurableNodeBinaryTree as a nested class while waiting for a test for RNBT.

Version:

JDSL 2.1.1

Author:

Ming En Cho, Michael Boilen, Mark Handy, Ryan Shaun Baker, Luca Vismara

Nested Class Summary

Nested classes/interfaces inherited from interface nz.ac.waikato.jdsl.core.api.InspectableDictionary

InspectableDictionary.InvalidLocator

Field Summary

static int	BLACK
static int	DOUBLEBLACK
static int	RED

Fields inherited from interface nz.ac.waikato.jdsl.core.api.InspectableOrderedDictionary

BOUNDARY_VIOLATION

Fields inherited from interface nz.ac.waikato.jdsl.core.api.InspectableDictionary

NO_SUCH_KEY

Constructor Summary

RedBlackTree(Comparator comparator)
Takes O(1) time This constructor creates the tree with a single no-element-stored-here locator.

Method Summary

Locator	after(Locator locator) Takes O(logN) time -- may need to traverse the height of the tree to find the next note that we do not return color-locators in the leaves -- we only return key locators.
Locator	before(Locator locator) Takes O(logN) time -- may need to traverse the height of the tree to find the next note that we do not return color-locators in the leaves -- we only return key locators.
protected void	case1(Position y, Position z) Takes O(1) time Implements case 1, the Restructuring case Protected for purposes of allowing snapshots during visualization
protected void	case2(Position y) Takes O(1) time Implements case 2, the Recoloring case Protected for purposes of allowing snapshots during visualization
protected void	case3(Position y) Takes O(1) time Implements case 3, the Adjustment case Protected for purposes of allowing snapshots during visualization
protected void	checkDoubleRed(Position p) Takes O(logN) time -- where N = the number of locators in the tree and O(logN) = the height of the tree Check for double reds, then rotate or promote if necessary Protected for purposes of allowing snapshots during visualization
Locator	closestAfter(java.lang.Object key) Takes O(logN) time -- traverses the height of the tree once.
Locator	closestBefore(java.lang.Object key) Takes O(logN) time -- traverses the height of the tree once.
protected void	colorPromotion(Position parent, Position uncle) Takes O(logN) time -- where N = the number of locators in the tree and O(logN) = the height of the tree Do a color promotion and then check if colors are now wrong higher up Protected for purposes of allowing snapshots during visualization
boolean	contains(Accessor a) Takes O(1) time
ObjectIterator	elements() Takes O(N) time from the need to iterate through the tree during snapshot -- where N= the number of locators in the tree Could very easily be cached; not sure that would be useful
Locator	find(java.lang.Object key) Takes O(logN) time -- where N = the number of locators in the tree and O(logN) = the height of the tree Takes the time to traverse the tree's height, which is O(logN)
LocatorIterator	findAll(java.lang.Object key) Takes O(logN+R) time -- where N = the number of locators in the tree and O(logN) = the height of the tree, and R = the number of instances of key in the tree O(log N) for one element; in theory, for each element, taking its inorder prev or next may take up to O(log N).
Locator	first() Takes O(log N) time to traverse the height of the tree where N is the number of locators in the tree and O(logN) is the height of the tree
Locator	insert(java.lang.Object key, java.lang.Object element) Takes O(logN) time -- where N = the number of locators in the tree and O(logN) = the height of the tree The worst-case insertion would restructure once each step up the tree.
InspectableBinaryTree	inspectableBinaryTree() Used for visualization and testers
boolean	isBlack(Position p) Returns whether or not the given position of the underlying tre is black; for visualization/testing purposes.
boolean	isDoubleBlack(Position p) Returns whether or not the given position of the underlying tre is double-black; for visualization/testing purposes.
boolean	isEmpty() Takes O(1) time
boolean	isRed(Position p) Returns whether or not the given position of the underlying tre is red; for visualization/testing purposes.
ObjectIterator	keys() Takes O(N) time from the need to iterate through the tree during snapshot -- where N= the number of locators in the tree Could very easily be cached; not sure that would be useful
Locator	last() Takes O(log N) time to traverse the height of the tree where N is the number of locators in the tree and O(logN) is the height of the tree
LocatorIterator	locators() Takes O(N) time from the need to iterate through the tree during snapshot -- where N= the number of locators in the tree Could very easily be cached; not sure that would be useful
Container	newContainer() Takes O(1) time
protected void	recolorAfterRemove(Position p) Takes O(logN) time -- where N = the number of locators in the tree and O(logN) = the height of the tree.
void	remove(Locator locator) Takes O(logN) time -- where N = the number of locators in the tree and O(logN) = the height of the tree The worst-case removal would restructure once each step up the tree.
LocatorIterator	removeAll(java.lang.Object key) Takes O(RlogN) time where R = the number of objects with key key and log N = the height of the tree (N locators in the tree) (one removal case per each object)
Locator	removeKey(java.lang.Object key) Takes O(logN) time -- where N = the number of locators in the tree and O(logN) = the height of the tree The worst-case removal would restructure once each step up the tree.
java.lang.Object	replaceElement(Accessor loc, java.lang.Object newElement) Takes O(1) time
java.lang.Object	replaceKey(Locator locator, java.lang.Object key) Takes O(logN) time -- where N = the number of locators in the tree and O(logN) = the height of the tree Takes the running time it would take to execute both remove and insert.
int	size() Takes O(1) time
java.lang.String	toString()

Methods inherited from class java.lang.Object

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

Field Detail

RED

public static final int RED

See Also:

Constant Field Values

BLACK

public static final int BLACK

See Also:

Constant Field Values

DOUBLEBLACK

public static final int DOUBLEBLACK

See Also:

Constant Field Values

Constructor Detail

RedBlackTree

public RedBlackTree(Comparator comparator)

Takes O(1) time This constructor creates the tree with a single no-element-stored-here locator. (null key)

Method Detail

newContainer

public Container newContainer()

Takes O(1) time

Specified by:

newContainer in interface Container

Returns:

A new, empty Container of the same class as this one.

size

public int size()

Takes O(1) time

Specified by:

size in interface InspectableContainer

Returns:

Number of elements stored by the container.

isEmpty

public boolean isEmpty()

Takes O(1) time

Specified by:

isEmpty in interface InspectableContainer

Returns:

true if and only if the container is empty (holds no elements)

See Also:

InspectableBinaryTree

contains

public boolean contains(Accessor a)
                 throws InvalidAccessorException

Takes O(1) time

Specified by:

contains in interface InspectableContainer

Throws:

InvalidAccessorException - if a is null

replaceElement

public java.lang.Object replaceElement(Accessor loc,
                                       java.lang.Object newElement)
                                throws InvalidAccessorException

Takes O(1) time

Specified by:

replaceElement in interface Container

Parameters:

loc - Accessor in this container

newElement - to be stored at a

Returns:

old element, previously stored at a

Throws:

InvalidAccessorException - if a is null or does not belong to this container

locators

public LocatorIterator locators()

Takes O(N) time from the need to iterate through the tree during snapshot -- where N= the number of locators in the tree Could very easily be cached; not sure that would be useful

Specified by:

locators in interface InspectableKeyBasedContainer

Returns:

LocatorIterator of the container inorder

elements

public ObjectIterator elements()

Takes O(N) time from the need to iterate through the tree during snapshot -- where N= the number of locators in the tree Could very easily be cached; not sure that would be useful

Specified by:

elements in interface InspectableContainer

Returns:

an iterator over the container elements inorder

keys

public ObjectIterator keys()

Takes O(N) time from the need to iterate through the tree during snapshot -- where N= the number of locators in the tree Could very easily be cached; not sure that would be useful

Specified by:

keys in interface InspectableKeyBasedContainer

Returns:

an iterator over the container keys inorder

replaceKey

public java.lang.Object replaceKey(Locator locator,
                                   java.lang.Object key)
                            throws InvalidAccessorException,
                                   InvalidKeyException

Takes O(logN) time -- where N = the number of locators in the tree and O(logN) = the height of the tree Takes the running time it would take to execute both remove and insert.

Specified by:

replaceKey in interface KeyBasedContainer

Parameters:

locator - the locator in the container whose key should be replaced

key - the new key to associate with loc.

Returns:

The old key

Throws:

InvalidAccessorException - If the locator is not valid or is not contained by this container

InvalidKeyException - If key cannot be used by this container

find

public Locator find(java.lang.Object key)
             throws InvalidKeyException

Takes O(logN) time -- where N = the number of locators in the tree and O(logN) = the height of the tree Takes the time to traverse the tree's height, which is O(logN)

Specified by:

find in interface InspectableDictionary

Parameters:

key - The key mapped to search for.

Returns:

The Locator referring to the key-element pair that was found, or NO_SUCH_KEY if it could not be found.

Throws:

InvalidKeyException - if the specified key is not a valid key in this container.

See Also:

InspectableDictionary.NO_SUCH_KEY

findAll

public LocatorIterator findAll(java.lang.Object key)
                        throws InvalidKeyException

Takes O(logN+R) time -- where N = the number of locators in the tree and O(logN) = the height of the tree, and R = the number of instances of key in the tree O(log N) for one element; in theory, for each element, taking its inorder prev or next may take up to O(log N). In practice, the O(log N) case can only occur twice, and every other case is O(1).

Specified by:

findAll in interface InspectableDictionary

Parameters:

key - The key to search for.

Returns:

A LocatorIterator over the set of (key, element) pairs whose keys match the parameter key

Throws:

InvalidKeyException - if the specified key is not valid in this container

closestBefore

public Locator closestBefore(java.lang.Object key)
                      throws InvalidKeyException

Takes O(logN) time -- traverses the height of the tree once.

Specified by:

closestBefore in interface InspectableOrderedDictionary

Parameters:

key - A valid key.

Returns:

The locator with largest key less than or equal to key. Note: If no such locator exists, the returned locator will be BOUNDARY_VIOLATION.

Throws:

InvalidKeyException - If key is not of a type accepted by this Container (For example: the key is not comparable).

closestAfter

public Locator closestAfter(java.lang.Object key)
                     throws InvalidKeyException

Takes O(logN) time -- traverses the height of the tree once.

Specified by:

closestAfter in interface InspectableOrderedDictionary

Parameters:

key - A valid key.

Returns:

The locator with smallest key greater than or equal to key. Note: If no such Locator exists, the returned locator will be BOUNDARY_VIOLATION.

Throws:

InvalidKeyException - If key is not of a type accepted by this Container (For example: the key is not comparable).

after

public Locator after(Locator locator)
              throws InvalidAccessorException

Takes O(logN) time -- may need to traverse the height of the tree to find the next note that we do not return color-locators in the leaves -- we only return key locators.

Specified by:

after in interface InspectableOrderedDictionary

Parameters:

locator - An abstract position in this Container.

Returns:

A Locator which is sequentially after locator. Note: Will return the invalid BOUNDARY_VIOLATION Locator if no such locator exists.

Throws:

InvalidAccessorException - If locator is invalid (For example: It does not actually reference an element within this Container).

before

public Locator before(Locator locator)
               throws InvalidAccessorException

Takes O(logN) time -- may need to traverse the height of the tree to find the next note that we do not return color-locators in the leaves -- we only return key locators.

Specified by:

before in interface InspectableOrderedDictionary

Parameters:

locator - An abstract position in this Container.

Returns:

A Locator which is sequentially before locator. Note: Will return the invalid BOUNDARY_VIOLATION Locator if no such locator exists.

Throws:

InvalidAccessorException - If locator is invalid (For example: It does not actually reference an element within this Container).

insert

public Locator insert(java.lang.Object key,
                      java.lang.Object element)
               throws InvalidKeyException

Takes O(logN) time -- where N = the number of locators in the tree and O(logN) = the height of the tree The worst-case insertion would restructure once each step up the tree.

Specified by:

insert in interface KeyBasedContainer

Parameters:

key - the key associated with the specified element.

element - the element to insert into the container.

Returns:

a locator associated with the inserted pair.

Throws:

InvalidKeyException - if key cannot be used by this container

checkDoubleRed

protected void checkDoubleRed(Position p)

Takes O(logN) time -- where N = the number of locators in the tree and O(logN) = the height of the tree Check for double reds, then rotate or promote if necessary Protected for purposes of allowing snapshots during visualization

Parameters:

p - The position that would be the child of the two double reds

colorPromotion

protected void colorPromotion(Position parent,
                              Position uncle)

Takes O(logN) time -- where N = the number of locators in the tree and O(logN) = the height of the tree Do a color promotion and then check if colors are now wrong higher up Protected for purposes of allowing snapshots during visualization

Parameters:

parent - The position that would be the parent of the two double reds

uncle - parent's sibling

removeAll

public LocatorIterator removeAll(java.lang.Object key)
                          throws InvalidKeyException

Takes O(RlogN) time where R = the number of objects with key key and log N = the height of the tree (N locators in the tree) (one removal case per each object)

Specified by:

removeAll in interface Dictionary

Parameters:

key - the key to search for

Returns:

a LocatorIterator over the (key, element) pairs whose keys match the parameter key

Throws:

InvalidKeyException - if the specified key is not a valid key in this container

removeKey

public Locator removeKey(java.lang.Object key)
                  throws InvalidKeyException

Takes O(logN) time -- where N = the number of locators in the tree and O(logN) = the height of the tree The worst-case removal would restructure once each step up the tree. Finds the locator to remove, then removes it.

Throws:

InvalidKeyException

remove

public void remove(Locator locator)
            throws InvalidAccessorException

Takes O(logN) time -- where N = the number of locators in the tree and O(logN) = the height of the tree The worst-case removal would restructure once each step up the tree. Ensures that the locator has a leaf child (Swapping if necessary) Then removes it. This leaves a double-black node, which we then resolve to a black node. This may propagate the double-black up the tree, in which case more resolutions will be necessary. The number of resolutions (repairs to the tree) will be <= O(log N)

Specified by:

remove in interface KeyBasedContainer

Parameters:

locator - a locator in the container to remove

Throws:

InvalidAccessorException - if the locator is not valid or is not contained by this container

recolorAfterRemove

protected void recolorAfterRemove(Position p)

Takes O(logN) time -- where N = the number of locators in the tree and O(logN) = the height of the tree. Recolors after removal, i.e., delegate to appropriate case; can be called recursively for case 2. Protected for purposes of allowing snapshots during visualization

Parameters:

p - The node to recolor above

case1

protected void case1(Position y,
                     Position z)

Takes O(1) time Implements case 1, the Restructuring case Protected for purposes of allowing snapshots during visualization

Parameters:

y - -- the sibling of the double-black node

z - -- the red child of y

case2

protected void case2(Position y)

Takes O(1) time Implements case 2, the Recoloring case Protected for purposes of allowing snapshots during visualization

Parameters:

y - -- the sibling of the double-black node

case3

protected void case3(Position y)

Takes O(1) time Implements case 3, the Adjustment case Protected for purposes of allowing snapshots during visualization

Parameters:

y - -- the sibling of the double-black node

first

public Locator first()

Takes O(log N) time to traverse the height of the tree where N is the number of locators in the tree and O(logN) is the height of the tree

Specified by:

first in interface InspectableOrderedDictionary

Returns:

A Locator which is sequentially before any other locator. Note: Will return the invalid BOUNDARY_VIOLATION Locator if no such locator exists.

last

public Locator last()

Takes O(log N) time to traverse the height of the tree where N is the number of locators in the tree and O(logN) is the height of the tree

Specified by:

last in interface InspectableOrderedDictionary

Returns:

A Locator which is sequentially after any other locator. Note: Will return the invalid BOUNDARY_VIOLATION Locator if no such locator exists.

isRed

public final boolean isRed(Position p)

Returns whether or not the given position of the underlying tre is red; for visualization/testing purposes.

Parameters:

p - The position to check

isBlack

public final boolean isBlack(Position p)

Returns whether or not the given position of the underlying tre is black; for visualization/testing purposes.

Parameters:

p - The position to check

isDoubleBlack

public final boolean isDoubleBlack(Position p)

Returns whether or not the given position of the underlying tre is double-black; for visualization/testing purposes.

Parameters:

p - The position to check

inspectableBinaryTree

public InspectableBinaryTree inspectableBinaryTree()

Used for visualization and testers

toString

public java.lang.String toString()

Overrides:

toString in class java.lang.Object