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.

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