Class TreeList.AVLNode<E>
- java.lang.Object
-
- org.apache.commons.collections4.list.TreeList.AVLNode<E>
-
static class TreeList.AVLNode<E> extends java.lang.Object
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
Fields Modifier and Type Field Description private int
height
How many levels of left/right are below this one.private TreeList.AVLNode<E>
left
The left child node or the predecessor ifleftIsPrevious
.private boolean
leftIsPrevious
Flag indicating that left reference is not a subtree but the predecessor.private int
relativePosition
The relative position, root holds absolute position.private TreeList.AVLNode<E>
right
The right child node or the successor ifrightIsNext
.private boolean
rightIsNext
Flag indicating that right reference is not a subtree but the successor.private E
value
The stored element.
-
Constructor Summary
Constructors Modifier Constructor Description private
AVLNode(int relativePosition, E obj, TreeList.AVLNode<E> rightFollower, TreeList.AVLNode<E> leftFollower)
Constructs a new node with a relative position.private
AVLNode(java.util.Collection<? extends E> coll)
Constructs a new AVL tree from a collection.private
AVLNode(java.util.Iterator<? extends E> iterator, int start, int end, int absolutePositionOfParent, TreeList.AVLNode<E> prev, TreeList.AVLNode<E> next)
Constructs a new AVL tree from a collection.
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description private TreeList.AVLNode<E>
addAll(TreeList.AVLNode<E> otherTree, int currentSize)
Appends the elements of another tree list to this tree list by efficiently merging the two AVL trees.private TreeList.AVLNode<E>
balance()
Balances according to the AVL algorithm.(package private) TreeList.AVLNode<E>
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<E> node)
Returns the height of the node or -1 if the node is null.private TreeList.AVLNode<E>
getLeftSubTree()
Gets the left node, returning null if its a faedelung.private int
getOffset(TreeList.AVLNode<E> node)
Gets the relative position.private TreeList.AVLNode<E>
getRightSubTree()
Gets the right node, returning null if its a faedelung.(package private) E
getValue()
Gets the value.private int
heightRightMinusLeft()
Returns the height difference right - left(package private) int
indexOf(java.lang.Object object, int index)
Locate the index that contains the specified object.(package private) TreeList.AVLNode<E>
insert(int index, E obj)
Inserts a node at the position index.private TreeList.AVLNode<E>
insertOnLeft(int indexRelativeToMe, E obj)
private TreeList.AVLNode<E>
insertOnRight(int indexRelativeToMe, E obj)
private TreeList.AVLNode<E>
max()
Gets the rightmost child of this node.private TreeList.AVLNode<E>
min()
Gets the leftmost child of this node.(package private) TreeList.AVLNode<E>
next()
Gets the next node in the list after this one.(package private) TreeList.AVLNode<E>
previous()
Gets the node in the list before this one.private void
recalcHeight()
Sets the height by calculation.(package private) TreeList.AVLNode<E>
remove(int index)
Removes the node at a given position.private TreeList.AVLNode<E>
removeMax()
private TreeList.AVLNode<E>
removeMin()
private TreeList.AVLNode<E>
removeSelf()
Removes this node from the tree.private TreeList.AVLNode<E>
rotateLeft()
private TreeList.AVLNode<E>
rotateRight()
private void
setLeft(TreeList.AVLNode<E> node, TreeList.AVLNode<E> previous)
Sets the left field to the node, or the previous node if that is nullprivate int
setOffset(TreeList.AVLNode<E> node, int newOffest)
Sets the relative position.private void
setRight(TreeList.AVLNode<E> node, TreeList.AVLNode<E> next)
Sets the right field to the node, or the next node if that is null(package private) void
setValue(E obj)
Sets the value.(package private) void
toArray(java.lang.Object[] array, int index)
Stores the node and its children into the array specified.java.lang.String
toString()
Used for debugging.
-
-
-
Field Detail
-
left
private TreeList.AVLNode<E> left
The left child node or the predecessor ifleftIsPrevious
.
-
leftIsPrevious
private boolean leftIsPrevious
Flag indicating that left reference is not a subtree but the predecessor.
-
right
private TreeList.AVLNode<E> right
The right child node or the successor ifrightIsNext
.
-
rightIsNext
private boolean rightIsNext
Flag indicating that right reference is not a subtree but the successor.
-
height
private int height
How many levels of left/right are below this one.
-
relativePosition
private int relativePosition
The relative position, root holds absolute position.
-
value
private E value
The stored element.
-
-
Constructor Detail
-
AVLNode
private AVLNode(int relativePosition, E obj, TreeList.AVLNode<E> rightFollower, TreeList.AVLNode<E> leftFollower)
Constructs a new node with a relative position.- Parameters:
relativePosition
- the relative position of the nodeobj
- the value for the noderightFollower
- the node with the value following this oneleftFollower
- the node with the value leading this one
-
AVLNode
private AVLNode(java.util.Collection<? extends E> coll)
Constructs a new AVL tree from a collection.The collection must be nonempty.
- Parameters:
coll
- a nonempty collection
-
AVLNode
private AVLNode(java.util.Iterator<? extends E> iterator, int start, int end, int absolutePositionOfParent, TreeList.AVLNode<E> prev, TreeList.AVLNode<E> next)
Constructs a new AVL tree from a collection.This is a recursive helper for
AVLNode(Collection)
. A call to this method will construct the subtree for elementsstart
throughend
of the collection, assuming the iteratore
already points at elementstart
.- Parameters:
iterator
- an iterator over the collection, which should already point to the element at indexstart
within the collectionstart
- the index of the first element in the collection that should be in this subtreeend
- the index of the last element in the collection that should be in this subtreeabsolutePositionOfParent
- absolute position of this node's parent, or 0 if this node is the rootprev
- theAVLNode
corresponding to element (start - 1) of the collection, or null if start is 0next
- theAVLNode
corresponding to element (end + 1) of the collection, or null if end is the last element of the collection
-
-
Method Detail
-
getValue
E getValue()
Gets the value.- Returns:
- the value of this node
-
setValue
void setValue(E obj)
Sets the value.- Parameters:
obj
- the value to store
-
get
TreeList.AVLNode<E> get(int index)
Locate the element with the given index relative to the offset of the parent of this node.
-
indexOf
int indexOf(java.lang.Object object, int index)
Locate the index that contains the specified object.
-
toArray
void toArray(java.lang.Object[] array, int index)
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<E> next()
Gets the next node in the list after this one.- Returns:
- the next node
-
previous
TreeList.AVLNode<E> previous()
Gets the node in the list before this one.- Returns:
- the previous node
-
insert
TreeList.AVLNode<E> insert(int index, E obj)
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
private TreeList.AVLNode<E> insertOnLeft(int indexRelativeToMe, E obj)
-
insertOnRight
private TreeList.AVLNode<E> insertOnRight(int indexRelativeToMe, E obj)
-
getLeftSubTree
private TreeList.AVLNode<E> getLeftSubTree()
Gets the left node, returning null if its a faedelung.
-
getRightSubTree
private TreeList.AVLNode<E> getRightSubTree()
Gets the right node, returning null if its a faedelung.
-
max
private TreeList.AVLNode<E> max()
Gets the rightmost child of this node.- Returns:
- the rightmost child (greatest index)
-
min
private TreeList.AVLNode<E> min()
Gets the leftmost child of this node.- Returns:
- the leftmost child (smallest index)
-
remove
TreeList.AVLNode<E> remove(int index)
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
private TreeList.AVLNode<E> removeMax()
-
removeMin
private TreeList.AVLNode<E> removeMin()
-
removeSelf
private TreeList.AVLNode<E> removeSelf()
Removes this node from the tree.- Returns:
- the node that replaces this one in the parent
-
balance
private TreeList.AVLNode<E> balance()
Balances according to the AVL algorithm.
-
getOffset
private int getOffset(TreeList.AVLNode<E> node)
Gets the relative position.
-
setOffset
private int setOffset(TreeList.AVLNode<E> node, int newOffest)
Sets the relative position.
-
recalcHeight
private void recalcHeight()
Sets the height by calculation.
-
getHeight
private int getHeight(TreeList.AVLNode<E> node)
Returns the height of the node or -1 if the node is null.
-
heightRightMinusLeft
private int heightRightMinusLeft()
Returns the height difference right - left
-
rotateLeft
private TreeList.AVLNode<E> rotateLeft()
-
rotateRight
private TreeList.AVLNode<E> rotateRight()
-
setLeft
private void setLeft(TreeList.AVLNode<E> node, TreeList.AVLNode<E> previous)
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
private void setRight(TreeList.AVLNode<E> node, TreeList.AVLNode<E> next)
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
-
addAll
private TreeList.AVLNode<E> addAll(TreeList.AVLNode<E> otherTree, int currentSize)
Appends the elements of another tree list to this tree list by efficiently merging the two AVL trees. This operation is destructive to both trees and runs in O(log(m + n)) time.- Parameters:
otherTree
- the root of the AVL tree to merge with this onecurrentSize
- the number of elements in this AVL tree- Returns:
- the root of the new, merged AVL tree
-
toString
public java.lang.String toString()
Used for debugging.- Overrides:
toString
in classjava.lang.Object
-
-