Class TreeList.AVLNode
java.lang.Object
org.apache.commons.collections.list.TreeList.AVLNode
- Enclosing class:
TreeList
Implements an AVLNode which keeps the offset updated.
This node contains the real work.
TreeList is just there to implement List
.
The nodes don't know the index of the object they are holding. They
do know however their position relative to their parent node.
This allows to calculate the index of a node while traversing the tree.
The Faedelung calculation stores a flag for both the left and right child to indicate if they are a child (false) or a link as in linked list (true).
-
Field Summary
FieldsModifier and TypeFieldDescriptionprivate int
How many levels of left/right are below this one.private TreeList.AVLNode
The left child node or the predecessor ifleftIsPrevious
.private boolean
Flag indicating that left reference is not a subtree but the predecessor.private int
The relative position, root holds absolute position.private TreeList.AVLNode
The right child node or the successor ifrightIsNext
.private boolean
Flag indicating that right reference is not a subtree but the successor.private Object
The stored element. -
Constructor Summary
ConstructorsModifierConstructorDescriptionprivate
AVLNode
(int relativePosition, Object obj, TreeList.AVLNode rightFollower, TreeList.AVLNode leftFollower) Constructs a new node with a relative position. -
Method Summary
Modifier and TypeMethodDescriptionprivate TreeList.AVLNode
balance()
Balances according to the AVL algorithm.(package private) TreeList.AVLNode
get
(int index) Locate the element with the given index relative to the offset of the parent of this node.private int
getHeight
(TreeList.AVLNode node) Returns the height of the node or -1 if the node is null.private TreeList.AVLNode
Gets the left node, returning null if its a faedelung.private int
getOffset
(TreeList.AVLNode node) Gets the relative position.private TreeList.AVLNode
Gets the right node, returning null if its a faedelung.(package private) Object
getValue()
Gets the value.private int
Returns the height difference right - left(package private) int
Locate the index that contains the specified object.(package private) TreeList.AVLNode
Inserts a node at the position index.private TreeList.AVLNode
insertOnLeft
(int indexRelativeToMe, Object obj) private TreeList.AVLNode
insertOnRight
(int indexRelativeToMe, Object obj) private TreeList.AVLNode
max()
Gets the rightmost child of this node.private TreeList.AVLNode
min()
Gets the leftmost child of this node.(package private) TreeList.AVLNode
next()
Gets the next node in the list after this one.(package private) TreeList.AVLNode
previous()
Gets the node in the list before this one.private void
Sets the height by calculation.(package private) TreeList.AVLNode
remove
(int index) Removes the node at a given position.private TreeList.AVLNode
private TreeList.AVLNode
private TreeList.AVLNode
Removes this node from the tree.private TreeList.AVLNode
private TreeList.AVLNode
private void
setLeft
(TreeList.AVLNode node, TreeList.AVLNode previous) Sets the left field to the node, or the previous node if that is nullprivate int
setOffset
(TreeList.AVLNode node, int newOffest) Sets the relative position.private void
setRight
(TreeList.AVLNode node, TreeList.AVLNode next) Sets the right field to the node, or the next node if that is null(package private) void
Sets the value.(package private) void
Stores the node and its children into the array specified.toString()
Used for debugging.
-
Field Details
-
left
The left child node or the predecessor ifleftIsPrevious
. -
leftIsPrevious
private boolean leftIsPreviousFlag indicating that left reference is not a subtree but the predecessor. -
right
The right child node or the successor ifrightIsNext
. -
rightIsNext
private boolean rightIsNextFlag indicating that right reference is not a subtree but the successor. -
height
private int heightHow many levels of left/right are below this one. -
relativePosition
private int relativePositionThe relative position, root holds absolute position. -
value
The stored element.
-
-
Constructor Details
-
AVLNode
private AVLNode(int relativePosition, Object obj, TreeList.AVLNode rightFollower, TreeList.AVLNode leftFollower) Constructs a new node with a relative position.- Parameters:
relativePosition
- the relative position of the nodeobj
- the value for the ndoerightFollower
- the node with the value following this oneleftFollower
- the node with the value leading this one
-
-
Method Details
-
getValue
Object getValue()Gets the value.- Returns:
- the value of this node
-
setValue
Sets the value.- Parameters:
obj
- the value to store
-
get
Locate the element with the given index relative to the offset of the parent of this node. -
indexOf
Locate the index that contains the specified object. -
toArray
Stores the node and its children into the array specified.- Parameters:
array
- the array to be filledindex
- the index of this node
-
next
TreeList.AVLNode next()Gets the next node in the list after this one.- Returns:
- the next node
-
previous
TreeList.AVLNode previous()Gets the node in the list before this one.- Returns:
- the previous node
-
insert
Inserts a node at the position index.- Parameters:
index
- is the index of the position relative to the position of the parent node.obj
- is the object to be stored in the position.
-
insertOnLeft
-
insertOnRight
-
getLeftSubTree
Gets the left node, returning null if its a faedelung. -
getRightSubTree
Gets the right node, returning null if its a faedelung. -
max
Gets the rightmost child of this node.- Returns:
- the rightmost child (greatest index)
-
min
Gets the leftmost child of this node.- Returns:
- the leftmost child (smallest index)
-
remove
Removes the node at a given position.- Parameters:
index
- is the index of the element to be removed relative to the position of the parent node of the current node.
-
removeMax
-
removeMin
-
removeSelf
Removes this node from the tree.- Returns:
- the node that replaces this one in the parent
-
balance
Balances according to the AVL algorithm. -
getOffset
Gets the relative position. -
setOffset
Sets the relative position. -
recalcHeight
private void recalcHeight()Sets the height by calculation. -
getHeight
Returns the height of the node or -1 if the node is null. -
heightRightMinusLeft
private int heightRightMinusLeft()Returns the height difference right - left -
rotateLeft
-
rotateRight
-
setLeft
Sets the left field to the node, or the previous node if that is null- Parameters:
node
- the new left subtree nodeprevious
- the previous node in the linked list
-
setRight
Sets the right field to the node, or the next node if that is null- Parameters:
node
- the new left subtree nodenext
- the next node in the linked list
-
toString
Used for debugging.
-