Class TreeList.AVLNode<E>

java.lang.Object
org.apache.commons.collections4.list.TreeList.AVLNode<E>
Enclosing class:
TreeList<E>

static class TreeList.AVLNode<E> extends 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 Details

    • left

      private TreeList.AVLNode<E> left
      The left child node or the predecessor if leftIsPrevious.
    • 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 Details

    • 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(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(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 Details

    • 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(Object object, int index)
      Locate the index that contains the specified object.
    • toArray

      void toArray(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

      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.
    • removeMax

      private TreeList.AVLNode<E> removeMax()
    • removeMin

      private TreeList.AVLNode<E> removeMin()
    • 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
    • rotateLeft

      private TreeList.AVLNode<E> rotateLeft()
    • rotateRight

      private TreeList.AVLNode<E> rotateRight()
    • 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 String toString()
      Used for debugging.
      Overrides:
      toString in class Object