net.datastructures

Class RBTree<K,V>

java.lang.Object

net.datastructures.LinkedBinaryTree<Entry<K,V>>

net.datastructures.BinarySearchTree<K,V>

net.datastructures.RBTree<K,V>

All Implemented Interfaces:

BinaryTree<Entry<K,V>>, Dictionary<K,V>, Tree<Entry<K,V>>

public class RBTree<K,V>
extends BinarySearchTree<K,V>
implements Dictionary<K,V>

Realization of a dictionary by means of a red-black tree.

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
protected static class	RBTree.RBNode<K,V> Nested class for the nodes of a red-black tree

Nested classes/interfaces inherited from class net.datastructures.BinarySearchTree

BinarySearchTree.BSTEntry<K,V>

Field Summary

Fields inherited from class net.datastructures.BinarySearchTree

actionPos, C, numEntries

Fields inherited from class net.datastructures.LinkedBinaryTree

root, size

Constructor Summary

Constructors

Constructor and Description
RBTree()
RBTree(java.util.Comparator<K> C)

Method Summary

Modifier and Type	Method and Description
protected BTPosition<Entry<K,V>>	createNode(Entry<K,V> element, BTPosition<Entry<K,V>> parent, BTPosition<Entry<K,V>> left, BTPosition<Entry<K,V>> right) Creates a new tree node.
protected boolean	hasRedChild(Position<Entry<K,V>> position) Returns whether a node has a red child.
Entry<K,V>	insert(K k, V x) Inserts an item into the dictionary and returns the newly created entry.
protected boolean	isPosRed(Position<Entry<K,V>> position) Returns whether a node is red.
protected Position<Entry<K,V>>	redChild(Position<Entry<K,V>> position) Returns a red child of a node.
protected void	remedyDoubleBlack(Position<Entry<K,V>> posR) Remedies a double black violation at a given node caused by removal.
protected void	remedyDoubleRed(Position<Entry<K,V>> posZ) Remedies a double red violation at a given node caused by insertion.
Entry<K,V>	remove(Entry<K,V> ent) Removes and returns the given entry from the dictionary.
protected void	setBlack(Position<Entry<K,V>> position) Colors a node black.
protected void	setColor(Position<Entry<K,V>> position, boolean color) Sets the color of a node.
protected void	setRed(Position<Entry<K,V>> position) Colors a node red.
protected void	swap(Position<Entry<K,V>> swapPos, Position<Entry<K,V>> remPos) Swaps the colors and elements at the two nodes.
protected boolean	swapColor(Position<Entry<K,V>> a, Position<Entry<K,V>> b) Swaps the colors of a and b if they are different and returns whether a was red.

Methods inherited from class net.datastructures.BinarySearchTree

addAll, checkEntry, checkKey, entries, entry, find, findAll, insertAtExternal, isEmpty, key, removeExternal, replaceEntry, restructure, size, treeSearch, value

Methods inherited from class net.datastructures.LinkedBinaryTree

addRoot, attach, checkPosition, children, expandExternal, hasLeft, hasRight, inorderPositions, insertLeft, insertRight, isExternal, isInternal, isRoot, iterator, left, parent, positions, preorderPositions, remove, removeAboveExternal, replace, right, root, sibling, swapElements

Methods inherited from class java.lang.Object

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

Methods inherited from interface net.datastructures.Dictionary

entries, find, findAll, isEmpty, size

Constructor Detail

RBTree

public RBTree()

RBTree

public RBTree(java.util.Comparator<K> C)

Method Detail

createNode

protected BTPosition<Entry<K,V>> createNode(Entry<K,V> element,
                                            BTPosition<Entry<K,V>> parent,
                                            BTPosition<Entry<K,V>> left,
                                            BTPosition<Entry<K,V>> right)

Creates a new tree node.

Overrides:

createNode in class LinkedBinaryTree<Entry<K,V>>

insert

public Entry<K,V> insert(K k,
                         V x)
                  throws InvalidKeyException

Inserts an item into the dictionary and returns the newly created entry.

Specified by:

insert in interface Dictionary<K,V>

Overrides:

insert in class BinarySearchTree<K,V>

Throws:

InvalidKeyException

remedyDoubleRed

protected void remedyDoubleRed(Position<Entry<K,V>> posZ)

Remedies a double red violation at a given node caused by insertion.

remove

public Entry<K,V> remove(Entry<K,V> ent)
                  throws InvalidEntryException

Removes and returns the given entry from the dictionary.

Specified by:

remove in interface Dictionary<K,V>

Overrides:

remove in class BinarySearchTree<K,V>

Throws:

InvalidEntryException

remedyDoubleBlack

protected void remedyDoubleBlack(Position<Entry<K,V>> posR)

Remedies a double black violation at a given node caused by removal.

isPosRed

protected boolean isPosRed(Position<Entry<K,V>> position)

Returns whether a node is red.

setRed

protected void setRed(Position<Entry<K,V>> position)

Colors a node red.

setBlack

protected void setBlack(Position<Entry<K,V>> position)

Colors a node black.

setColor

protected void setColor(Position<Entry<K,V>> position,
                        boolean color)

Sets the color of a node.

Parameters:

color - true to color the node red, false to color the node black

redChild

protected Position<Entry<K,V>> redChild(Position<Entry<K,V>> position)

Returns a red child of a node.

hasRedChild

protected boolean hasRedChild(Position<Entry<K,V>> position)

Returns whether a node has a red child.

swapColor

protected boolean swapColor(Position<Entry<K,V>> a,
                            Position<Entry<K,V>> b)

Swaps the colors of a and b if they are different and returns whether a was red.

swap

protected void swap(Position<Entry<K,V>> swapPos,
                    Position<Entry<K,V>> remPos)

Swaps the colors and elements at the two nodes.