The `goog.structs.AvlTree` Class

`goog.structs.AvlTree(opt_comparator)`

Constructs an AVL-Tree, which uses the specified comparator to order its values. The values can be accessed efficiently in their sorted order since the tree enforces a O(logn) maximum height.

opt_comparator {Function=}: Function used to order the tree's nodes.

The `goog.structs.AvlTree.Node` Class

Constructs an AVL-Tree node with the specified value. If no parent is specified, the node's parent is assumed to be null. The node's height defaults to 1 and its children default to null. … more

`.add(value)`

Inserts a node into the tree with the specified value if the tree does not already contain a node with the specified value. If the value is inserted, the tree is balanced to enforce the AVL-Tree height property.

value {*}: Value to insert into the tree.
returns {boolean}: Whether value was inserted into the tree.

`.clear()`

Removes all nodes from the tree.

`.contains(value)`

Returns true if the tree contains a node with the specified value, false otherwise.

value {*}: Value to find in the tree.
returns {boolean}: Whether the tree contains a node with the specified value.

`.getCount()`

Returns the number of values stored in the tree.

returns {number}: The number of values stored in the tree.

`.getHeight()`

Returns the height of the tree (the maximum depth). This height should always be <= 1.4405*(Math.log(n+2)/Math.log(2))-1.3277, where n is the number of nodes in the tree.

returns {number}: The height of the tree.

`.getMaximum()`

Returns the value u, such that u is contained in the tree and u > v, for all values v in the tree where v != u.

returns {*}: The maximum value contained in the tree.

`.getMinimum()`

Returns the value u, such that u is contained in the tree and u < v, for all values v in the tree where v != u.

returns {*}: The minimum value contained in the tree.

`.getValues()`

Inserts the values stored in the tree into a new Array and returns the Array.

returns {Array}: An array containing all of the trees values in sorted order.

`.inOrderTraverse(func, opt_startValue)`

Performs an in-order traversal of the tree and calls {@code func} with each traversed node, optionally starting from the smallest node with a value >= to the specified start value. The traversal ends after traversing the tree's maximum node or when {@code func} returns a value that evaluates to true.

func {Function}: Function to call on each traversed node.
opt_startValue {Object=}: If specified, traversal will begin on the node with the smallest value >= opt_startValue.

`.remove(value)`

Removes a node from the tree with the specified value if the tree contains a node with this value. If a node is removed the tree is balanced to enforce the AVL-Tree height property. The value of the removed node is returned.

value {*}: Value to find and remove from the tree.
returns {*}: The value of the removed node or null if the value was not in the tree.

`.reverseOrderTraverse(func, opt_startValue)`

Performs a reverse-order traversal of the tree and calls {@code func} with each traversed node, optionally starting from the largest node with a value <= to the specified start value. The traversal ends after traversing the tree's minimum node or when func returns a value that evaluates to true.

func {Function}: Function to call on each traversed node.
opt_startValue {Object=}: If specified, traversal will begin on the node with the largest value <= opt_startValue.

The goog.structs.AvlTree Class

goog.structs.AvlTree(opt_comparator)

The goog.structs.AvlTree.Node Class

.add(value)

.clear()

.contains(value)

.getCount()

.getHeight()

.getMaximum()

.getMinimum()

.getValues()

.inOrderTraverse(func, opt_startValue)

.remove(value)

.reverseOrderTraverse(func, opt_startValue)