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