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

java.lang.Object
  extended by 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)


Copyright © 2003-2009 Apache Software Foundation. All Rights Reserved.