|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Objectorg.apache.commons.math3.geometry.partitioning.utilities.AVLTree.Node
public class AVLTree.Node
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.
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 |
---|
private T extends Comparable<T> element
private AVLTree.Node left
private AVLTree.Node right
private AVLTree.Node parent
private AVLTree.Skew skew
Constructor Detail |
---|
AVLTree.Node(T element, AVLTree.Node parent)
element
- elementparent
- parent nodeMethod Detail |
---|
public 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 insert
public 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
|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |