structs.AvlTree Extends Object
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.

Inheritance

Constructor

goog.structs.AvlTree(opt_comparator)

Parameters

opt_comparator :
(Function | null | undefined)
Function used to order the tree's nodes.

Instance Methods

Public Protected Private
Defined in goog.structs.AvlTree
add(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.
Arguments:
value :
*
Value to insert into the tree.
Returns: 
boolean
  Whether value was inserted into the tree.
code »
balance_(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).
Arguments:
node :
(goog.structs.AvlTree.Node | null)
Node to begin balance from.
code »
clear()
Removes all nodes from the tree.
code »
contains(value) ⇒
boolean
Returns true if the tree contains a node with the specified value, false otherwise.
Arguments:
value :
*
Value to find in the tree.
Returns: 
boolean
  Whether the tree contains a node with the specified value.
code »
getCount() ⇒
number
Returns the number of values stored in the tree.
Returns: 
number
  The number of values stored in the tree.
code »
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.
Returns: 
number
  The height of the tree.
code »
getMaxNode_(opt_rootNode) ⇒
(goog.structs.AvlTree.Node | null)
Returns the node with the largest value in tree, optionally rooted at opt_rootNode.
Arguments:
opt_rootNode :
(goog.structs.AvlTree.Node | null | undefined)
Optional root node.
Returns: 
(goog.structs.AvlTree.Node | null)
  The node with the largest value in the tree.
code »
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.
code »
getMinNode_(opt_rootNode) ⇒
(goog.structs.AvlTree.Node | null)
Returns the node with the smallest value in tree, optionally rooted at opt_rootNode.
Arguments:
opt_rootNode :
(goog.structs.AvlTree.Node | null | undefined)
Optional root node.
Returns: 
(goog.structs.AvlTree.Node | null)
  The node with the smallest value in the tree.
code »
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.
code »
getValues() ⇒
(Array | null)
Inserts the values stored in the tree into a new Array and returns the Array.
Returns: 
(Array | null)
  An array containing all of the trees values in sorted order.
code »
inOrderTraverse(func, opt_startValue)
Performs an in-order traversal of the tree and calls func with each traversed node, optionally starting from the smallest node with a value &amp;gt;= to the specified start value. The traversal ends after traversing the tree&amp;#39;s maximum node or when func returns a value that evaluates to true.
Arguments:
func :
(Function | null)
Function to call on each traversed node.
opt_startValue :
(Object | null | undefined)
If specified, traversal will begin on the node with the smallest value >= opt_startValue.
code »
leftRotate_(node)
Performs a left tree rotation on the specified node.
Arguments:
node :
(goog.structs.AvlTree.Node | null)
Pivot node to rotate from.
code »
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.
Arguments:
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.
code »
removeNode_(node)
Removes the specified node from the tree and ensures the tree still maintains the AVL-tree balance.
Arguments:
node :
(goog.structs.AvlTree.Node | null)
The node to be removed.
code »
reverseOrderTraverse(func, opt_startValue)
Performs a reverse-order traversal of the tree and calls func with each traversed node, optionally starting from the largest node with a value &lt;= to the specified start value. The traversal ends after traversing the tree&#39;s minimum node or when func returns a value that evaluates to true.
Arguments:
func :
(Function | null)
Function to call on each traversed node.
opt_startValue :
(Object | null | undefined)
If specified, traversal will begin on the node with the largest value <= opt_startValue.
code »
rightRotate_(node)
Performs a right tree rotation on the specified node.
Arguments:
node :
(goog.structs.AvlTree.Node | null)
Pivot node to rotate from.
code »
traverse_(traversalFunc, opt_startNode, opt_endNode)
Performs a traversal defined by the supplied traversalFunc. The first call to traversalFunc is passed the root or the optionally specified startNode. After that, calls traversalFunc with the node returned by the previous call to traversalFunc until traversalFunc returns null or the optionally specified endNode. The first call to traversalFunc is passed the root or the optionally specified startNode.
Arguments:
traversalFunc :
(Function | null)
Function used to traverse the tree. Takes a node as a parameter and returns a node.
opt_startNode :
(goog.structs.AvlTree.Node | null | undefined)
The node at which the traversal begins.
opt_endNode :
(goog.structs.AvlTree.Node | null | undefined)
The node at which the traversal ends.
code »

Instance Properties

Defined in goog.structs.AvlTree
comparator_ :
(Function | null)
Comparison function used to compare values in the tree. This function should take two values, a and b, and return x where: 
x < 0 if a < b,
x > 0 if a > b,
x = 0 otherwise
Code »
count_ :
number
Keeps track of the number of nodes in the tree.
Code »
maxNode_ :
(goog.structs.AvlTree.Node | null)
Pointer to the node with the largest value in the tree.
Code »
minNode_ :
(goog.structs.AvlTree.Node | null)
Pointer to the node with the smallest value in the tree.
Code »
root_ :
(goog.structs.AvlTree.Node | null)
Pointer to the root node of the tree.
Code »

Static Methods

goog.structs.AvlTree.DEFAULT_COMPARATOR_(a, 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.
Arguments:
a :
string
The first string.
b :
string
The second string.
Returns: 
number
  -1 if a < b, 1 if a > b, 0 if a = b.
code »

Package structs

Package Reference