Class goog.structs.AvlTree

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.

Instance Method Summary
	`add(<Any Type> value) ⇒ boolean` 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.
	`balance_(?goog.structs.AvlTree.Node node)` Ensures that the specified node and all its ancestors are balanced. If they are not, performs left and right tree rotations to achieve a balanced tree. This method assumes that at most 2 rotations are necessary to balance the tree (which is true for AVL-trees that are balanced after each node is added or removed).
	`clear()` Removes all nodes from the tree.
	`contains(<Any Type> value) ⇒ boolean` Returns true if the tree contains a node with the specified value, false otherwise.
	`getCount() ⇒ number` Returns the number of values stored in the tree.
	`getHeight() ⇒ number` 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.
	`getMaxNode_(?goog.structs.AvlTree.Node= opt_rootNode) ⇒ ?goog.structs.AvlTree.Node` Returns the node with the largest value in tree, optionally rooted at opt_rootNode.
	`getMaximum() ⇒ <Any Type>` 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.
	`getMinNode_(?goog.structs.AvlTree.Node= opt_rootNode) ⇒ ?goog.structs.AvlTree.Node` Returns the node with the smallest value in tree, optionally rooted at {@code opt_rootNode}.
	`getMinimum() ⇒ <Any Type>` 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.
	`getValues() ⇒ ?Array` Inserts the values stored in the tree into a new Array and returns the Array.
	`inOrderTraverse(?Function func, ?Object= 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.
	`leftRotate_(?goog.structs.AvlTree.Node node)` Performs a left tree rotation on the specified node.
	`remove(<Any Type> value) ⇒ <Any Type>` 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.
	`removeNode_(?goog.structs.AvlTree.Node node)` Removes the specified node from the tree and ensures the tree still maintains the AVL-tree balance.
	`reverseOrderTraverse(?Function func, ?Object= 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.
	`rightRotate_(?goog.structs.AvlTree.Node node)` Performs a right tree rotation on the specified node.
	`traverse_(?Function traversalFunc, ?goog.structs.AvlTree.Node= opt_startNode, ?goog.structs.AvlTree.Node= opt_endNode)` Performs a traversal defined by the supplied {@code traversalFunc}. The first call to {@code traversalFunc} is passed the root or the optionally specified startNode. After that, calls {@code traversalFunc} with the node returned by the previous call to {@code traversalFunc} until {@code traversalFunc} returns null or the optionally specified endNode. The first call to traversalFunc is passed the root or the optionally specified startNode.

Static Method Summary
	`DEFAULT_COMPARATOR_(string a, string b) ⇒ number` String comparison function used to compare values in the tree. This function is used by default if no comparator is specified in the tree's constructor.