org.apache.commons.math3.geometry.partitioning.utilities
public class AVLTree.Node extends java.lang.Object
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.
AVLTree
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 and Description |
---|
AVLTree.Node(T element,
AVLTree.Node parent)
Build a node for a specified element.
|
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.
|
private AVLTree.Node left
private AVLTree.Node right
private AVLTree.Node parent
private AVLTree.Skew skew
AVLTree.Node(T element, AVLTree.Node parent)
element
- elementparent
- parent nodepublic T getElement()
int size()
AVLTree.Node getSmallest()
getLargest()
AVLTree.Node getLargest()
getSmallest()
public AVLTree.Node getPrevious()
getNext()
public AVLTree.Node getNext()
getPrevious()
boolean insert(T newElement)
newElement
- element to insertpublic void delete()
private boolean rebalanceLeftGrown()
private boolean rebalanceRightGrown()
private boolean rebalanceLeftShrunk()
private boolean rebalanceRightShrunk()
private void rotateCW()
The skew factor are not updated by this method, they must be updated by the caller
private void rotateCCW()
The skew factor are not updated by this method, they must be updated by the caller
Copyright (c) 2003-2013 Apache Software Foundation