public class PuAVLTree
extends java.lang.Object
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.
Constructor and Description |
---|
PuAVLTree(PuCompare_If comparator)
Constructor
|
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.
|
public PuAVLTree(PuCompare_If comparator)
public int getSize()
public PuBinaryTreeNode getRoot()
public void setAvoidDuplicates(boolean flag)
public boolean getAvoidDuplicates()
public PuBinaryTreeNode[] getSortedList()
public int insert(java.lang.Object value)
value
- the object to be insertedpublic int getHeight()
public void remove(java.lang.Object value)
value
- the object to be removedpublic java.lang.Object findNode(java.lang.Object value)
value
- The object to be searched.public void removeNode(PuBinaryTreeNode node)
public int compareValue(java.lang.Object value1, java.lang.Object value2)
"