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.

Author:
Timofey Chudakov

  • Constructor Details

    • AVLTree

      public AVLTree()
      Constructs an empty 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

    • 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