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