jvx.util

Class PuAVLTree

java.lang.Object

jvx.util.PuAVLTree

public class PuAVLTree
extends java.lang.Object

AVL tree is a self-balancing binary search tree. For each node all nodes in the left sub-tree have smaller values, all nodes in the right sub-tree have greater values. For each node the longest path in its sub-tree to a leaf is stored (the "height" of the node).

The AVL tree is not perfectly balanced (this would take too much time for insert or delete operations), but it fulfills for every node the balance condition that the heights of the left and right sub-tree differ by not more than 1.

In case of an insert or delete operation which leads to violation of the balance condition for some node, the tree is re-balanced by rotate left or rotate right operations, i.e. the parent-child relation for a pair of nodes is inverted, including a re-assignment of the three affected sub-trees and the relation to the grand-parent of the former 'child' node.

Author:

Ulrich Reitebuch

Version:

24.04.13, 1.00 created (ur)

Constructor Summary

Constructors

Constructor and Description
PuAVLTree(PuCompare_If comparator) Constructor

Method Summary

Modifier and Type	Method and Description
int	compareValue(java.lang.Object value1, java.lang.Object value2) Compare value objects of two tree nodes.
java.lang.Object	findNode(java.lang.Object value) Find an object in the tree - if the Object does not exist, return null.
boolean	getAvoidDuplicates() Get flag to avoid duplicate tree nodes, i.e. nodes which are judged equal by the comparator.
int	getHeight() Get current height of tree.
PuBinaryTreeNode	getRoot() Return root node.
int	getSize() Return number of nodes in the tree.
PuBinaryTreeNode[]	getSortedList() Return all nodes as linear sorted list.
int	insert(java.lang.Object value) Insert a (new) object into the balanced binary search tree.
void	remove(java.lang.Object value) Remove an object from the balanced binary search tree.
void	removeNode(PuBinaryTreeNode node) Remove a node from the AVL tree.
void	setAvoidDuplicates(boolean flag) Set flag to avoid duplicate tree nodes, i.e. nodes which are judged equal by the comparator.

Methods inherited from class java.lang.Object

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

Constructor Detail

PuAVLTree

public PuAVLTree(PuCompare_If comparator)

Constructor

Method Detail

getSize

public int getSize()

Return number of nodes in the tree.

getRoot

public PuBinaryTreeNode getRoot()

Return root node.

setAvoidDuplicates

public void setAvoidDuplicates(boolean flag)

Set flag to avoid duplicate tree nodes, i.e. nodes which are judged equal by the comparator.

getAvoidDuplicates

public boolean getAvoidDuplicates()

Get flag to avoid duplicate tree nodes, i.e. nodes which are judged equal by the comparator.

getSortedList

public PuBinaryTreeNode[] getSortedList()

Return all nodes as linear sorted list.

insert

public int insert(java.lang.Object value)

Insert a (new) object into the balanced binary search tree.

Parameters:

value - the object to be inserted

Returns:

key of the object

getHeight

public int getHeight()

Get current height of tree.

remove

public void remove(java.lang.Object value)

Remove an object from the balanced binary search tree. Object will be searched by comparison of its value by the comparator.

Parameters:

value - the object to be removed

findNode

public java.lang.Object findNode(java.lang.Object value)

Find an object in the tree - if the Object does not exist, return null. If the object is found, this method will return the object with equal value from the tree.

Parameters:

value - The object to be searched.

Returns:

Return the Object in the tree or null.

removeNode

public void removeNode(PuBinaryTreeNode node)

Remove a node from the AVL tree.

compareValue

public int compareValue(java.lang.Object value1,
                        java.lang.Object value2)

Compare value objects of two tree nodes.

Returns:

value1 > value2 => 1, value1 == value2 => 0, value1 < value2 => -1.