edu.ksu.cis.viewer
Class SplayTree

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

All Implemented Interfaces:

BSTInterface

public final class SplayTree

extends Object

implements BSTInterface

An immutable splay tree that can draw itself. A splay tree is self-adjusting in the sense that the deepest node accessed on any operation is brought to the root. By using double rotations whenever possible, logarathmic amortized peformance is achieved. This implementation is top-down. As a result, if a single rotation must occur, it occurs at the lowest point in the path traversed.

Author:

Rod Howell (howell@cis.ksu.edu)

Constructor Summary

SplayTree()
Constructs an empty SplayTree.

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 tree resulting from the insert of the given key.
BSTInterface	remove(String key) Returns the tree resulting from the removal of the given key.

Methods inherited from class java.lang.Object

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

Constructor Detail

SplayTree

public SplayTree()

Constructs an empty SplayTree.

Method Detail

put

public BSTInterface put(String key)
                 throws NullPointerException

Returns the tree resulting from the insert of the given key. If key is already in the tree, a tree having the same contents with key at the root is returned.

Specified by:

put in interface BSTInterface

Throws:

NullPointerException - If key is null

remove

public BSTInterface remove(String key)
                    throws NullPointerException

Returns the tree resulting from the removal of the given key. If the key is not in the tree, a tree having the same contents 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)
                      throws NullPointerException

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