net.datastructures
Class RBTreeMap<K,V>

java.lang.Object
  net.datastructures.LinkedBinaryTree<Entry<K,V>>
      net.datastructures.BinarySearchTreeMap<K,V>
          net.datastructures.RBTreeMap<K,V>

All Implemented Interfaces:

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

public class RBTreeMap<K,V>
extends BinarySearchTreeMap<K,V>
implements Map<K,V>

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

Nested Class Summary

protected static class

RBTreeMap.RBNode<K,V> Nested class for the nodes of a red-black tree

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

BinarySearchTreeMap.BSTEntry<K,V>

Field Summary

Fields inherited from class net.datastructures.BinarySearchTreeMap

actionPos, C, numEntries

Fields inherited from class net.datastructures.LinkedBinaryTree

root, size

Constructor Summary

RBTreeMap()

RBTreeMap(Comparator<K> C)

Method Summary

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.
protected boolean	isPosRed(Position<Entry<K,V>> position) Returns whether a node is red.
V	put(K k, V x) If there is an entry with the specified key, replaces the value of this entry with the specified value and returns the old value.
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.
V	remove(K k) If there is an entry with the specified key, removes this entry and returns its value.
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.BinarySearchTreeMap

checkEntry, checkKey, entry, entrySet, get, insertAtExternal, isEmpty, key, keySet, removeExternal, replaceEntry, restructure, size, treeSearch, value, values

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.Map

entrySet, get, isEmpty, keySet, size, values

Constructor Detail

RBTreeMap

public RBTreeMap()

RBTreeMap

public RBTreeMap(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>>

put

public V put(K k,
             V x)
      throws InvalidKeyException

If there is an entry with the specified key, replaces the value of this entry with the specified value and returns the old value. Else, adds a new entry with the specified key and value and returns null.

Specified by:

put in interface Map<K,V>

Overrides:

put in class BinarySearchTreeMap<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 V remove(K k)
         throws InvalidKeyException

If there is an entry with the specified key, removes this entry and returns its value. Else, returns null.

Specified by:

remove in interface Map<K,V>

Overrides:

remove in class BinarySearchTreeMap<K,V>

Throws:

InvalidKeyException

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.