static class TreeList.AVLNode
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 |
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 |
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 java.lang.Object |
value
The stored element.
|
Modifier | Constructor and Description |
---|---|
private |
AVLNode(int relativePosition,
java.lang.Object obj,
TreeList.AVLNode rightFollower,
TreeList.AVLNode leftFollower)
Constructs a new node with a relative position.
|
Modifier and Type | Method and Description |
---|---|
private 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 |
getLeftSubTree()
Gets the left node, returning null if its a faedelung.
|
private int |
getOffset(TreeList.AVLNode node)
Gets the relative position.
|
private TreeList.AVLNode |
getRightSubTree()
Gets the right node, returning null if its a faedelung.
|
(package private) java.lang.Object |
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 |
insert(int index,
java.lang.Object obj)
Inserts a node at the position index.
|
private TreeList.AVLNode |
insertOnLeft(int indexRelativeToMe,
java.lang.Object obj) |
private TreeList.AVLNode |
insertOnRight(int indexRelativeToMe,
java.lang.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 |
recalcHeight()
Sets the height by calculation.
|
(package private) TreeList.AVLNode |
remove(int index)
Removes the node at a given position.
|
private TreeList.AVLNode |
removeMax() |
private TreeList.AVLNode |
removeMin() |
private TreeList.AVLNode |
removeSelf()
Removes this node from the tree.
|
private TreeList.AVLNode |
rotateLeft() |
private TreeList.AVLNode |
rotateRight() |
private void |
setLeft(TreeList.AVLNode node,
TreeList.AVLNode previous)
Sets the left field to the node, or the previous node if that is null
|
private 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 |
setValue(java.lang.Object 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 left
leftIsPrevious
.private boolean leftIsPrevious
private TreeList.AVLNode right
rightIsNext
.private boolean rightIsNext
private int height
private int relativePosition
private java.lang.Object value
private AVLNode(int relativePosition, java.lang.Object obj, TreeList.AVLNode rightFollower, TreeList.AVLNode leftFollower)
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 onejava.lang.Object getValue()
void setValue(java.lang.Object obj)
obj
- the value to storeTreeList.AVLNode 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 next()
TreeList.AVLNode previous()
TreeList.AVLNode insert(int index, java.lang.Object 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 insertOnLeft(int indexRelativeToMe, java.lang.Object obj)
private TreeList.AVLNode insertOnRight(int indexRelativeToMe, java.lang.Object obj)
private TreeList.AVLNode getLeftSubTree()
private TreeList.AVLNode getRightSubTree()
private TreeList.AVLNode max()
private TreeList.AVLNode min()
TreeList.AVLNode 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 removeMax()
private TreeList.AVLNode removeMin()
private TreeList.AVLNode removeSelf()
private TreeList.AVLNode balance()
private int getOffset(TreeList.AVLNode node)
private int setOffset(TreeList.AVLNode node, int newOffest)
private void recalcHeight()
private int getHeight(TreeList.AVLNode node)
private int heightRightMinusLeft()
private TreeList.AVLNode rotateLeft()
private TreeList.AVLNode rotateRight()
private void setLeft(TreeList.AVLNode node, TreeList.AVLNode previous)
node
- the new left subtree nodeprevious
- the previous node in the linked listprivate void setRight(TreeList.AVLNode node, TreeList.AVLNode next)
node
- the new left subtree nodenext
- the next node in the linked listpublic java.lang.String toString()
toString
in class java.lang.Object