 Type Parameters:
T
 the key data type
 All Implemented Interfaces:
Iterable<T>
AVL tree is a selfbalancing binary tree data structure. In an AVL tree, the heights of two child subtrees differ by at most one. This ensures that the height of the tree is $\mathcal{O}(\log n)$ where $n$ is the number of elements in the tree. Also this tree doesn't support key comparisons, it does define an element order. As a result, this tree can be used to query node successor/predecessor.
Subtree query means that the result is being computed only on the subtree nodes. This tree supports the following operations:
 Min/max insertion and deletion in $\mathcal{O}(\log n)$ time
 Subtree min/max queries in $\mathcal{O}(1)$ time
 Node successor/predecessor queries in $\mathcal{O}(1)$ time
 Tree split in $\mathcal{O}(\log n)$ time
 Tree merge in $\mathcal{O}(\log n)$ time
This implementation gives users access to the tree nodes which hold the inserted elements. The user is able to store the tree nodes references but isn't able to modify them.
 Author:
 Timofey Chudakov

Nested Class Summary
Modifier and TypeClassDescriptionstatic class
Container holding the values stored in the tree. 
Constructor Summary

Method Summary
Modifier and TypeMethodDescriptionAddsvalue
as a maximum element to this tree.void
addMaxNode
(AVLTree.TreeNode<T> newMax) Adds thenewMax
as a maximum node to this tree.Adds thevalue
as a minimum element to this treevoid
addMinNode
(AVLTree.TreeNode<T> newMin) Adds thenewMin
as a minimum node to this treevoid
clear()
Removes all nodes from this tree.getMax()
Returns the maximum node in this tree or null if the tree is empty.getMin()
Returns the minimum node in this tree or null if the tree is empty.getRoot()
Returns the root of this tree or null if this tree is empty.int
getSize()
Returns the size of this treeboolean
isEmpty()
Check if this tree is emptyiterator()
void
mergeAfter
(AVLTree<T> tree) Append the nodes in thetree
after the nodes in this tree.void
mergeBefore
(AVLTree<T> tree) Prepends the nodes in thetree
before the nodes in this tree.Returns an iterator over the tree nodes rather than the node values.predecessor
(AVLTree.TreeNode<T> node) Returns the node, which is before thenode
in the order defined by this tree.Removes the maximum node in this tree.Removes the minimum node in this tree.splitAfter
(AVLTree.TreeNode<T> node) Splits the tree into two parts.splitBefore
(AVLTree.TreeNode<T> node) Splits the tree into two parts.successor
(AVLTree.TreeNode<T> node) Returns the node following thenode
in the order defined by this tree.toString()
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
Methods inherited from interface java.lang.Iterable
forEach, spliterator

Constructor Details

AVLTree
public AVLTree()Constructs an empty tree


Method Details

addMax
Addsvalue
as a maximum element to this tree. The running time of this method is $\mathcal{O}(\log n)$ Parameters:
value
 a value to add as a tree max Returns:
 a tree node holding the
value

addMaxNode
Adds thenewMax
as a maximum node to this tree. Parameters:
newMax
 a node to add as a tree max

addMin
Adds thevalue
as a minimum element to this tree Parameters:
value
 a value to add as a tree min Returns:
 a tree node holding the
value

addMinNode
Adds thenewMin
as a minimum node to this tree Parameters:
newMin
 a node to add as a tree min

splitAfter
Splits the tree into two parts.The first part contains the nodes which are smaller than or equal to the
node
. The first part stays in this tree. The second part contains the nodes which are strictly greater than thenode
. The second part is returned as a tree. Parameters:
node
 a separating node Returns:
 a tree containing the nodes which are strictly greater than the
node

splitBefore
Splits the tree into two parts.The first part contains the nodes which are smaller than the
node
. The first part stays in this tree. The second part contains the nodes which are greater than or equal to thenode
. The second part is returned as a tree. Parameters:
node
 a separating node Returns:
 a tree containing the nodes which are greater than or equal to the
node

mergeAfter
Append the nodes in thetree
after the nodes in this tree.The result of this operation is stored in this tree.
 Parameters:
tree
 a tree to append

mergeBefore
Prepends the nodes in thetree
before the nodes in this tree.The result of this operation is stored in this tree.
 Parameters:
tree
 a tree to prepend

removeMin
Removes the minimum node in this tree. Returnsnull
if this tree is empty Returns:
 the removed node or
null
if this tree is empty

removeMax
Removes the maximum node in this tree. Returnsnull
if this tree is empty Returns:
 the removed node or
null
if this tree is empty

getRoot
Returns the root of this tree or null if this tree is empty. Returns:
 the root of this tree or null if this tree is empty.

successor
Returns the node following thenode
in the order defined by this tree. Returns null if thenode
is the maximum node in the tree. Parameters:
node
 a node to compute successor of Returns:
 the successor of the
node

predecessor
Returns the node, which is before thenode
in the order defined by this tree. Returns null if thenode
is the minimum node in the tree. Parameters:
node
 a node to compute predecessor of Returns:
 the predecessor of the
node

getMin
Returns the minimum node in this tree or null if the tree is empty. Returns:
 the minimum node in this tree or null if the tree is empty.

getMax
Returns the maximum node in this tree or null if the tree is empty. Returns:
 the maximum node in this tree or null if the tree is empty.

isEmpty
public boolean isEmpty()Check if this tree is empty Returns:
true
if this tree is empty,false otherwise

clear
public void clear()Removes all nodes from this tree.Note: the memory allocated for the tree structure won't be deallocated until there are active external referenced to the nodes of this tree.

getSize
public int getSize()Returns the size of this tree Returns:
 the size of this tree

toString

iterator

nodeIterator
Returns an iterator over the tree nodes rather than the node values. The tree are returned in the same order as the tree values. Returns:
 an iterator over the tree nodes
