- Type Parameters:
T
- the key data type
- All Implemented Interfaces:
Iterable<T>
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 ClassesModifier and TypeClassDescriptionstatic class
Container holding the values stored in the tree.private class
Iterator over the tree nodes.private class
Iterator over the values stored in this tree. -
Field Summary
FieldsModifier and TypeFieldDescriptionprivate int
Modification trackerprivate AVLTree.TreeNode
<T> An auxiliary node which's always present in a tree and doesn't contain any data. -
Constructor Summary
ConstructorsModifierConstructorDescriptionAVLTree()
Constructs an empty treeprivate
AVLTree
(AVLTree.TreeNode<T> root) Constructor for internal usage -
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 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.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()
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.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.private void
Registers a modifying operationRemoves the maximum node in this tree.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.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.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.private void
Swaps the contents of this tree and thetree
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
-
Field Details
-
virtualRoot
An auxiliary node which's always present in a tree and doesn't contain any data. -
modCount
private int modCountModification tracker
-
-
Constructor Details
-
AVLTree
public AVLTree()Constructs an empty tree -
AVLTree
Constructor for internal usage- Parameters:
root
- the root of the newly create 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
-
makeRoot
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
Swaps the contents of this tree and thetree
- Parameters:
tree
- a tree to swap content of
-
rotateRight
Performs a right node rotation.- Parameters:
node
- a node to rotate- Returns:
- a new parent of the
node
-
rotateLeft
Performs a left node rotation.- Parameters:
node
- a node to rotate- Returns:
- a new parent of the
node
-
balance
Performs a node balancing on the path fromnode
up until the root- Parameters:
node
- a node to start tree balancing from
-
balance
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
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
-
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
-