Package com.google.gson.internal
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 java.lang.Object
Builds AVL trees of a predetermined size by accepting nodes of increasing value. To use:- Call
reset(int)
to initialize the target size size. - Call
add(com.google.gson.internal.LinkedHashTreeMap.Node<K, V>)
size times with increasing values. - 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 Summary
Fields Modifier and Type Field Description private int
leavesSkipped
private int
leavesToSkip
private int
size
private LinkedHashTreeMap.Node<K,V>
stack
This stack is a singly linked list, linked by the 'parent' field.
-
Constructor Summary
Constructors Constructor Description AvlBuilder()
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description (package private) void
add(LinkedHashTreeMap.Node<K,V> node)
(package private) void
reset(int targetSize)
(package private) LinkedHashTreeMap.Node<K,V>
root()
-
-
-
Field Detail
-
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
-
-
Method Detail
-
reset
void reset(int targetSize)
-
add
void add(LinkedHashTreeMap.Node<K,V> node)
-
root
LinkedHashTreeMap.Node<K,V> root()
-
-