- java.lang.Object
-
- org.jgrapht.util.AVLTree.TreeNode<T>
-
-
Field Summary
Fields Modifier and Type Field Description (package private) int
height
Height of the node(package private) AVLTree.TreeNode<T>
left
Left child of this node(package private) AVLTree.TreeNode<T>
parent
Parent of this node(package private) AVLTree.TreeNode<T>
predecessor
Previous node in the tree according to the in order traversal(package private) AVLTree.TreeNode<T>
right
Right child of this node(package private) AVLTree.TreeNode<T>
subtreeMax
A maximum node in the subtree rooted at this node(package private) AVLTree.TreeNode<T>
subtreeMin
A minimum node in the subtree rooted at this node(package private) int
subtreeSize
Size of the subtree rooted at this node(package private) AVLTree.TreeNode<T>
successor
Next node in the tree according to the in order traversal(package private) T
value
A value stored in this tree node
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description (package private) int
getHeight()
Returns a height of this nodeAVLTree.TreeNode<T>
getLeft()
Returns a left child of this node(package private) int
getLeftHeight()
Returns a height of the left subtree(package private) int
getLeftSubtreeSize()
Returns a size of the left subtreeAVLTree.TreeNode<T>
getParent()
Returns a parent of this nodeAVLTree.TreeNode<T>
getPredecessor()
Returns a predecessor of this node according to the tree in order traversal, ornull
if this node is a minimum node in the treeAVLTree.TreeNode<T>
getRight()
Returns a right child of this node(package private) int
getRightHeight()
Returns a height of the right subtree(package private) int
getRightSubtreeSize()
Returns a size of the right subtreeAVLTree.TreeNode<T>
getRoot()
Returns a root of the tree this node is stored inAVLTree.TreeNode<T>
getSubtreeMax()
Returns a maximum node stored in the subtree rooted at this nodeAVLTree.TreeNode<T>
getSubtreeMin()
Returns a minimum node stored in the subtree rooted at this node(package private) int
getSubtreeSize()
Returns a subtree size of the tree rooted at this nodeAVLTree.TreeNode<T>
getSuccessor()
Returns a successor of this node according to the tree in order traversal, ornull
if this node is a maximum node in the treeAVLTree.TreeNode<T>
getTreeMax()
Returns a maximum node stored in the treeAVLTree.TreeNode<T>
getTreeMin()
Returns a minimum node stored in the treeT
getValue()
Returns a value stored in this node(package private) boolean
isLeftChild()
Returnstrue
if this node is a left child of its parent,false
otherwise(package private) boolean
isLeftDoubleHeavy()
Returnstrue
if this node is unbalanced and the left child's height is greater,false otherwise
(package private) boolean
isLeftHeavy()
Returnstrue
if the height of the left child is greater than the height of the right child(package private) boolean
isRightChild()
Returnstrue
if this node is a right child of its parent,false
otherwise(package private) boolean
isRightDoubleHeavy()
Returnstrue
if this node is unbalanced and the right child's height is greater,false otherwise
(package private) boolean
isRightHeavy()
Returnstrue
if the height of the right child is greater than the height of the left child(package private) void
reset()
Resets this node to the default state(package private) void
setLeftChild(AVLTree.TreeNode<T> node)
Sets the left child reference of this node tonode
.(package private) void
setPredecessor(AVLTree.TreeNode<T> node)
Updates the predecessor reference of this node.(package private) void
setRightChild(AVLTree.TreeNode<T> node)
Sets the right child reference of this node tonode
.(package private) void
setSuccessor(AVLTree.TreeNode<T> node)
Updates the successor reference of this node.(package private) void
substituteChild(AVLTree.TreeNode<T> prevChild, AVLTree.TreeNode<T> newChild)
Substitutes theprevChild
with thenewChild
.java.lang.String
toString()
(package private) void
updateHeightAndSubtreeSize()
Updates the height and subtree size of this node according to the values of the left and right children
-
-
-
Field Detail
-
value
T value
A value stored in this tree node
-
parent
AVLTree.TreeNode<T> parent
Parent of this node
-
left
AVLTree.TreeNode<T> left
Left child of this node
-
right
AVLTree.TreeNode<T> right
Right 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 Detail
-
TreeNode
TreeNode(T value)
Constructs a new node with thevalue
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()
Returnstrue
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()
Returnstrue
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()
Returnstrue
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()
Returnstrue
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()
Returnstrue
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()
Returnstrue
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, ornull
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, ornull
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 thenode
is notnull
, 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 thenode
is notnull
, 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 tonode
. If thenode
is notnull
, 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 tonode
. If thenode
is notnull
, updates its parent reference as well.- Parameters:
node
- a new right child
-
substituteChild
void substituteChild(AVLTree.TreeNode<T> prevChild, AVLTree.TreeNode<T> newChild)
Substitutes theprevChild
with thenewChild
. If thenewChild
is notnull
, updates its parent reference as well- Parameters:
prevChild
- either left or right child of this nodenewChild
- a new child of this node
-
toString
public java.lang.String toString()
- Overrides:
toString
in classjava.lang.Object
-
-