org.apache.directory.server.core.avltree

Class AvlTreeImpl<K>

java.lang.Object

org.apache.directory.server.core.avltree.AvlTreeImpl<K>

All Implemented Interfaces:

AvlTree<K>

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

An AVL tree implementation

Field Summary

Fields

Modifier and Type	Field and Description
private java.util.Comparator<K>	comparator The Comparator used for comparing the keys
private LinkedAvlNode<K>	first node representing the start of the doubly linked list formed with the tree nodes
private LinkedAvlNode<K>	last node representing the end of the doubly linked list formed with the tree nodes
private LinkedAvlNode<K>	root the root of the tree
private int	size size of the tree

Constructor Summary

Constructors

Constructor and Description
AvlTreeImpl(java.util.Comparator<K> comparator) Creates a new instance of AVLTree.

Method Summary

Modifier and Type	Method and Description
private void	balance(java.util.List<LinkedAvlNode<K>> treePath) Balances the tree by visiting the nodes present in the List of nodes present in the treePath parameter. This really does the balancing if the height of the tree is greater than 2 and the balance factor is greater than +1 or less than -1. For an excellent info please read the Wikipedia article on AVL tree.
private void	detachNodes(LinkedAvlNode<K> node, LinkedAvlNode<K> parentNode) Detach a LinkedAvlNode from its parent
private LinkedAvlNode<K>	fetchNonNullNode(K key, LinkedAvlNode<K> startNode, LinkedAvlNode<K> parent)
LinkedAvlNode<K>	find(K key) Find a LinkedAvlNode with the given key value in the tree.
private LinkedAvlNode<K>	find(K key, LinkedAvlNode<K> startNode)
private java.util.List<LinkedAvlNode<K>>	find(K key, LinkedAvlNode<K> startNode, java.util.List<LinkedAvlNode<K>> path) Find a LinkedAvlNode with the given key value in the tree starting from the startNode.
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.
private java.util.List<LinkedAvlNode<K>>	findMax(LinkedAvlNode<K> startNode) Find the LinkedAvlNode having the max key value in the tree starting from the startNode.
private java.util.List<LinkedAvlNode<K>>	findMin(LinkedAvlNode<K> startNode) Find the LinkedAvlNode having the min key value in the tree starting from the startNode.
private int	getBalance(LinkedAvlNode<K> node) Get balance-factor of the given LinkedAvlNode.
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.
private void	insertInList(LinkedAvlNode<K> node, LinkedAvlNode<K> parentNode, int pos)
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
private void	removeFromList(LinkedAvlNode<K> node)
private void	replaceNode(LinkedAvlNode<K> deleteNode, LinkedAvlNode<K> replaceNode, LinkedAvlNode<K> parentNode) Replace a LinkedAvlNode to be removed with a new existing LinkedAvlNode
private void	rotateSingleLeft(LinkedAvlNode<K> node, LinkedAvlNode<K> parentNode) Rotate the node left side once.
private void	rotateSingleRight(LinkedAvlNode<K> node, LinkedAvlNode<K> parentNode) Rotate the node right side once.
(package private) void	setFirst(LinkedAvlNode<K> first) Set the first element of the tree Note : this method is used by the deserialization method
(package private) void	setLast(LinkedAvlNode<K> last) Set the last element of the tree Note : this method is used by the deserialization method
(package private) void	setRoot(LinkedAvlNode<K> root) Set the root of the tree.
(package private) void	setSize(int size) Set the size of the tree.
private void	visit(LinkedAvlNode<K> node, LinkedAvlNode<K> parentNode)

Methods inherited from class java.lang.Object

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

Field Detail

root

private LinkedAvlNode<K> root

the root of the tree

comparator

private java.util.Comparator<K> comparator

The Comparator used for comparing the keys

first

private LinkedAvlNode<K> first

node representing the start of the doubly linked list formed with the tree nodes

last

private LinkedAvlNode<K> last

node representing the end of the doubly linked list formed with the tree nodes

size

private int size

size of the tree

Constructor Detail

AvlTreeImpl

public AvlTreeImpl(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()

Specified by:

getComparator in interface AvlTree<K>

Returns:

the comparator associated with this tree

insert

public K insert(K key)

Description copied from interface: AvlTree

Inserts a LinkedAvlNode with the given key.

Specified by:

insert in interface AvlTree<K>

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.

removeFromList

private void removeFromList(LinkedAvlNode<K> node)

insertInList

private void insertInList(LinkedAvlNode<K> node,
                          LinkedAvlNode<K> parentNode,
                          int pos)

remove

public K remove(K key)

Description copied from interface: AvlTree

Removes the LinkedAvlNode present in the tree with the given key value

Specified by:

remove in interface AvlTree<K>

Parameters:

key - the value of the node to be removed

Returns:

the removed key, if any, or null if the key does not exist

balance

private void balance(java.util.List<LinkedAvlNode<K>> treePath)

Balances the tree by visiting the nodes present in the List of nodes present in the treePath parameter.

This really does the balancing if the height of the tree is greater than 2 and the
balance factor is greater than +1 or less than -1.

For an excellent info please read the Wikipedia article on AVL tree.

Parameters:

treePath - the traversed list of LinkedAvlNodes after performing an insert/delete operation.

isEmpty

public boolean isEmpty()

Description copied from interface: AvlTree

Tests if the tree is logically empty.

Specified by:

isEmpty in interface AvlTree<K>

Returns:

true if the tree is empty, false otherwise

getSize

public int getSize()

Description copied from interface: AvlTree

returns the number of nodes present in this tree.

Specified by:

getSize in interface AvlTree<K>

Returns:

the number of nodes present in this tree

setSize

void setSize(int size)

Set the size of the tree. Note : this method is used by the deserialization method

Parameters:

size - the size of the tree

setRoot

void setRoot(LinkedAvlNode<K> root)

Set the root of the tree. Note : this method is used by the deserialization method

Parameters:

root - the root of the tree

setFirst

void setFirst(LinkedAvlNode<K> first)

Set the first element of the tree Note : this method is used by the deserialization method

Parameters:

first - the first element to be added

setLast

void setLast(LinkedAvlNode<K> last)

Set the last element of the tree Note : this method is used by the deserialization method

Parameters:

last - the last element to be added

getRoot

public LinkedAvlNode<K> getRoot()

Specified by:

getRoot in interface AvlTree<K>

Returns:

the root element of this tree (ie, not the first, but the topmost element)

getKeys

public java.util.List<K> getKeys()

Specified by:

getKeys in interface AvlTree<K>

Returns:

a list of the stored keys in this tree

printTree

public void printTree()

Description copied from interface: AvlTree

Prints the contents of AVL tree in pretty format

Specified by:

printTree in interface AvlTree<K>

getFirst

public LinkedAvlNode<K> getFirst()

Specified by:

getFirst in interface AvlTree<K>

Returns:

The first element of this tree

getLast

public LinkedAvlNode<K> getLast()

Specified by:

getLast in interface AvlTree<K>

Returns:

The last element in this tree

rotateSingleLeft

private void rotateSingleLeft(LinkedAvlNode<K> node,
                              LinkedAvlNode<K> parentNode)

Rotate the node left side once.

Parameters:

node - the LinkedAvlNode to be rotated

parentNode - parent LinkedAvlNode of node

rotateSingleRight

private void rotateSingleRight(LinkedAvlNode<K> node,
                               LinkedAvlNode<K> parentNode)

Rotate the node right side once.

Parameters:

node - the LinkedAvlNode to be rotated

parentNode - parent LinkedAvlNode of node

detachNodes

private void detachNodes(LinkedAvlNode<K> node,
                         LinkedAvlNode<K> parentNode)

Detach a LinkedAvlNode from its parent

Parameters:

node - the LinkedAvlNode to be detached

parentNode - the parent LinkedAvlNode of the node

replaceNode

private void replaceNode(LinkedAvlNode<K> deleteNode,
                         LinkedAvlNode<K> replaceNode,
                         LinkedAvlNode<K> parentNode)

Replace a LinkedAvlNode to be removed with a new existing LinkedAvlNode

Parameters:

deleteNode - the LinkedAvlNode to be deleted

replaceNode - the LinkedAvlNode to replace the deleteNode

parentNode - the parent LinkedAvlNode of deleteNode

find

private java.util.List<LinkedAvlNode<K>> find(K key,
                                              LinkedAvlNode<K> startNode,
                                              java.util.List<LinkedAvlNode<K>> path)

Find a LinkedAvlNode with the given key value in the tree starting from the startNode.

Parameters:

key - the key to find

startNode - starting node of a subtree/tree

path - the list to be filled with traversed nodes

Returns:

the list of traversed LinkedAvlNodes.

findGreater

public LinkedAvlNode<K> findGreater(K key)

Description copied from interface: AvlTree

Finds a LinkedAvlNode whose key is higher than the given key.

Specified by:

findGreater in interface AvlTree<K>

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)

Description copied from interface: AvlTree

Finds a LinkedAvlNode whose key is higher than the given key.

Specified by:

findGreaterOrEqual in interface AvlTree<K>

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)

Description copied from interface: AvlTree

Finds a LinkedAvlNode whose key is lower than the given key.

Specified by:

findLess in interface AvlTree<K>

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)

Description copied from interface: AvlTree

Finds a LinkedAvlNode whose key is lower than the given key.

Specified by:

findLessOrEqual in interface AvlTree<K>

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.

fetchNonNullNode

private LinkedAvlNode<K> fetchNonNullNode(K key,
                                          LinkedAvlNode<K> startNode,
                                          LinkedAvlNode<K> parent)

find

public LinkedAvlNode<K> find(K key)

Description copied from interface: AvlTree

Find a LinkedAvlNode with the given key value in the tree.

Specified by:

find in interface AvlTree<K>

Parameters:

key - the key to find

Returns:

the list of traversed LinkedAvlNode.

find

private LinkedAvlNode<K> find(K key,
                              LinkedAvlNode<K> startNode)

findMax

private java.util.List<LinkedAvlNode<K>> findMax(LinkedAvlNode<K> startNode)

Find the LinkedAvlNode having the max key value in the tree starting from the startNode.

Parameters:

startNode - starting node of a subtree/tree

Returns:

the list of traversed LinkedAvlNodes.

findMin

private java.util.List<LinkedAvlNode<K>> findMin(LinkedAvlNode<K> startNode)

Find the LinkedAvlNode having the min key value in the tree starting from the startNode.

Parameters:

startNode - starting node of a subtree/tree

Returns:

the list of traversed LinkedAvlNodes.

getBalance

private int getBalance(LinkedAvlNode<K> node)

Get balance-factor of the given LinkedAvlNode.

Parameters:

node - a LinkedAvlNode

Returns:

balance-factor of the node

visit

private void visit(LinkedAvlNode<K> node,
                   LinkedAvlNode<K> parentNode)