static final class LinkedHashTreeMap.AvlBuilder<K,V>
extends java.lang.Object
reset(int)
to initialize the target size size.
add(com.google.gson.internal.LinkedHashTreeMap.Node<K, V>)
size times with increasing values.
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)
.
Modifier and Type | Field and 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 and Description |
---|
AvlBuilder() |
Modifier and Type | Method and Description |
---|---|
(package private) void |
add(LinkedHashTreeMap.Node<K,V> node) |
(package private) void |
reset(int targetSize) |
(package private) LinkedHashTreeMap.Node<K,V> |
root() |
private LinkedHashTreeMap.Node<K,V> stack
private int leavesToSkip
private int leavesSkipped
private int size
void reset(int targetSize)
void add(LinkedHashTreeMap.Node<K,V> node)
LinkedHashTreeMap.Node<K,V> root()