Top Description Inners Fields Constructors Methods
org.apache.commons.math3.geometry.partitioning.utilities

public Class AVLTree<T extends Comparable<T>>

extends Object
Class Inheritance
Annotations
@Deprecated
Type Parameters
<T>
the type of the elements

Deprecated

as of 3.4, this class is not used anymore and considered to be out of scope of Apache Commons Math

This class implements AVL trees.

The purpose of this class is to sort elements while allowing duplicate elements (i.e. such that a.equals(b) is true). The SortedSet interface does not allow this, so a specific class is needed. Null elements are not allowed.

Since the equals method is not sufficient to differentiate elements, the delete method is implemented using the equality operator.

In order to clearly mark the methods provided here do not have the same semantics as the ones specified in the SortedSet interface, different names are used (add has been replaced by insert and remove has been replaced by delete).

This class is based on the C implementation Georg Kraml has put in the public domain. Unfortunately, his page seems not to exist any more.

Since
3.0

Nested and Inner Type Summary

Modifier and TypeClass and Description
public class
AVLTree.Node

This class implements AVL trees nodes.

private static enum
AVLTree.Skew

Enum for tree skew factor.

Field Summary

Modifier and TypeField and Description
private AVLTree<T>.Node
top

Top level node.

Constructor Summary

AccessConstructor and Description
public
AVLTree()

Build an empty tree.

Method Summary

Modifier and TypeMethod and Description
public boolean

Returns:

true if the element was deleted from the tree
delete(final T
element to delete (silently ignored if null)
element)

Delete an element from the tree.

public AVLTree<T>.Node

Returns:

the tree node containing the largest element in the tree or null if the tree is empty
getLargest()

Get the node whose element is the largest one in the tree.

public AVLTree<T>.Node

Returns:

the tree node containing the largest element not larger than the reference object (in which case the node is guaranteed not to be empty) or null if either the tree is empty or all its elements are larger than the reference object
getNotLarger(final T
reference object (may not be in the tree)
reference)

Get the node whose element is not larger than the reference object.

public AVLTree<T>.Node

Returns:

the tree node containing the smallest element not smaller than the reference object or null if either the tree is empty or all its elements are smaller than the reference object
getNotSmaller(final T
reference object (may not be in the tree)
reference)

Get the node whose element is not smaller than the reference object.

public AVLTree<T>.Node

Returns:

the tree node containing the smallest element in the tree or null if the tree is empty
getSmallest()

Get the node whose element is the smallest one in the tree.

public void
insert(final T
element to insert (silently ignored if null)
element)

Insert an element in the tree.

public boolean

Returns:

true if the tree is empty
isEmpty()

Check if the tree is empty.

public int

Returns:

number of elements contained in the tree
size()

Get the number of elements of the tree.

Inherited from java.lang.Object:
cloneequalsfinalizegetClasshashCodenotifynotifyAlltoStringwaitwaitwait

Field Detail

topback to summary
private AVLTree<T>.Node top

Top level node.

Constructor Detail

AVLTreeback to summary
public AVLTree()

Build an empty tree.

Method Detail

deleteback to summary
public boolean delete(final T element)

Delete an element from the tree.

The element is deleted only if there is a node n containing exactly the element instance specified, i.e. for which n.getElement() == element. This is purposely different from the specification of the java.util.Set remove method (in fact, this is the reason why a specific class has been developed).

Parameters
element:T

element to delete (silently ignored if null)

Returns:boolean

true if the element was deleted from the tree

getLargestback to summary
public AVLTree<T>.Node getLargest()

Get the node whose element is the largest one in the tree.

Returns:AVLTree<T>.Node

the tree node containing the largest element in the tree or null if the tree is empty

See Also
getSmallest, getNotSmaller, getNotLarger, Node#getPrevious, Node#getNext
getNotLargerback to summary
public AVLTree<T>.Node getNotLarger(final T reference)

Get the node whose element is not larger than the reference object.

Parameters
reference:T

reference object (may not be in the tree)

Returns:AVLTree<T>.Node

the tree node containing the largest element not larger than the reference object (in which case the node is guaranteed not to be empty) or null if either the tree is empty or all its elements are larger than the reference object

See Also
getSmallest, getLargest, getNotSmaller, Node#getPrevious, Node#getNext
getNotSmallerback to summary
public AVLTree<T>.Node getNotSmaller(final T reference)

Get the node whose element is not smaller than the reference object.

Parameters
reference:T

reference object (may not be in the tree)

Returns:AVLTree<T>.Node

the tree node containing the smallest element not smaller than the reference object or null if either the tree is empty or all its elements are smaller than the reference object

See Also
getSmallest, getLargest, getNotLarger, Node#getPrevious, Node#getNext
getSmallestback to summary
public AVLTree<T>.Node getSmallest()

Get the node whose element is the smallest one in the tree.

Returns:AVLTree<T>.Node

the tree node containing the smallest element in the tree or null if the tree is empty

See Also
getLargest, getNotSmaller, getNotLarger, Node#getPrevious, Node#getNext
insertback to summary
public void insert(final T element)

Insert an element in the tree.

Parameters
element:T

element to insert (silently ignored if null)

isEmptyback to summary
public boolean isEmpty()

Check if the tree is empty.

Returns:boolean

true if the tree is empty

sizeback to summary
public int size()

Get the number of elements of the tree.

Returns:int

number of elements contained in the tree

org.apache.commons.math3.geometry.partitioning.utilities back to summary

public Class AVLTree.Node

extends Object
Class Inheritance
  • java.lang.Object
  • org.apache.commons.math3.geometry.partitioning.utilities.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.

See Also
AVLTree

Field Summary

Modifier and TypeField and Description
private T
element

Element contained in the current node.

private AVLTree<T>.Node
left

Left sub-tree.

private AVLTree<T>.Node
parent

Parent tree.

private AVLTree<T>.Node
right

Right sub-tree.

private AVLTree.Skew
skew

Skew factor.

Constructor Summary

AccessConstructor and Description
pack-priv
Node(final T
element
element, final AVLTree<T>.Node
parent node
parent)

Build a node for a specified element.

Method Summary

Modifier and TypeMethod and Description
public void
delete()

Delete the node from the tree.

public T

Returns:

element contained in the node
getElement()

Get the contained element.

pack-priv AVLTree<T>.Node

Returns:

the tree node containing the largest element in the tree rooted at this node or null if the tree is empty
getLargest()

Get the node whose element is the largest one in the tree rooted at this node.

public AVLTree<T>.Node

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
getNext()

Get the node containing the next larger or equal element.

public AVLTree<T>.Node

Returns:

node containing the next smaller or equal element or null if there is no smaller or equal element in the tree
getPrevious()

Get the node containing the next smaller or equal element.

pack-priv AVLTree<T>.Node

Returns:

the tree node containing the smallest element in the tree rooted at this node or null if the tree is empty
getSmallest()

Get the node whose element is the smallest one in the tree rooted at this node.

pack-priv boolean

Returns:

true if the parent tree should be re-Skew.BALANCED
insert(final T
element to insert
newElement)

Insert an element in a sub-tree.

private boolean

Returns:

true if the parent tree should be reSkew.BALANCED too
rebalanceLeftGrown()

Re-balance the instance as left sub-tree has grown.

private boolean

Returns:

true if the parent tree should be reSkew.BALANCED too
rebalanceLeftShrunk()

Re-balance the instance as left sub-tree has shrunk.

private boolean

Returns:

true if the parent tree should be reSkew.BALANCED too
rebalanceRightGrown()

Re-balance the instance as right sub-tree has grown.

private boolean

Returns:

true if the parent tree should be reSkew.BALANCED too
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.

pack-priv int

Returns:

number of elements contained in the tree rooted at this node
size()

Get the number of elements of the tree rooted at this node.

Inherited from java.lang.Object:
cloneequalsfinalizegetClasshashCodenotifynotifyAlltoStringwaitwaitwait

Field Detail

elementback to summary
private T element

Element contained in the current node.

leftback to summary
private AVLTree<T>.Node left

Left sub-tree.

parentback to summary
private AVLTree<T>.Node parent

Parent tree.

rightback to summary
private AVLTree<T>.Node right

Right sub-tree.

skewback to summary
private AVLTree.Skew skew

Skew factor.

Constructor Detail

Nodeback to summary
pack-priv Node(final T element, final AVLTree<T>.Node parent)

Build a node for a specified element.

Parameters
element:T

element

parent:AVLTree<T>.Node

parent node

Method Detail

deleteback to summary
public void delete()

Delete the node from the tree.

getElementback to summary
public T getElement()

Get the contained element.

Returns:T

element contained in the node

getLargestback to summary
pack-priv AVLTree<T>.Node getLargest()

Get the node whose element is the largest one in the tree rooted at this node.

Returns:AVLTree<T>.Node

the tree node containing the largest element in the tree rooted at this node or null if the tree is empty

See Also
getSmallest
getNextback to summary
public AVLTree<T>.Node getNext()

Get the node containing the next larger or equal element.

Returns:AVLTree<T>.Node

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
getPreviousback to summary
public AVLTree<T>.Node getPrevious()

Get the node containing the next smaller or equal element.

Returns:AVLTree<T>.Node

node containing the next smaller or equal element or null if there is no smaller or equal element in the tree

See Also
getNext
getSmallestback to summary
pack-priv AVLTree<T>.Node getSmallest()

Get the node whose element is the smallest one in the tree rooted at this node.

Returns:AVLTree<T>.Node

the tree node containing the smallest element in the tree rooted at this node or null if the tree is empty

See Also
getLargest
insertback to summary
pack-priv boolean insert(final T newElement)

Insert an element in a sub-tree.

Parameters
newElement:T

element to insert

Returns:boolean

true if the parent tree should be re-Skew.BALANCED

rebalanceLeftGrownback to summary
private boolean rebalanceLeftGrown()

Re-balance the instance as left sub-tree has grown.

Returns:boolean

true if the parent tree should be reSkew.BALANCED too

rebalanceLeftShrunkback to summary
private boolean rebalanceLeftShrunk()

Re-balance the instance as left sub-tree has shrunk.

Returns:boolean

true if the parent tree should be reSkew.BALANCED too

rebalanceRightGrownback to summary
private boolean rebalanceRightGrown()

Re-balance the instance as right sub-tree has grown.

Returns:boolean

true if the parent tree should be reSkew.BALANCED too

rebalanceRightShrunkback to summary
private boolean rebalanceRightShrunk()

Re-balance the instance as right sub-tree has shrunk.

Returns:boolean

true if the parent tree should be reSkew.BALANCED too

rotateCCWback to summary
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

rotateCWback to summary
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

sizeback to summary
pack-priv int size()

Get the number of elements of the tree rooted at this node.

Returns:int

number of elements contained in the tree rooted at this node

org.apache.commons.math3.geometry.partitioning.utilities back to summary

private final Enum AVLTree.Skew

extends Enum<AVLTree.Skew>
Class Inheritance
Enum for tree skew factor.

Field Summary

Modifier and TypeField and Description
public static final AVLTree.Skew
BALANCED

Code for Skew.BALANCED trees.

public static final AVLTree.Skew
LEFT_HIGH

Code for left high trees.

public static final AVLTree.Skew
RIGHT_HIGH

Code for right high trees.

Constructor Summary

AccessConstructor and Description
private
Skew()

Method Summary

Modifier and TypeMethod and Description
public static AVLTree.Skew
valueOf(String name)

public static AVLTree.Skew[]
values()

Inherited from java.lang.Enum:
clonecompareTodescribeConstableequalsfinalizegetDeclaringClasshashCodenameordinaltoStringvalueOf

Field Detail

BALANCEDback to summary
public static final AVLTree.Skew BALANCED

Code for Skew.BALANCED trees.

LEFT_HIGHback to summary
public static final AVLTree.Skew LEFT_HIGH

Code for left high trees.

RIGHT_HIGHback to summary
public static final AVLTree.Skew RIGHT_HIGH

Code for right high trees.

Constructor Detail

Skewback to summary
private Skew()

Method Detail

valueOfback to summary
public static AVLTree.Skew valueOf(String name)
valuesback to summary
public static AVLTree.Skew[] values()