Package edu.ksu.cis.viewer

Class Trie

java.lang.Object
edu.ksu.cis.viewer.Trie
All Implemented Interfaces:
BSTInterface, TreeInterface, Serializable
public final class Trie extends Object implements BSTInterface, TreeInterface
An immutable trie that can draw itself. The trie is immutable in the sense that any Trie returned by a public constructor or method cannot subsequently be changed. A trie is comprised of a nonempty tree containing all of the characters used in the strings that it stores. The root of the tree stores null, and its children store the first characters of all of the strings stored. Characters occurring in subsequent positions of a string are stored in children of the characters they follow. Nodes that end contained strings are colored red, and other nodes are colored black. Thus a string is contained in the trie if its first character is a child of the root, its second character is a child of that character, and so on until its last character is reached, and this character is red. If the empty string is to be stored, the root will be drawn red. The children of a given node will be drawn in order of their Unicode values.
Author:
Rod Howell (rhowell@ksu.edu)
See Also:

  • Constructor Details

    • Trie

      public Trie()
      Constructs an empty Trie.

  • Method Details

    • put

      public BSTInterface put(String key) throws NullPointerException
      Returns the Trie resulting from the insertion of key into this Trie. If key is already in this Trie, an identical Trie will be 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 Trie resulting from the removal of key from this Trie. If key is not in this Trie, an identical Trie 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 Trie.
      Specified by:
      getDrawing in interface BSTInterface
      Returns:
      a drawing of the tree

    • getDrawing

      public JComponent getDrawing(Font fnt) throws NullPointerException
      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 Trie.
      Specified by:
      clone in interface BSTInterface
      Overrides:
      clone in class Object
      Returns:
      a clone of the this tree

    • getRoot

      public Object getRoot()
      Returns the root of this Trie. This method is intended for use by the TreeDrawing class.
      Specified by:
      getRoot in interface TreeInterface
      Returns:
      the root of this tree
      See Also:

    • getChildren

      public TreeInterface[] getChildren()
      Returns the children of this Trie. This method is intended for use by the TreeDrawing class.
      Specified by:
      getChildren in interface TreeInterface
      Returns:
      an array containing the children of this tree

    • isEmpty

      public boolean isEmpty()
      Always returns false. This method is intended for use by the TreeDrawing class.
      Specified by:
      isEmpty in interface TreeInterface
      Returns:
      whether this tree is empty