org.apache.commons.math3.geometry.partitioning.utilities
Class AVLTree.Node

java.lang.Object
  extended by org.apache.commons.math3.geometry.partitioning.utilities.AVLTree.Node
Enclosing class:
AVLTree<T extends Comparable<T>>

public class AVLTree.Node
extends 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
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
AVLTree.Node(T element, AVLTree.Node parent)
          Build a node for a specified element.
 
Method Summary
 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 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