Class AVLTree.TreeNode<T>

java.lang.Object
org.jgrapht.util.AVLTree.TreeNode<T>
Type Parameters:
T - a tree node value type
Enclosing class:
AVLTree<T>

public static class AVLTree.TreeNode<T> extends Object
Container holding the values stored in the tree.
  • Field Details

    • value

      T value
      A value stored in this tree node
    • parent

      Parent of this node
    • left

      Left child of this 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 Details

    • TreeNode

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

    • 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 String toString()
      Overrides:
      toString in class Object