org.apache.directory.server.core.splay
Class SplayTree<K>

java.lang.Object
  org.apache.directory.server.core.splay.SplayTree<K>

public class SplayTree<K>
extends java.lang.Object

A generified, top-down, linked, in memory, splay tree implementation. This is an adaptation of the Danny Sleator's non-linked implementation here .

Version:

$Rev: 602753 $

Author:

Apache Directory Project

Constructor Summary

SplayTree(java.util.Comparator<K> keyComparator)

Method Summary

K	find(K key) Find an item in the tree.
K	findMax() Find the largest item in the tree.
K	findMin() Find the smallest item in the tree.
LinkedBinaryNode<K>	getFirst()
LinkedBinaryNode<K>	getLast()
LinkedBinaryNode<K>	getRoot()
void	insert(K key) Insert into the tree.
boolean	isEmpty() Test if the tree is logically empty.
static void	main(java.lang.String[] args)
void	printTree() Prints the contents of splay tree in pretty format
void	remove(K key) Remove from the tree.

Methods inherited from class java.lang.Object

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

Constructor Detail

SplayTree

public SplayTree(java.util.Comparator<K> keyComparator)

Method Detail

insert

public void insert(K key)

Insert into the tree.

Parameters:

x - the item to insert.

Throws:

DuplicateItemException - if x is already present.

remove

public void remove(K key)

Remove from the tree.

Parameters:

x - the item to remove.

Throws:

ItemNotFoundException - if x is not found.

findMin

public K findMin()

Find the smallest item in the tree.

findMax

public K findMax()

Find the largest item in the tree.

find

public K find(K key)

Find an item in the tree.

isEmpty

public boolean isEmpty()

Test if the tree is logically empty.

Returns:

true if empty, false otherwise.

getFirst

public LinkedBinaryNode<K> getFirst()

getLast

public LinkedBinaryNode<K> getLast()

getRoot

public LinkedBinaryNode<K> getRoot()

printTree

public void printTree()

Prints the contents of splay tree in pretty format

main

public static void main(java.lang.String[] args)