Class LinkedHashTreeMap.AvlBuilder<K,V>

java.lang.Object
com.google.gson.internal.LinkedHashTreeMap.AvlBuilder<K,V>
Enclosing class:
LinkedHashTreeMap<K,V>

static final class LinkedHashTreeMap.AvlBuilder<K,V> extends Object
Builds AVL trees of a predetermined size by accepting nodes of increasing value. To use:
  1. Call reset(int) to initialize the target size size.
  2. Call add(com.google.gson.internal.LinkedHashTreeMap.Node<K, V>) size times with increasing values.
  3. Call root() to get the root of the balanced tree.

The returned tree will satisfy the AVL constraint: for every node N, the height of N.left and N.right is different by at most 1. It accomplishes this by omitting deepest-level leaf nodes when building trees whose size isn't a power of 2 minus 1.

Unlike rebuilding a tree from scratch, this approach requires no value comparisons. Using this class to create a tree of size S is O(S).

  • Field Details

    • stack

      private LinkedHashTreeMap.Node<K,V> stack
      This stack is a singly linked list, linked by the 'parent' field.
    • leavesToSkip

      private int leavesToSkip
    • leavesSkipped

      private int leavesSkipped
    • size

      private int size
  • Constructor Details

    • AvlBuilder

      AvlBuilder()
  • Method Details