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>
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
FieldsModifier and TypeFieldDescriptionprivate int
private int
private int
private LinkedHashTreeMap.Node<K,
V> This stack is a singly linked list, linked by the 'parent' field. -
Constructor Summary
Constructors -
Method Summary
Modifier and TypeMethodDescription(package private) void
add
(LinkedHashTreeMap.Node<K, V> node) (package private) void
reset
(int targetSize) (package private) LinkedHashTreeMap.Node<K,
V> root()
-
Field Details
-
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
-
reset
void reset(int targetSize) -
add
-
root
LinkedHashTreeMap.Node<K,V> root()
-