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

Class 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

    • Constructor Detail

      • AVLTree

        public AVLTree()
        Constructs an empty tree

    • Method Detail

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