net.datastructures
Class RBTree

java.lang.Object
  net.datastructures.LinkedBinaryTree
      net.datastructures.BinarySearchTree
          net.datastructures.RBTree

All Implemented Interfaces:

BinaryTree, Dictionary, Tree

public class RBTree

extends BinarySearchTree

implements Dictionary

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

Nested Class Summary

protected static class

RBTree.RBNode Nested class for the nodes of a red-black tree

Nested classes inherited from class net.datastructures.BinarySearchTree

BinarySearchTree.BSTEntry

Field Summary

Fields inherited from class net.datastructures.BinarySearchTree

actionPos, C, numEntries

Fields inherited from class net.datastructures.LinkedBinaryTree

root, size

Constructor Summary

RBTree()

RBTree(Comparator C)

Method Summary

protected BTPosition	createNode(Object element, BTPosition parent, BTPosition left, BTPosition right) Creates a new tree node.
protected boolean	hasRedChild(Position position) Returns whether a node has a red child.
Entry	insert(Object k, Object x) Inserts an item into the dictionary and returns the newly created entry.
protected boolean	isPosRed(Position position) Returns whether a node is red.
protected Position	redChild(Position position) Returns a red child of a node.
protected void	remedyDoubleBlack(Position posR) Remedies a double black violation at a given node caused by removal.
protected void	remedyDoubleRed(Position posZ) Remedies a double red violation at a given node caused by insertion.
Entry	remove(Entry ent) Removes and returns the given entry from the dictionary.
protected void	setBlack(Position position) Colors a node black.
protected void	setColor(Position position, boolean color) Sets the color of a node.
protected void	setRed(Position position) Colors a node red.
protected void	swap(Position swapPos, Position remPos) Swaps the colors and elements at the two nodes.
protected boolean	swapColor(Position a, Position 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, elements, expandExternal, hasLeft, hasRight, inorderPositions, insertLeft, insertRight, isExternal, isInternal, isRoot, left, parent, positions, 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(Comparator C)

Method Detail

createNode

protected BTPosition createNode(Object element,
                                BTPosition parent,
                                BTPosition left,
                                BTPosition right)

Creates a new tree node.

Overrides:

createNode in class LinkedBinaryTree

insert

public Entry insert(Object k,
                    Object x)
             throws InvalidKeyException

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

Specified by:

insert in interface Dictionary

Overrides:

insert in class BinarySearchTree

Throws:

InvalidKeyException

remedyDoubleRed

protected void remedyDoubleRed(Position posZ)

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

remove

public Entry remove(Entry ent)
             throws InvalidEntryException

Removes and returns the given entry from the dictionary.

Specified by:

remove in interface Dictionary

Overrides:

remove in class BinarySearchTree

Throws:

InvalidEntryException

remedyDoubleBlack

protected void remedyDoubleBlack(Position posR)

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

isPosRed

protected boolean isPosRed(Position position)

Returns whether a node is red.

setRed

protected void setRed(Position position)

Colors a node red.

setBlack

protected void setBlack(Position position)

Colors a node black.

setColor

protected void setColor(Position 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 redChild(Position position)

Returns a red child of a node.

hasRedChild

protected boolean hasRedChild(Position position)

Returns whether a node has a red child.

swapColor

protected boolean swapColor(Position a,
                            Position b)

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

swap

protected void swap(Position swapPos,
                    Position remPos)

Swaps the colors and elements at the two nodes.