Package org.apache.commons.math3.geometry.partitioning.utilities

Class AVLTree<T extends java.lang.Comparable<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 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 Class Summary

      Nested Classes 
      Modifier and Type Class Description
      class  AVLTree.Node
      Deprecated.
      This class implements AVL trees nodes.
      private static class  AVLTree.Skew
      Deprecated.
      Enum for tree skew factor.

    • Field Summary

      Fields 
      Modifier and Type Field Description
      private AVLTree.Node top
      Deprecated.
      Top level node.

    • 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.

      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

    • Field Detail

    • Constructor Detail

      • AVLTree

        public AVLTree()
        Deprecated.
        Build an empty 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 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 - 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

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