- 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.
-
-
Nested Class Summary
Nested Classes Modifier and Type Class Description static class
AVLTree.TreeNode<T>
Container holding the values stored in the tree.private class
AVLTree.TreeNodeIterator
Iterator over the tree nodes.private class
AVLTree.TreeValuesIterator
Iterator over the values stored in this tree.
-
Field Summary
Fields Modifier and Type Field Description private int
modCount
Modification trackerprivate AVLTree.TreeNode<T>
virtualRoot
An auxiliary node which's always present in a tree and doesn't contain any data.
-
Constructor Summary
Constructors Modifier Constructor Description AVLTree()
Constructs an empty treeprivate
AVLTree(AVLTree.TreeNode<T> root)
Constructor for internal usage
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description AVLTree.TreeNode<T>
addMax(T value)
Addsvalue
as a maximum element to this tree.void
addMaxNode(AVLTree.TreeNode<T> newMax)
Adds thenewMax
as a maximum node to this tree.AVLTree.TreeNode<T>
addMin(T value)
Adds thevalue
as a minimum element to this treevoid
addMinNode(AVLTree.TreeNode<T> newMin)
Adds thenewMin
as a minimum node to this treeprivate void
balance(AVLTree.TreeNode<T> node)
Performs a node balancing on the path fromnode
up until the rootprivate void
balance(AVLTree.TreeNode<T> node, AVLTree.TreeNode<T> stop)
Performs a node balancing on the path fromnode
up until thestop
nodeprivate AVLTree.TreeNode<T>
balanceNode(AVLTree.TreeNode<T> node)
Checks whether thenode
is unbalanced.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 treeboolean
isEmpty()
Check if this tree is emptyjava.util.Iterator<T>
iterator()
private void
makeRoot(AVLTree.TreeNode<T> node)
Makes thenode
the root of this treeprivate AVLTree.TreeNode<T>
merge(AVLTree.TreeNode<T> junctionNode, AVLTree.TreeNode<T> left, AVLTree.TreeNode<T> right)
Merges theleft
andright
subtrees using thejunctionNode
.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.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 thenode
in the order defined by this tree.private void
registerModification()
Registers a modifying operationAVLTree.TreeNode<T>
removeMax()
Removes the maximum node in this tree.AVLTree.TreeNode<T>
removeMin()
Removes the minimum node in this tree.private AVLTree.TreeNode<T>
rotateLeft(AVLTree.TreeNode<T> node)
Performs a left node rotation.private AVLTree.TreeNode<T>
rotateRight(AVLTree.TreeNode<T> node)
Performs a right node rotation.private AVLTree<T>
split(AVLTree.TreeNode<T> left, AVLTree.TreeNode<T> right, AVLTree.TreeNode<T> p, boolean leftMove)
Traverses the tree up until the virtual root and splits it into two parts.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 thenode
in the order defined by this tree.private void
swap(AVLTree<T> tree)
Swaps the contents of this tree and thetree
java.lang.String
toString()
-
-
-
Field Detail
-
virtualRoot
private AVLTree.TreeNode<T> virtualRoot
An auxiliary node which's always present in a tree and doesn't contain any data.
-
modCount
private int modCount
Modification tracker
-
-
Constructor Detail
-
AVLTree
public AVLTree()
Constructs an empty tree
-
AVLTree
private AVLTree(AVLTree.TreeNode<T> root)
Constructor for internal usage- Parameters:
root
- the root of the newly create tree
-
-
Method Detail
-
addMax
public AVLTree.TreeNode<T> addMax(T value)
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
public void addMaxNode(AVLTree.TreeNode<T> newMax)
Adds thenewMax
as a maximum node to this tree.- Parameters:
newMax
- a node to add as a tree max
-
addMin
public AVLTree.TreeNode<T> addMin(T value)
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
public void addMinNode(AVLTree.TreeNode<T> newMin)
Adds thenewMin
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 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
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 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
public void mergeAfter(AVLTree<T> tree)
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
public void mergeBefore(AVLTree<T> tree)
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
public AVLTree.TreeNode<T> 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
public AVLTree.TreeNode<T> 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
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 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
public AVLTree.TreeNode<T> predecessor(AVLTree.TreeNode<T> node)
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
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
-
makeRoot
private void makeRoot(AVLTree.TreeNode<T> node)
Makes thenode
the root of this tree- Parameters:
node
- a new root of this tree
-
split
private AVLTree<T> split(AVLTree.TreeNode<T> left, AVLTree.TreeNode<T> right, AVLTree.TreeNode<T> p, boolean leftMove)
Traverses the tree up until the virtual root and splits it into two parts.The algorithm is described in Donald E. Knuth. The art of computer programming. Second Edition. Volume 3 / Sorting and Searching, p. 474.
- Parameters:
left
- a left subtreeright
- a right subtreep
- next parent nodeleftMove
-true
if we're moving from the left child,false
otherwise.- Returns:
- the resulting right tree
-
merge
private AVLTree.TreeNode<T> merge(AVLTree.TreeNode<T> junctionNode, AVLTree.TreeNode<T> left, AVLTree.TreeNode<T> right)
Merges theleft
andright
subtrees using thejunctionNode
.The algorithm is described in Donald E. Knuth. The art of computer programming. Second Edition. Volume 3 / Sorting and Searching, p. 474.
- Parameters:
junctionNode
- a node between left and right subtreesleft
- a left subtreeright
- a right subtree- Returns:
- the root of the resulting tree
-
swap
private void swap(AVLTree<T> tree)
Swaps the contents of this tree and thetree
- Parameters:
tree
- a tree to swap content of
-
rotateRight
private AVLTree.TreeNode<T> rotateRight(AVLTree.TreeNode<T> node)
Performs a right node rotation.- Parameters:
node
- a node to rotate- Returns:
- a new parent of the
node
-
rotateLeft
private AVLTree.TreeNode<T> rotateLeft(AVLTree.TreeNode<T> node)
Performs a left node rotation.- Parameters:
node
- a node to rotate- Returns:
- a new parent of the
node
-
balance
private void balance(AVLTree.TreeNode<T> node)
Performs a node balancing on the path fromnode
up until the root- Parameters:
node
- a node to start tree balancing from
-
balance
private void balance(AVLTree.TreeNode<T> node, AVLTree.TreeNode<T> stop)
Performs a node balancing on the path fromnode
up until thestop
node- Parameters:
node
- a node to start tree balancing fromstop
- a node to stop balancing at (this node is not being balanced)
-
balanceNode
private AVLTree.TreeNode<T> balanceNode(AVLTree.TreeNode<T> node)
Checks whether thenode
is unbalanced. If so, balances thenode
- Parameters:
node
- a node to balance- Returns:
- a new parent of
node
if the balancing occurs,node
otherwise
-
registerModification
private void registerModification()
Registers a modifying operation
-
toString
public java.lang.String toString()
- Overrides:
toString
in classjava.lang.Object
-
iterator
public java.util.Iterator<T> iterator()
- Specified by:
iterator
in interfacejava.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
-
-