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.

Constructor Summary

Constructors

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

Method Summary

Modifier and Type	Method and Description
Entry<K,V>	insert(K k, V x) Inserts an item into the dictionary and returns the newly created entry.
Entry<K,V>	remove(Entry<K,V> ent) Removes and returns the given entry from the dictionary.

Methods inherited from class net.datastructures.BinarySearchTree

entries, find, findAll, isEmpty, size

Methods inherited from class net.datastructures.LinkedBinaryTree

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

Methods inherited from class java.lang.Object

equals, 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

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

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