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

## Class AVLTree<T extends Comparable<T>>

- java.lang.Object
- - org.apache.commons.math3.geometry.partitioning.utilities.AVLTree<T>

Type Parameters:
  `T` - the type of the elements

    public class AVLTree<T extends Comparable<T>>
    extends Object

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
Version:
  $Id: AVLTree.java 1416643 2012-12-03 19:37:14Z tn $

### Nested Class Summary

Nested Classes
`class` `AVLTree.Node` This class implements AVL trees nodes.
`private static class` `AVLTree.Skew` Enum for tree skew factor.

### Field Summary

Fields
`private AVLTree.Node` `top` Top level node.

### Constructor Summary

Constructors
Constructor and Description
`AVLTree()` Build an empty tree.

### Method Summary

Methods
`boolean` `delete(T element)` Delete an element from the tree.
`AVLTree.Node` `getLargest()` Get the node whose element is the largest one in the tree.
`AVLTree.Node` `getNotLarger(T reference)` Get the node whose element is not larger than the reference object.
`AVLTree.Node` `getNotSmaller(T reference)` Get the node whose element is not smaller than the reference object.
`AVLTree.Node` `getSmallest()` Get the node whose element is the smallest one in the tree.
`void` `insert(T element)` Insert an element in the tree.
`boolean` `isEmpty()` Check if the tree is empty.
`int` `size()` 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

#### top

    private AVLTree.Node top

Top level node.

### Constructor Detail

#### AVLTree

    public AVLTree()

Build an empty tree.

### Method Detail

#### insert

    public void insert(T element)

Insert an element in the tree.

Parameters:
  `element` - element to insert (silently ignored if null)

#### delete

    public boolean delete(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` - element to delete (silently ignored if null)
Returns:
  true if the element was deleted from the tree

#### isEmpty

    public boolean isEmpty()

Check if the tree is empty.

Returns:
  true if the tree is empty

#### size

    public int size()

Get the number of elements of the tree.

Returns:
  number of elements contained in the tree

#### getSmallest

    public AVLTree.Node getSmallest()

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

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)

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)

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