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

Class AVLTree.TreeNode<T>

  • Type Parameters:
    T - a tree node value type
    Enclosing class:
    AVLTree<T>
    public static class AVLTree.TreeNode<T>
extends java.lang.Object
    Container holding the values stored in the tree.

    • Field Detail

      • value

        T value
        A value stored in this tree node

      • successor

        AVLTree.TreeNode<T> successor
        Next node in the tree according to the in order traversal

      • predecessor

        AVLTree.TreeNode<T> predecessor
        Previous node in the tree according to the in order traversal

      • subtreeMin

        AVLTree.TreeNode<T> subtreeMin
        A minimum node in the subtree rooted at this node

      • subtreeMax

        AVLTree.TreeNode<T> subtreeMax
        A maximum node in the subtree rooted at this node

      • height

        int height
        Height of the node

      • subtreeSize

        int subtreeSize
        Size of the subtree rooted at this node

    • Constructor Detail

      • TreeNode

        TreeNode​(T value)
        Constructs a new node with the value stored in it
        Parameters:
        value - a value to store in this node

    • Method Detail

      • getValue

        public T getValue()
        Returns a value stored in this node
        Returns:
        a value stored in this node

      • getRoot

        public AVLTree.TreeNode<T> getRoot()
        Returns a root of the tree this node is stored in
        Returns:
        a root of the tree this node is stored in

      • getSubtreeMin

        public AVLTree.TreeNode<T> getSubtreeMin()
        Returns a minimum node stored in the subtree rooted at this node
        Returns:
        a minimum node stored in the subtree rooted at this node

      • getSubtreeMax

        public AVLTree.TreeNode<T> getSubtreeMax()
        Returns a maximum node stored in the subtree rooted at this node
        Returns:
        a maximum node stored in the subtree rooted at this node

      • getTreeMin

        public AVLTree.TreeNode<T> getTreeMin()
        Returns a minimum node stored in the tree
        Returns:
        a minimum node stored in the tree

      • getTreeMax

        public AVLTree.TreeNode<T> getTreeMax()
        Returns a maximum node stored in the tree
        Returns:
        a maximum node stored in the tree

      • getParent

        public AVLTree.TreeNode<T> getParent()
        Returns a parent of this node
        Returns:
        a parent of this node

      • getLeft

        public AVLTree.TreeNode<T> getLeft()
        Returns a left child of this node
        Returns:
        a left child of this node

      • getRight

        public AVLTree.TreeNode<T> getRight()
        Returns a right child of this node
        Returns:
        a right child of this node

      • getHeight

        int getHeight()
        Returns a height of this node
        Returns:
        a height of this node

      • getSubtreeSize

        int getSubtreeSize()
        Returns a subtree size of the tree rooted at this node
        Returns:
        a subtree size of the tree rooted at this node

      • reset

        void reset()
        Resets this node to the default state

      • getRightHeight

        int getRightHeight()
        Returns a height of the right subtree
        Returns:
        a height of the right subtree

      • getLeftHeight

        int getLeftHeight()
        Returns a height of the left subtree
        Returns:
        a height of the right subtree

      • getLeftSubtreeSize

        int getLeftSubtreeSize()
        Returns a size of the left subtree
        Returns:
        a size of the left subtree

      • getRightSubtreeSize

        int getRightSubtreeSize()
        Returns a size of the right subtree
        Returns:
        a size of the right subtree

      • updateHeightAndSubtreeSize

        void updateHeightAndSubtreeSize()
        Updates the height and subtree size of this node according to the values of the left and right children

      • isLeftDoubleHeavy

        boolean isLeftDoubleHeavy()
        Returns true if this node is unbalanced and the left child's height is greater, false otherwise
        Returns:
        true if this node is unbalanced and the left child's height is greater, false otherwise

      • isRightDoubleHeavy

        boolean isRightDoubleHeavy()
        Returns true if this node is unbalanced and the right child's height is greater, false otherwise
        Returns:
        true if this node is unbalanced and the right child's height is greater, false otherwise

      • isLeftHeavy

        boolean isLeftHeavy()
        Returns true if the height of the left child is greater than the height of the right child
        Returns:
        true if the height of the left child is greater than the height of the right child

      • isRightHeavy

        boolean isRightHeavy()
        Returns true if the height of the right child is greater than the height of the left child
        Returns:
        true if the height of the right child is greater than the height of the left child

      • isLeftChild

        boolean isLeftChild()
        Returns true if this node is a left child of its parent, false otherwise
        Returns:
        true if this node is a left child of its parent, false otherwise

      • isRightChild

        boolean isRightChild()
        Returns true if this node is a right child of its parent, false otherwise
        Returns:
        true if this node is a right child of its parent, false otherwise

      • getSuccessor

        public AVLTree.TreeNode<T> getSuccessor()
        Returns a successor of this node according to the tree in order traversal, or null if this node is a maximum node in the tree
        Returns:
        successor of this node, or null if this node in a maximum node in the tree

      • getPredecessor

        public AVLTree.TreeNode<T> getPredecessor()
        Returns a predecessor of this node according to the tree in order traversal, or null if this node is a minimum node in the tree
        Returns:
        predecessor of this node, or null if this node in a minimum node in the tree

      • setSuccessor

        void setSuccessor​(AVLTree.TreeNode<T> node)
        Updates the successor reference of this node. If the node is not null, updates its predecessor reference as well
        Parameters:
        node - new successor

      • setPredecessor

        void setPredecessor​(AVLTree.TreeNode<T> node)
        Updates the predecessor reference of this node. If the node is not null, updates its successor reference as well
        Parameters:
        node - new predecessor

      • setLeftChild

        void setLeftChild​(AVLTree.TreeNode<T> node)
        Sets the left child reference of this node to node. If the node is not null, updates its parent reference as well.
        Parameters:
        node - a new left child

      • setRightChild

        void setRightChild​(AVLTree.TreeNode<T> node)
        Sets the right child reference of this node to node. If the node is not null, updates its parent reference as well.
        Parameters:
        node - a new right child

      • substituteChild

        void substituteChild​(AVLTree.TreeNode<T> prevChild,
                     AVLTree.TreeNode<T> newChild)
        Substitutes the prevChild with the newChild. If the newChild is not null, updates its parent reference as well
        Parameters:
        prevChild - either left or right child of this node
        newChild - a new child of this node

      • toString

        public java.lang.String toString()
        Overrides:
        toString in class java.lang.Object