## Class AVLTree<T>

• java.lang.Object
• org.jgrapht.util.AVLTree<T>
• Type Parameters:
T - the key data type
All Implemented Interfaces:
java.lang.Iterable<T>

public class AVLTree<T>
extends java.lang.Object
implements java.lang.Iterable<T>
Implementation of the AVL tree data structure. Note: this tree doesn't use key comparisons, so this tree can't be used as a binary search tree. This implies that the same key can be added to this tree multiple times.

AVL tree is a self-balancing 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

Nested Classes
Modifier and Type Class Description
static class  AVLTree.TreeNode<T>
Container holding the values stored in the tree.
• ### Constructor Summary

Constructors
Constructor Description
AVLTree()
Constructs an empty tree
• ### Method Summary

All Methods
Modifier and Type Method Description
AVLTree.TreeNode<T> addMax​(T value)
Adds value as a maximum element to this tree.
void addMaxNode​(AVLTree.TreeNode<T> newMax)
Adds the newMax as a maximum node to this tree.
AVLTree.TreeNode<T> addMin​(T value)
Adds the value as a minimum element to this tree
void addMinNode​(AVLTree.TreeNode<T> newMin)
Adds the newMin as a minimum node to this tree
void clear()
Removes all nodes from this tree.
AVLTree.TreeNode<T> getMax()
Returns the maximum node in this tree or null if the tree is empty.
AVLTree.TreeNode<T> getMin()
Returns the minimum node in this tree or null if the tree is empty.
AVLTree.TreeNode<T> getRoot()
Returns the root of this tree or null if this tree is empty.
int getSize()
Returns the size of this tree
boolean isEmpty()
Check if this tree is empty
java.util.Iterator<T> iterator()
void mergeAfter​(AVLTree<T> tree)
Append the nodes in the tree after the nodes in this tree.
void mergeBefore​(AVLTree<T> tree)
Prepends the nodes in the tree before the nodes in this tree.
java.util.Iterator<AVLTree.TreeNode<T>> nodeIterator()
Returns an iterator over the tree nodes rather than the node values.
AVLTree.TreeNode<T> predecessor​(AVLTree.TreeNode<T> node)
Returns the node, which is before the node in the order defined by this tree.
AVLTree.TreeNode<T> removeMax()
Removes the maximum node in this tree.
AVLTree.TreeNode<T> removeMin()
Removes the minimum node in this tree.
AVLTree<T> splitAfter​(AVLTree.TreeNode<T> node)
Splits the tree into two parts.
AVLTree<T> splitBefore​(AVLTree.TreeNode<T> node)
Splits the tree into two parts.
AVLTree.TreeNode<T> successor​(AVLTree.TreeNode<T> node)
Returns the node following the node in the order defined by this tree.
java.lang.String 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 Detail

• #### AVLTree

public AVLTree()
Constructs an empty tree
• ### Method Detail

public AVLTree.TreeNode<T> addMax​(T value)
Adds value 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

public void addMaxNode​(AVLTree.TreeNode<T> newMax)
Adds the newMax as a maximum node to this tree.
Parameters:
newMax - a node to add as a tree max

public AVLTree.TreeNode<T> addMin​(T value)
Adds the value as a minimum element to this tree
Parameters:
value - a value to add as a tree min
Returns:
a tree node holding the value

public void addMinNode​(AVLTree.TreeNode<T> newMin)
Adds the newMin as a minimum node to this tree
Parameters:
newMin - a node to add as a tree min
• #### splitAfter

public AVLTree<T> splitAfter​(AVLTree.TreeNode<T> node)
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 the node. 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

public AVLTree<T> splitBefore​(AVLTree.TreeNode<T> node)
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 the node. 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

public void mergeAfter​(AVLTree<T> tree)
Append the nodes in the tree after the nodes in this tree.

The result of this operation is stored in this tree.

Parameters:
tree - a tree to append
• #### mergeBefore

public void mergeBefore​(AVLTree<T> tree)
Prepends the nodes in the tree before the nodes in this tree.

The result of this operation is stored in this tree.

Parameters:
tree - a tree to prepend
• #### removeMin

public AVLTree.TreeNode<T> removeMin()
Removes the minimum node in this tree. Returns null if this tree is empty
Returns:
the removed node or null if this tree is empty
• #### removeMax

public AVLTree.TreeNode<T> removeMax()
Removes the maximum node in this tree. Returns null if this tree is empty
Returns:
the removed node or null if this tree is empty
• #### getRoot

public AVLTree.TreeNode<T> 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

public AVLTree.TreeNode<T> successor​(AVLTree.TreeNode<T> node)
Returns the node following the node in the order defined by this tree. Returns null if the node is the maximum node in the tree.
Parameters:
node - a node to compute successor of
Returns:
the successor of the node
• #### predecessor

public AVLTree.TreeNode<T> predecessor​(AVLTree.TreeNode<T> node)
Returns the node, which is before the node in the order defined by this tree. Returns null if the node is the minimum node in the tree.
Parameters:
node - a node to compute predecessor of
Returns:
the predecessor of the node
• #### getMin

public AVLTree.TreeNode<T> 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

public AVLTree.TreeNode<T> 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

public java.lang.String toString()
Overrides:
toString in class java.lang.Object
• #### iterator

public java.util.Iterator<T> iterator()
Specified by:
iterator in interface java.lang.Iterable<T>
• #### nodeIterator

public java.util.Iterator<AVLTree.TreeNode<T>> 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