org.apache.directory.server.core.avltree
Class AvlTree<K>

java.lang.Object
  extended by org.apache.directory.server.core.avltree.AvlTree<K>

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

An AVL tree implementation

Version:
$Rev$, $Date$
Author:
Apache Directory Project

Constructor Summary
AvlTree(java.util.Comparator<K> comparator)
          Creates a new instance of AVLTree.
 
Method Summary
 LinkedAvlNode<K> find(K key)
          Find a LinkedAvlNode with the given key value in the tree.
 LinkedAvlNode<K> findGreater(K key)
          Finds a LinkedAvlNode whose key is higher than the given key.
 LinkedAvlNode<K> findGreaterOrEqual(K key)
          Finds a LinkedAvlNode whose key is higher than the given key.
 LinkedAvlNode<K> findLess(K key)
          Finds a LinkedAvlNode whose key is lower than the given key.
 LinkedAvlNode<K> findLessOrEqual(K key)
          Finds a LinkedAvlNode whose key is lower than the given key.
 java.util.Comparator<K> getComparator()
           
 LinkedAvlNode<K> getFirst()
           
 java.util.List<K> getKeys()
           
 LinkedAvlNode<K> getLast()
           
 LinkedAvlNode<K> getRoot()
           
 int getSize()
          returns the number of nodes present in this tree.
 K insert(K key)
          Inserts a LinkedAvlNode with the given key.
 boolean isEmpty()
          Tests if the tree is logically empty.
 void printTree()
          Prints the contents of AVL tree in pretty format
 K remove(K key)
          Removes the LinkedAvlNode present in the tree with the given key value
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Constructor Detail

AvlTree

public AvlTree(java.util.Comparator<K> comparator)
Creates a new instance of AVLTree.

Parameters:
comparator - the comparator to be used for comparing keys
Method Detail

getComparator

public java.util.Comparator<K> getComparator()
Returns:
the comparator associated with this tree

insert

public K insert(K key)
Inserts a LinkedAvlNode with the given key.

Parameters:
key - the item to be inserted
Returns:
the replaced key if it already exists Note: Ignores if a node with the given key already exists.

remove

public K remove(K key)
Removes the LinkedAvlNode present in the tree with the given key value

Parameters:
key - the value of the node to be removed
Returns:
the removed key, if any, or null if the key does not exist

isEmpty

public boolean isEmpty()
Tests if the tree is logically empty.

Returns:
true if the tree is empty, false otherwise

getSize

public int getSize()
returns the number of nodes present in this tree.

Returns:
the number of nodes present in this tree

getRoot

public LinkedAvlNode<K> getRoot()
Returns:
the root element of this tree (ie, not the first, but the topmost element)

getKeys

public java.util.List<K> getKeys()
Returns:
a list of the stored keys in this tree

printTree

public void printTree()
Prints the contents of AVL tree in pretty format


getFirst

public LinkedAvlNode<K> getFirst()
Returns:
The first element of this tree

getLast

public LinkedAvlNode<K> getLast()
Returns:
The last element in this tree

findGreater

public LinkedAvlNode<K> findGreater(K key)
Finds a LinkedAvlNode whose key is higher than the given key.

Parameters:
key - the key
Returns:
the LinkedAvlNode whose key is greater than the given key ,
null if there is no node with a higher key than the given key.

findGreaterOrEqual

public LinkedAvlNode<K> findGreaterOrEqual(K key)
Finds a LinkedAvlNode whose key is higher than the given key.

Parameters:
key - the key
Returns:
the LinkedAvlNode whose key is greater than the given key ,
null if there is no node with a higher key than the given key.

findLess

public LinkedAvlNode<K> findLess(K key)
Finds a LinkedAvlNode whose key is lower than the given key.

Parameters:
key - the key
Returns:
the LinkedAvlNode whose key is lower than the given key ,
null if there is no node with a lower key than the given key.

findLessOrEqual

public LinkedAvlNode<K> findLessOrEqual(K key)
Finds a LinkedAvlNode whose key is lower than the given key.

Parameters:
key - the key
Returns:
the LinkedAvlNode whose key is lower than the given key ,
null if there is no node with a lower key than the given key.

find

public LinkedAvlNode<K> find(K key)
Find a LinkedAvlNode with the given key value in the tree.

Parameters:
key - the key to find
Returns:
the list of traversed LinkedAvlNode.


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