java.lang.Object
org.jgrapht.util.AVLTree.TreeNode<T>
- Type Parameters:
T
- a tree node value type
Container holding the values stored in the tree.
-
Field Summary
FieldsModifier and TypeFieldDescription(package private) int
Height of the node(package private) AVLTree.TreeNode
<T> Left child of this node(package private) AVLTree.TreeNode
<T> Parent of this node(package private) AVLTree.TreeNode
<T> Previous node in the tree according to the in order traversal(package private) AVLTree.TreeNode
<T> Right child of this node(package private) AVLTree.TreeNode
<T> A maximum node in the subtree rooted at this node(package private) AVLTree.TreeNode
<T> A minimum node in the subtree rooted at this node(package private) int
Size of the subtree rooted at this node(package private) AVLTree.TreeNode
<T> Next node in the tree according to the in order traversal(package private) T
A value stored in this tree node -
Constructor Summary
Constructors -
Method Summary
Modifier and TypeMethodDescription(package private) int
Returns a height of this nodegetLeft()
Returns a left child of this node(package private) int
Returns a height of the left subtree(package private) int
Returns a size of the left subtreeReturns a parent of this nodeReturns a predecessor of this node according to the tree in order traversal, ornull
if this node is a minimum node in the treegetRight()
Returns a right child of this node(package private) int
Returns a height of the right subtree(package private) int
Returns a size of the right subtreegetRoot()
Returns a root of the tree this node is stored inReturns a maximum node stored in the subtree rooted at this nodeReturns a minimum node stored in the subtree rooted at this node(package private) int
Returns a subtree size of the tree rooted at this nodeReturns a successor of this node according to the tree in order traversal, ornull
if this node is a maximum node in the treeReturns a maximum node stored in the treeReturns a minimum node stored in the treegetValue()
Returns a value stored in this node(package private) boolean
Returnstrue
if this node is a left child of its parent,false
otherwise(package private) boolean
Returnstrue
if this node is unbalanced and the left child's height is greater,false otherwise
(package private) boolean
Returnstrue
if the height of the left child is greater than the height of the right child(package private) boolean
Returnstrue
if this node is a right child of its parent,false
otherwise(package private) boolean
Returnstrue
if this node is unbalanced and the right child's height is greater,false otherwise
(package private) boolean
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
.toString()
(package private) void
Updates the height and subtree size of this node according to the values of the left and right children
-
Field Details
-
value
T valueA value stored in this tree node -
parent
AVLTree.TreeNode<T> parentParent of this node -
left
AVLTree.TreeNode<T> leftLeft child of this node -
right
AVLTree.TreeNode<T> rightRight child of this node -
successor
AVLTree.TreeNode<T> successorNext node in the tree according to the in order traversal -
predecessor
AVLTree.TreeNode<T> predecessorPrevious node in the tree according to the in order traversal -
subtreeMin
AVLTree.TreeNode<T> subtreeMinA minimum node in the subtree rooted at this node -
subtreeMax
AVLTree.TreeNode<T> subtreeMaxA maximum node in the subtree rooted at this node -
height
int heightHeight of the node -
subtreeSize
int subtreeSizeSize of the subtree rooted at this node
-
-
Constructor Details
-
TreeNode
TreeNode(T value) Constructs a new node with thevalue
stored in it- Parameters:
value
- a value to store in this node
-
-
Method Details
-
getValue
Returns a value stored in this node- Returns:
- a value stored in this node
-
getRoot
Returns a root of the tree this node is stored in- Returns:
- a root of the tree this node is stored in
-
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
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
Returns a minimum node stored in the tree- Returns:
- a minimum node stored in the tree
-
getTreeMax
Returns a maximum node stored in the tree- Returns:
- a maximum node stored in the tree
-
getParent
Returns a parent of this node- Returns:
- a parent of this node
-
getLeft
Returns a left child of this node- Returns:
- a left child of this node
-
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
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
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
Updates the successor reference of this node. If thenode
is notnull
, updates its predecessor reference as well- Parameters:
node
- new successor
-
setPredecessor
Updates the predecessor reference of this node. If thenode
is notnull
, updates its successor reference as well- Parameters:
node
- new predecessor
-
setLeftChild
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
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
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
-