Class AVLTree.Node
- java.lang.Object
-
- org.apache.commons.math3.geometry.partitioning.utilities.AVLTree.Node
-
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 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 Description Node(T element, AVLTree.Node parent)
Build a node for a specified element.
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method 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.
-
-
-
Field Detail
-
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
-
Node
Node(T element, AVLTree.Node parent)
Build a node for a specified element.- Parameters:
element
- elementparent
- 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
-
-