Package edu.ksu.cis.viewer

Class RedBlackTree

java.lang.Object
edu.ksu.cis.viewer.RedBlackTree
All Implemented Interfaces:
BSTInterface, Serializable
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 (rhowell@ksu.edu)
See Also:

  • Constructor Details

    • RedBlackTree

      public RedBlackTree()
      Constructs an empty RedBlackTree.

  • Method Details

    • 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
      Parameters:
      key - the key to insert
      Returns:
      the resutling tree
      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
      Parameters:
      key - the key to remove
      Returns:
      the resulting tree
      Throws:
      NullPointerException - If key is null

    • getDrawing

      public JComponent getDrawing()
      Returns a drawing of this tree.
      Specified by:
      getDrawing in interface BSTInterface
      Returns:
      a drawing of the tree

    • getDrawing

      public JComponent getDrawing(Font fnt)
      Returns a drawing of this tree using the given Font.
      Specified by:
      getDrawing in interface BSTInterface
      Parameters:
      fnt - the font to use
      Returns:
      a drawing of the tree
      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
      Overrides:
      clone in class Object
      Returns:
      a clone of the this tree