edu.ksu.cis.viewer
Class RedBlackTree

java.lang.Object
  edu.ksu.cis.viewer.RedBlackTree

All Implemented Interfaces:

BSTInterface

public final class RedBlackTree

extends Object

implements BSTInterface

An immutable red-black tree that can draw itself. A red-black tree is a binary search tree with the following properties:

1. Each node is colored either red or black.
2. The root is black.
3. If an internal node is red, its parent is black.
4. For every empty subtree, the number of black proper ancestors is the same.

Author:

Rod Howell (howell@cis.ksu.edu)

Constructor Summary

RedBlackTree()
Constructs an empty RedBlackTree.

Method Summary

Object	clone() Because this structure is immutable, this method simply returns this tree.
JComponent	getDrawing() Returns a drawing of this tree.
JComponent	getDrawing(Font fnt) Returns a drawing of this tree using the given Font.
BSTInterface	put(String key) Returns the RedBlackTree resulting from the insertion of key into this RedBlackTree.
BSTInterface	remove(String key) Returns the RedBlackTree resulting from the removal of key from this RedBlackTree.

Methods inherited from class java.lang.Object

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

Constructor Detail

RedBlackTree

public RedBlackTree()

Constructs an empty RedBlackTree.

Method Detail

put

public BSTInterface put(String key)
                 throws NullPointerException

Returns the RedBlackTree resulting from the insertion of key into this RedBlackTree. If key is already in this tree, an identical tree is returned.

Specified by:

put in interface BSTInterface

Throws:

NullPointerException - If key is null

remove

public BSTInterface remove(String key)
                    throws NullPointerException

Returns the RedBlackTree resulting from the removal of key from this RedBlackTree. If key is not in this tree, an identical tree is returned.

Specified by:

remove in interface BSTInterface

Throws:

NullPointerException - If key is null

getDrawing

public JComponent getDrawing()

Returns a drawing of this tree.

Specified by:

getDrawing in interface BSTInterface

getDrawing

public JComponent getDrawing(Font fnt)

Returns a drawing of this tree using the given Font.

Specified by:

getDrawing in interface BSTInterface

Throws:

NullPointerException - if fnt is null.

clone

public Object clone()

Because this structure is immutable, this method simply returns this tree.

Specified by:

clone in interface BSTInterface