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

    All Methods Instance Methods Concrete Methods
    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`.

"

The software JavaView? is copyright protected. All Rights Reserved.
"