Class TreeList.AVLNode<E>

  • Enclosing class:
    TreeList<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 Detail

      • leftIsPrevious

        private boolean leftIsPrevious
        Flag indicating that left reference is not a subtree but the predecessor.
      • 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 node
        obj - the value for the node
        rightFollower - the node with the value following this one
        leftFollower - 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 elements start through end of the collection, assuming the iterator e already points at element start.

        Parameters:
        iterator - an iterator over the collection, which should already point to the element at index start within the collection
        start - the index of the first element in the collection that should be in this subtree
        end - the index of the last element in the collection that should be in this subtree
        absolutePositionOfParent - absolute position of this node's parent, or 0 if this node is the root
        prev - the AVLNode corresponding to element (start - 1) of the collection, or null if start is 0
        next - the AVLNode 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 filled
        index - 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.
      • 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
      • 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 node
        previous - 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 node
        next - 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 one
        currentSize - 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 class java.lang.Object