Class TreeList.AVLNode

  • Enclosing class:
    TreeList

    static class TreeList.AVLNode
    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 java.lang.Object value
        The stored element.
    • Constructor Detail

      • AVLNode

        private AVLNode​(int relativePosition,
                        java.lang.Object obj,
                        TreeList.AVLNode rightFollower,
                        TreeList.AVLNode leftFollower)
        Constructs a new node with a relative position.
        Parameters:
        relativePosition - the relative position of the node
        obj - the value for the ndoe
        rightFollower - the node with the value following this one
        leftFollower - the node with the value leading this one
    • Method Detail

      • getValue

        java.lang.Object getValue()
        Gets the value.
        Returns:
        the value of this node
      • setValue

        void setValue​(java.lang.Object obj)
        Sets the value.
        Parameters:
        obj - the value to store
      • get

        TreeList.AVLNode 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 next()
        Gets the next node in the list after this one.
        Returns:
        the next node
      • previous

        TreeList.AVLNode previous()
        Gets the node in the list before this one.
        Returns:
        the previous node
      • insert

        TreeList.AVLNode insert​(int index,
                                java.lang.Object 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 insertOnLeft​(int indexRelativeToMe,
                                              java.lang.Object obj)
      • insertOnRight

        private TreeList.AVLNode insertOnRight​(int indexRelativeToMe,
                                               java.lang.Object obj)
      • getLeftSubTree

        private TreeList.AVLNode getLeftSubTree()
        Gets the left node, returning null if its a faedelung.
      • getRightSubTree

        private TreeList.AVLNode getRightSubTree()
        Gets the right node, returning null if its a faedelung.
      • max

        private TreeList.AVLNode max()
        Gets the rightmost child of this node.
        Returns:
        the rightmost child (greatest index)
      • min

        private TreeList.AVLNode min()
        Gets the leftmost child of this node.
        Returns:
        the leftmost child (smallest index)
      • remove

        TreeList.AVLNode 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 removeSelf()
        Removes this node from the tree.
        Returns:
        the node that replaces this one in the parent
      • balance

        private TreeList.AVLNode balance()
        Balances according to the AVL algorithm.
      • getOffset

        private int getOffset​(TreeList.AVLNode node)
        Gets the relative position.
      • setOffset

        private int setOffset​(TreeList.AVLNode node,
                              int newOffest)
        Sets the relative position.
      • recalcHeight

        private void recalcHeight()
        Sets the height by calculation.
      • getHeight

        private int getHeight​(TreeList.AVLNode 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 node,
                             TreeList.AVLNode 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 node,
                              TreeList.AVLNode 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
      • toString

        public java.lang.String toString()
        Used for debugging.
        Overrides:
        toString in class java.lang.Object