org.apache.commons.math3.geometry.partitioning.utilities

## Class AVLTree.Node

- java.lang.Object
- - org.apache.commons.math3.geometry.partitioning.utilities.AVLTree.Node

- Enclosing class:
    AVLTree<T extends java.lang.Comparable<T>>

      public class AVLTree.Node
      extends java.lang.Object

  This class implements AVL trees nodes.

  AVL tree nodes implement all the logical structure of the tree. Nodes are created by the `AVLTree` class.

  The nodes are not independant from each other but must obey specific balancing constraints and the tree structure is rearranged as elements are inserted or deleted from the tree. The creation, modification and tree-related navigation methods have therefore restricted access. Only the order-related navigation, reading and delete methods are public.

  See Also:
    `AVLTree`

- - ### Field Summary

    Fields
    Modifier and Type | Field and Description
    --- | ---
    `private T` | `element` Element contained in the current node.
    `private AVLTree.Node` | `left` Left sub-tree.
    `private AVLTree.Node` | `parent` Parent tree.
    `private AVLTree.Node` | `right` Right sub-tree.
    `private AVLTree.Skew` | `skew` Skew factor.

  - ### Constructor Summary

    Constructors
    Constructor and Description
    `AVLTree.Node(T element, AVLTree.Node parent)` Build a node for a specified element.

  - ### Method Summary

    Methods
    Modifier and Type | Method and Description
    --- | ---
    `void` | `delete()` Delete the node from the tree.
    `T` | `getElement()` Get the contained element.
    `(package private) AVLTree.Node` | `getLargest()` Get the node whose element is the largest one in the tree rooted at this node.
    `AVLTree.Node` | `getNext()` Get the node containing the next larger or equal element.
    `AVLTree.Node` | `getPrevious()` Get the node containing the next smaller or equal element.
    `(package private) AVLTree.Node` | `getSmallest()` Get the node whose element is the smallest one in the tree rooted at this node.
    `(package private) boolean` | `insert(T newElement)` Insert an element in a sub-tree.
    `private boolean` | `rebalanceLeftGrown()` Re-balance the instance as left sub-tree has grown.
    `private boolean` | `rebalanceLeftShrunk()` Re-balance the instance as left sub-tree has shrunk.
    `private boolean` | `rebalanceRightGrown()` Re-balance the instance as right sub-tree has grown.
    `private boolean` | `rebalanceRightShrunk()` Re-balance the instance as right sub-tree has shrunk.
    `private void` | `rotateCCW()` Perform a counter-clockwise rotation rooted at the instance.
    `private void` | `rotateCW()` Perform a clockwise rotation rooted at the instance.
    `(package private) int` | `size()` Get the number of elements of the tree rooted at this node.

    - ### Methods inherited from class java.lang.Object

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

- - ### Field Detail

    - #### element

          private T extends java.lang.Comparable<T> element

      Element contained in the current node.

    - #### left

          private AVLTree.Node left

      Left sub-tree.

    - #### right

          private AVLTree.Node right

      Right sub-tree.

    - #### parent

          private AVLTree.Node parent

      Parent tree.

    - #### skew

          private AVLTree.Skew skew

      Skew factor.

  - ### Constructor Detail

    - #### AVLTree.Node

          AVLTree.Node(T element,
                      AVLTree.Node parent)

      Build a node for a specified element.
      Parameters:
        `element` - element
        `parent` - parent node

  - ### Method Detail

    - #### getElement

          public T getElement()

      Get the contained element.
      Returns:
        element contained in the node

    - #### size

          int size()

      Get the number of elements of the tree rooted at this node.
      Returns:
        number of elements contained in the tree rooted at this node

    - #### getSmallest

          AVLTree.Node getSmallest()

      Get the node whose element is the smallest one in the tree rooted at this node.
      Returns:
        the tree node containing the smallest element in the tree rooted at this node or null if the tree is empty
      See Also:
        `getLargest()`

    - #### getLargest

          AVLTree.Node getLargest()

      Get the node whose element is the largest one in the tree rooted at this node.
      Returns:
        the tree node containing the largest element in the tree rooted at this node or null if the tree is empty
      See Also:
        `getSmallest()`

    - #### getPrevious

          public AVLTree.Node getPrevious()

      Get the node containing the next smaller or equal element.
      Returns:
        node containing the next smaller or equal element or null if there is no smaller or equal element in the tree
      See Also:
        `getNext()`

    - #### getNext

          public AVLTree.Node getNext()

      Get the node containing the next larger or equal element.
      Returns:
        node containing the next larger or equal element (in which case the node is guaranteed not to be empty) or null if there is no larger or equal element in the tree
      See Also:
        `getPrevious()`

    - #### insert

          boolean insert(T newElement)

      Insert an element in a sub-tree.
      Parameters:
        `newElement` - element to insert
      Returns:
        true if the parent tree should be re-Skew.BALANCED

    - #### delete

          public void delete()

      Delete the node from the tree.

    - #### rebalanceLeftGrown

          private boolean rebalanceLeftGrown()

      Re-balance the instance as left sub-tree has grown.
      Returns:
        true if the parent tree should be reSkew.BALANCED too

    - #### rebalanceRightGrown

          private boolean rebalanceRightGrown()

      Re-balance the instance as right sub-tree has grown.
      Returns:
        true if the parent tree should be reSkew.BALANCED too

    - #### rebalanceLeftShrunk

          private boolean rebalanceLeftShrunk()

      Re-balance the instance as left sub-tree has shrunk.
      Returns:
        true if the parent tree should be reSkew.BALANCED too

    - #### rebalanceRightShrunk

          private boolean rebalanceRightShrunk()

      Re-balance the instance as right sub-tree has shrunk.
      Returns:
        true if the parent tree should be reSkew.BALANCED too

    - #### rotateCW

          private void rotateCW()

      Perform a clockwise rotation rooted at the instance.

      The skew factor are not updated by this method, they must be updated by the caller

    - #### rotateCCW

          private void rotateCCW()

      Perform a counter-clockwise rotation rooted at the instance.

      The skew factor are not updated by this method, they must be updated by the caller

Copyright (c) 2003-2013 Apache Software Foundation