Class LinkedHashTreeMap.AvlBuilder<K,​V>

  • Enclosing class:
    LinkedHashTreeMap<K,​V>

    static final class LinkedHashTreeMap.AvlBuilder<K,​V>
    extends java.lang.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 Detail

      • leavesToSkip

        private int leavesToSkip
      • leavesSkipped

        private int leavesSkipped
      • size

        private int size
    • Constructor Detail

      • AvlBuilder

        AvlBuilder()