Module org.jgrapht.core
Package org.jgrapht.util

Class AVLTree<T>

java.lang.Object
org.jgrapht.util.AVLTree<T>
Type Parameters:
T - the key data type
All Implemented Interfaces:
Iterable<T>
public class AVLTree<T> extends Object implements 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.

  • Field Details

    • 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 Details

    • 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 Details

    • addMax

      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

    • addMaxNode

      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

    • addMin

      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

    • addMinNode

      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

    • makeRoot

      private void makeRoot(AVLTree.TreeNode<T> node)
      Makes the node 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 subtree
      right - a right subtree
      p - next parent node
      leftMove - 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 the left and right subtrees using the junctionNode.

      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 subtrees
      left - a left subtree
      right - a right subtree
      Returns:
      the root of the resulting tree

    • swap

      private void swap(AVLTree<T> tree)
      Swaps the contents of this tree and the tree
      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 from node 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 from node up until the stop node
      Parameters:
      node - a node to start tree balancing from
      stop - a node to stop balancing at (this node is not being balanced)

    • balanceNode

      private AVLTree.TreeNode<T> balanceNode(AVLTree.TreeNode<T> node)
      Checks whether the node is unbalanced. If so, balances the node
      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 String toString()
      Overrides:
      toString in class Object

    • iterator

      public Iterator<T> iterator()
      Specified by:
      iterator in interface Iterable<T>

    • nodeIterator

      public 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