Class AVLTree<T extends java.lang.Comparable<T>>
- java.lang.Object
-
- org.apache.commons.math3.geometry.partitioning.utilities.AVLTree<T>
-
- Type Parameters:
T
- the type of the elements
@Deprecated public class AVLTree<T extends java.lang.Comparable<T>> extends java.lang.Object
Deprecated.as of 3.4, this class is not used anymore and considered to be out of scope of Apache Commons MathThis 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). TheSortedSet
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, thedelete
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 byinsert
andremove
has been replaced bydelete
).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 Class Summary
Nested Classes Modifier and Type Class Description class
AVLTree.Node
Deprecated.This class implements AVL trees nodes.
-
Constructor Summary
Constructors Constructor Description AVLTree()
Deprecated.Build an empty tree.
-
Method Summary
All Methods Instance Methods Concrete Methods Deprecated Methods Modifier and Type Method Description boolean
delete(T element)
Deprecated.Delete an element from the tree.AVLTree.Node
getLargest()
Deprecated.Get the node whose element is the largest one in the tree.AVLTree.Node
getNotLarger(T reference)
Deprecated.Get the node whose element is not larger than the reference object.AVLTree.Node
getNotSmaller(T reference)
Deprecated.Get the node whose element is not smaller than the reference object.AVLTree.Node
getSmallest()
Deprecated.Get the node whose element is the smallest one in the tree.void
insert(T element)
Deprecated.Insert an element in the tree.boolean
isEmpty()
Deprecated.Check if the tree is empty.int
size()
Deprecated.Get the number of elements of the tree.
-
-
-
Method Detail
-
insert
public void insert(T element)
Deprecated.Insert an element in the tree.- Parameters:
element
- element to insert (silently ignored if null)
-
delete
public boolean delete(T element)
Deprecated.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 whichn.getElement() == element
. This is purposely different from the specification of thejava.util.Set
remove
method (in fact, this is the reason why a specific class has been developed).- Parameters:
element
- element to delete (silently ignored if null)- Returns:
- true if the element was deleted from the tree
-
isEmpty
public boolean isEmpty()
Deprecated.Check if the tree is empty.- Returns:
- true if the tree is empty
-
size
public int size()
Deprecated.Get the number of elements of the tree.- Returns:
- number of elements contained in the tree
-
getSmallest
public AVLTree.Node getSmallest()
Deprecated.Get the node whose element is the smallest one in the tree.- Returns:
- the tree node containing the smallest element in the tree or null if the tree is empty
- See Also:
getLargest()
,getNotSmaller(T)
,getNotLarger(T)
,AVLTree.Node.getPrevious()
,AVLTree.Node.getNext()
-
getLargest
public AVLTree.Node getLargest()
Deprecated.Get the node whose element is the largest one in the tree.- Returns:
- the tree node containing the largest element in the tree or null if the tree is empty
- See Also:
getSmallest()
,getNotSmaller(T)
,getNotLarger(T)
,AVLTree.Node.getPrevious()
,AVLTree.Node.getNext()
-
getNotSmaller
public AVLTree.Node getNotSmaller(T reference)
Deprecated.Get the node whose element is not smaller than the reference object.- Parameters:
reference
- reference object (may not be in the tree)- 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
- See Also:
getSmallest()
,getLargest()
,getNotLarger(T)
,AVLTree.Node.getPrevious()
,AVLTree.Node.getNext()
-
getNotLarger
public AVLTree.Node getNotLarger(T reference)
Deprecated.Get the node whose element is not larger than the reference object.- Parameters:
reference
- reference object (may not be in the tree)- 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
- See Also:
getSmallest()
,getLargest()
,getNotSmaller(T)
,AVLTree.Node.getPrevious()
,AVLTree.Node.getNext()
-
-