static class TreeList.AVLNode<E>
extends java.lang.Object
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).
| Modifier and Type | Field and 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 if
leftIsPrevious. |
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 if
rightIsNext. |
private boolean |
rightIsNext
Flag indicating that right reference is not a subtree but the successor.
|
private E |
value
The stored element.
|
| Modifier | Constructor and Description |
|---|---|
private |
AVLNode(java.util.Collection<? extends E> coll)
Constructs a new AVL tree from a collection.
|
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.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.
|
| Modifier and Type | Method and 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 null
|
private 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.
|
private TreeList.AVLNode<E> left
leftIsPrevious.private boolean leftIsPrevious
private TreeList.AVLNode<E> right
rightIsNext.private boolean rightIsNext
private int height
private int relativePosition
private E value
private AVLNode(int relativePosition,
E obj,
TreeList.AVLNode<E> rightFollower,
TreeList.AVLNode<E> leftFollower)
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 oneprivate AVLNode(java.util.Collection<? extends E> coll)
The collection must be nonempty.
coll - a nonempty collectionprivate AVLNode(java.util.Iterator<? extends E> iterator, int start, int end, int absolutePositionOfParent, TreeList.AVLNode<E> prev, TreeList.AVLNode<E> next)
This is a recursive helper for #AVLNode(Collection). A call
to this method will construct the subtree for elements start
through end of the collection, assuming the iterator
e already points at element start.
iterator - an iterator over the collection, which should already point
to the element at index start 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 - the AVLNode corresponding to element (start - 1)
of the collection, or null if start is 0next - the AVLNode corresponding to element (end + 1)
of the collection, or null if end is the last element of the collectionE getValue()
void setValue(E obj)
obj - the value to storeTreeList.AVLNode<E> get(int index)
int indexOf(java.lang.Object object,
int index)
void toArray(java.lang.Object[] array,
int index)
array - the array to be filledindex - the index of this nodeTreeList.AVLNode<E> next()
TreeList.AVLNode<E> previous()
TreeList.AVLNode<E> insert(int index, E obj)
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.private TreeList.AVLNode<E> insertOnLeft(int indexRelativeToMe, E obj)
private TreeList.AVLNode<E> insertOnRight(int indexRelativeToMe, E obj)
private TreeList.AVLNode<E> getLeftSubTree()
private TreeList.AVLNode<E> getRightSubTree()
private TreeList.AVLNode<E> max()
private TreeList.AVLNode<E> min()
TreeList.AVLNode<E> remove(int index)
index - is the index of the element to be removed relative to the position of
the parent node of the current node.private TreeList.AVLNode<E> removeMax()
private TreeList.AVLNode<E> removeMin()
private TreeList.AVLNode<E> removeSelf()
private TreeList.AVLNode<E> balance()
private int getOffset(TreeList.AVLNode<E> node)
private int setOffset(TreeList.AVLNode<E> node, int newOffest)
private void recalcHeight()
private int getHeight(TreeList.AVLNode<E> node)
private int heightRightMinusLeft()
private TreeList.AVLNode<E> rotateLeft()
private TreeList.AVLNode<E> rotateRight()
private void setLeft(TreeList.AVLNode<E> node, TreeList.AVLNode<E> previous)
node - the new left subtree nodeprevious - the previous node in the linked listprivate void setRight(TreeList.AVLNode<E> node, TreeList.AVLNode<E> next)
node - the new left subtree nodenext - the next node in the linked listprivate TreeList.AVLNode<E> addAll(TreeList.AVLNode<E> otherTree, int currentSize)
otherTree - the root of the AVL tree to merge with this onecurrentSize - the number of elements in this AVL treepublic java.lang.String toString()
toString in class java.lang.Object