Debian Codegraph @

closure-library/closure/goog/structs/avltree.js

raw
1 // Copyright 2007 The Closure Library Authors. All Rights Reserved.
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License");
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 //
7 // http://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS-IS" BASIS,
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
14
15 /**
16 * @fileoverview Datastructure: AvlTree.
17 *
18 *
19 * This file provides the implementation of an AVL-Tree datastructure. The tree
20 * maintains a set of unique values in a sorted order. The values can be
21 * accessed efficiently in their sorted order since the tree enforces an O(logn)
22 * maximum height. See http://en.wikipedia.org/wiki/Avl_tree for more detail.
23 *
24 * The big-O notation for all operations are below:
25 * <pre>
26 * Method big-O
27 * ----------------------------------------------------------------------------
28 * - add O(logn)
29 * - remove O(logn)
30 * - clear O(1)
31 * - contains O(logn)
32 * - indexOf O(logn)
33 * - getCount O(1)
34 * - getMinimum O(1), or O(logn) when optional root is specified
35 * - getMaximum O(1), or O(logn) when optional root is specified
36 * - getHeight O(1)
37 * - getValues O(n)
38 * - inOrderTraverse O(logn + k), where k is number of traversed nodes
39 * - reverseOrderTraverse O(logn + k), where k is number of traversed nodes
40 * </pre>
41 */
42
43
44 goog.provide('goog.structs.AvlTree');
45 goog.provide('goog.structs.AvlTree.Node');
46
47 goog.require('goog.structs.Collection');
48
49
50
51 /**
52 * Constructs an AVL-Tree, which uses the specified comparator to order its
53 * values. The values can be accessed efficiently in their sorted order since
54 * the tree enforces a O(logn) maximum height.
55 *
56 * @param {Function=} opt_comparator Function used to order the tree's nodes.
57 * @constructor
58 * @implements {goog.structs.Collection<T>}
59 * @final
60 * @template T
61 */
62 goog.structs.AvlTree = function(opt_comparator) {
63 this.comparator_ = opt_comparator || goog.structs.AvlTree.DEFAULT_COMPARATOR_;
64 };
65
66
67 /**
68 * String comparison function used to compare values in the tree. This function
69 * is used by default if no comparator is specified in the tree's constructor.
70 *
71 * @param {T} a The first value.
72 * @param {T} b The second value.
73 * @return {number} -1 if a < b, 1 if a > b, 0 if a = b.
74 * @template T
75 * @private
76 */
77 goog.structs.AvlTree.DEFAULT_COMPARATOR_ = function(a, b) {
78 if (String(a) < String(b)) {
79 return -1;
80 } else if (String(a) > String(b)) {
81 return 1;
82 }
83 return 0;
84 };
85
86
87 /**
88 * Pointer to the root node of the tree.
89 *
90 * @private {goog.structs.AvlTree.Node<T>}
91 */
92 goog.structs.AvlTree.prototype.root_ = null;
93
94
95 /**
96 * Comparison function used to compare values in the tree. This function should
97 * take two values, a and b, and return x where:
98 * <pre>
99 * x < 0 if a < b,
100 * x > 0 if a > b,
101 * x = 0 otherwise
102 * </pre>
103 *
104 * @type {Function}
105 * @private
106 */
107 goog.structs.AvlTree.prototype.comparator_ = null;
108
109
110 /**
111 * Pointer to the node with the smallest value in the tree.
112 *
113 * @type {goog.structs.AvlTree.Node<T>}
114 * @private
115 */
116 goog.structs.AvlTree.prototype.minNode_ = null;
117
118
119 /**
120 * Pointer to the node with the largest value in the tree.
121 *
122 * @type {goog.structs.AvlTree.Node<T>}
123 * @private
124 */
125 goog.structs.AvlTree.prototype.maxNode_ = null;
126
127
128 /**
129 * Inserts a node into the tree with the specified value if the tree does
130 * not already contain a node with the specified value. If the value is
131 * inserted, the tree is balanced to enforce the AVL-Tree height property.
132 *
133 * @param {T} value Value to insert into the tree.
134 * @return {boolean} Whether value was inserted into the tree.
135 * @override
136 */
137 goog.structs.AvlTree.prototype.add = function(value) {
138 // If the tree is empty, create a root node with the specified value
139 if (this.root_ == null) {
140 this.root_ = new goog.structs.AvlTree.Node(value);
141 this.minNode_ = this.root_;
142 this.maxNode_ = this.root_;
143 return true;
144 }
145
146 // This will be set to the new node if a new node is added.
147 /** @type {?goog.structs.AvlTree.Node} */
148 var newNode = null;
149
150 // Depth traverse the tree and insert the value if we reach a null node
151 this.traverse_(function(node) {
152 var retNode = null;
153 var comparison = this.comparator_(node.value, value);
154 if (comparison > 0) {
155 retNode = node.left;
156 if (node.left == null) {
157 newNode = new goog.structs.AvlTree.Node(value, node);
158 node.left = newNode;
159 if (node == this.minNode_) {
160 this.minNode_ = newNode;
161 }
162 }
163 } else if (comparison < 0) {
164 retNode = node.right;
165 if (node.right == null) {
166 newNode = new goog.structs.AvlTree.Node(value, node);
167 node.right = newNode;
168 if (node == this.maxNode_) {
169 this.maxNode_ = newNode;
170 }
171 }
172 }
173 return retNode; // If null, we'll stop traversing the tree
174 });
175
176 // If a node was added, increment counts and balance tree.
177 if (newNode) {
178 var nonNullNewNode = /** @type {!goog.structs.AvlTree.Node} */ (newNode);
179 this.traverse_(function(node) {
180 node.count++;
181 return node.parent;
182 }, nonNullNewNode.parent);
183 this.balance_(nonNullNewNode.parent); // Maintain the AVL-tree balance
184 }
185
186 // Return true if a node was added, false otherwise
187 return !!newNode;
188 };
189
190
191 /**
192 * Removes a node from the tree with the specified value if the tree contains a
193 * node with this value. If a node is removed the tree is balanced to enforce
194 * the AVL-Tree height property. The value of the removed node is returned.
195 *
196 * @param {T} value Value to find and remove from the tree.
197 * @return {T} The value of the removed node or null if the value was not in
198 * the tree.
199 * @override
200 */
201 goog.structs.AvlTree.prototype.remove = function(value) {
202 // Assume the value is not removed and set the value when it is removed
203 var retValue = null;
204
205 // Depth traverse the tree and remove the value if we find it
206 this.traverse_(function(node) {
207 var retNode = null;
208 var comparison = this.comparator_(node.value, value);
209 if (comparison > 0) {
210 retNode = node.left;
211 } else if (comparison < 0) {
212 retNode = node.right;
213 } else {
214 retValue = node.value;
215 this.removeNode_(node);
216 }
217 return retNode; // If null, we'll stop traversing the tree
218 });
219
220 // Return the value that was removed, null if the value was not in the tree
221 return retValue;
222 };
223
224
225 /**
226 * Removes all nodes from the tree.
227 */
228 goog.structs.AvlTree.prototype.clear = function() {
229 this.root_ = null;
230 this.minNode_ = null;
231 this.maxNode_ = null;
232 };
233
234
235 /**
236 * Returns true if the tree contains a node with the specified value, false
237 * otherwise.
238 *
239 * @param {T} value Value to find in the tree.
240 * @return {boolean} Whether the tree contains a node with the specified value.
241 * @override
242 */
243 goog.structs.AvlTree.prototype.contains = function(value) {
244 // Assume the value is not in the tree and set this value if it is found
245 var isContained = false;
246
247 // Depth traverse the tree and set isContained if we find the node
248 this.traverse_(function(node) {
249 var retNode = null;
250 var comparison = this.comparator_(node.value, value);
251 if (comparison > 0) {
252 retNode = node.left;
253 } else if (comparison < 0) {
254 retNode = node.right;
255 } else {
256 isContained = true;
257 }
258 return retNode; // If null, we'll stop traversing the tree
259 });
260
261 // Return true if the value is contained in the tree, false otherwise
262 return isContained;
263 };
264
265
266 /**
267 * Returns the index (in an in-order traversal) of the node in the tree with
268 * the specified value. For example, the minimum value in the tree will
269 * return an index of 0 and the maximum will return an index of n - 1 (where
270 * n is the number of nodes in the tree). If the value is not found then -1
271 * is returned.
272 *
273 * @param {T} value Value in the tree whose in-order index is returned.
274 * @return {number} The in-order index of the given value in the
275 * tree or -1 if the value is not found.
276 */
277 goog.structs.AvlTree.prototype.indexOf = function(value) {
278 // Assume the value is not in the tree and set this value if it is found
279 var retIndex = -1;
280 var currIndex = 0;
281
282 // Depth traverse the tree and set retIndex if we find the node
283 this.traverse_(function(node) {
284 var comparison = this.comparator_(node.value, value);
285 if (comparison > 0) {
286 // The value is less than this node, so recurse into the left subtree.
287 return node.left;
288 }
289
290 if (node.left) {
291 // The value is greater than all of the nodes in the left subtree.
292 currIndex += node.left.count;
293 }
294
295 if (comparison < 0) {
296 // The value is also greater than this node.
297 currIndex++;
298 // Recurse into the right subtree.
299 return node.right;
300 }
301 // We found the node, so stop traversing the tree.
302 retIndex = currIndex;
303 return null;
304 });
305
306 // Return index if the value is contained in the tree, -1 otherwise
307 return retIndex;
308 };
309
310
311 /**
312 * Returns the number of values stored in the tree.
313 *
314 * @return {number} The number of values stored in the tree.
315 * @override
316 */
317 goog.structs.AvlTree.prototype.getCount = function() {
318 return this.root_ ? this.root_.count : 0;
319 };
320
321
322 /**
323 * Returns a k-th smallest value, based on the comparator, where 0 <= k <
324 * this.getCount().
325 * @param {number} k The number k.
326 * @return {T} The k-th smallest value.
327 */
328 goog.structs.AvlTree.prototype.getKthValue = function(k) {
329 if (k < 0 || k >= this.getCount()) {
330 return null;
331 }
332 return this.getKthNode_(k).value;
333 };
334
335
336 /**
337 * Returns the value u, such that u is contained in the tree and u < v, for all
338 * values v in the tree where v != u.
339 *
340 * @return {T} The minimum value contained in the tree.
341 */
342 goog.structs.AvlTree.prototype.getMinimum = function() {
343 return this.getMinNode_().value;
344 };
345
346
347 /**
348 * Returns the value u, such that u is contained in the tree and u > v, for all
349 * values v in the tree where v != u.
350 *
351 * @return {T} The maximum value contained in the tree.
352 */
353 goog.structs.AvlTree.prototype.getMaximum = function() {
354 return this.getMaxNode_().value;
355 };
356
357
358 /**
359 * Returns the height of the tree (the maximum depth). This height should
360 * always be <= 1.4405*(Math.log(n+2)/Math.log(2))-1.3277, where n is the
361 * number of nodes in the tree.
362 *
363 * @return {number} The height of the tree.
364 */
365 goog.structs.AvlTree.prototype.getHeight = function() {
366 return this.root_ ? this.root_.height : 0;
367 };
368
369
370 /**
371 * Inserts the values stored in the tree into a new Array and returns the Array.
372 *
373 * @return {!Array<T>} An array containing all of the trees values in sorted
374 * order.
375 */
376 goog.structs.AvlTree.prototype.getValues = function() {
377 var ret = [];
378 this.inOrderTraverse(function(value) { ret.push(value); });
379 return ret;
380 };
381
382
383 /**
384 * Performs an in-order traversal of the tree and calls {@code func} with each
385 * traversed node, optionally starting from the smallest node with a value >= to
386 * the specified start value. The traversal ends after traversing the tree's
387 * maximum node or when {@code func} returns a value that evaluates to true.
388 *
389 * @param {Function} func Function to call on each traversed node.
390 * @param {T=} opt_startValue If specified, traversal will begin on the node
391 * with the smallest value >= opt_startValue.
392 */
393 goog.structs.AvlTree.prototype.inOrderTraverse = function(
394 func, opt_startValue) {
395 // If our tree is empty, return immediately
396 if (!this.root_) {
397 return;
398 }
399
400 // Depth traverse the tree to find node to begin in-order traversal from
401 /** @type {undefined|!goog.structs.AvlTree.Node} */
402 var startNode;
403 if (opt_startValue !== undefined) {
404 this.traverse_(function(node) {
405 var retNode = null;
406 var comparison = this.comparator_(node.value, opt_startValue);
407 if (comparison > 0) {
408 retNode = node.left;
409 startNode = node;
410 } else if (comparison < 0) {
411 retNode = node.right;
412 } else {
413 startNode = node;
414 }
415 return retNode; // If null, we'll stop traversing the tree
416 });
417 if (!startNode) {
418 return;
419 }
420 } else {
421 startNode = /** @type {!goog.structs.AvlTree.Node} */ (this.getMinNode_());
422 }
423
424 // Traverse the tree and call func on each traversed node's value
425 var node = /** @type {!goog.structs.AvlTree.Node} */ (startNode);
426 var prev = node.left ? node.left : node;
427 while (node != null) {
428 if (node.left != null && node.left != prev && node.right != prev) {
429 node = node.left;
430 } else {
431 if (node.right != prev) {
432 if (func(node.value)) {
433 return;
434 }
435 }
436 var temp = node;
437 node =
438 node.right != null && node.right != prev ? node.right : node.parent;
439 prev = temp;
440 }
441 }
442 };
443
444
445 /**
446 * Performs a reverse-order traversal of the tree and calls {@code func} with
447 * each traversed node, optionally starting from the largest node with a value
448 * <= to the specified start value. The traversal ends after traversing the
449 * tree's minimum node or when func returns a value that evaluates to true.
450 *
451 * @param {function(T):?} func Function to call on each traversed node.
452 * @param {T=} opt_startValue If specified, traversal will begin on the node
453 * with the largest value <= opt_startValue.
454 */
455 goog.structs.AvlTree.prototype.reverseOrderTraverse = function(
456 func, opt_startValue) {
457 // If our tree is empty, return immediately
458 if (!this.root_) {
459 return;
460 }
461
462 // Depth traverse the tree to find node to begin reverse-order traversal from
463 var startNode;
464 if (opt_startValue !== undefined) {
465 this.traverse_(goog.bind(function(node) {
466 var retNode = null;
467 var comparison = this.comparator_(node.value, opt_startValue);
468 if (comparison > 0) {
469 retNode = node.left;
470 } else if (comparison < 0) {
471 retNode = node.right;
472 startNode = node;
473 } else {
474 startNode = node;
475 }
476 return retNode; // If null, we'll stop traversing the tree
477 }, this));
478 if (!startNode) {
479 return;
480 }
481 } else {
482 startNode = this.getMaxNode_();
483 }
484
485 // Traverse the tree and call func on each traversed node's value
486 var node = startNode, prev = startNode.right ? startNode.right : startNode;
487 while (node != null) {
488 if (node.right != null && node.right != prev && node.left != prev) {
489 node = node.right;
490 } else {
491 if (node.left != prev) {
492 if (func(node.value)) {
493 return;
494 }
495 }
496 var temp = node;
497 node = node.left != null && node.left != prev ? node.left : node.parent;
498 prev = temp;
499 }
500 }
501 };
502
503
504 /**
505 * Performs a traversal defined by the supplied {@code traversalFunc}. The first
506 * call to {@code traversalFunc} is passed the root or the optionally specified
507 * startNode. After that, calls {@code traversalFunc} with the node returned
508 * by the previous call to {@code traversalFunc} until {@code traversalFunc}
509 * returns null or the optionally specified endNode. The first call to
510 * traversalFunc is passed the root or the optionally specified startNode.
511 *
512 * @param {function(
513 * this:goog.structs.AvlTree<T>,
514 * !goog.structs.AvlTree.Node):?goog.structs.AvlTree.Node} traversalFunc
515 * Function used to traverse the tree.
516 * @param {goog.structs.AvlTree.Node<T>=} opt_startNode The node at which the
517 * traversal begins.
518 * @param {goog.structs.AvlTree.Node<T>=} opt_endNode The node at which the
519 * traversal ends.
520 * @private
521 */
522 goog.structs.AvlTree.prototype.traverse_ = function(
523 traversalFunc, opt_startNode, opt_endNode) {
524 var node = opt_startNode ? opt_startNode : this.root_;
525 var endNode = opt_endNode ? opt_endNode : null;
526 while (node && node != endNode) {
527 node = traversalFunc.call(this, node);
528 }
529 };
530
531
532 /**
533 * Ensures that the specified node and all its ancestors are balanced. If they
534 * are not, performs left and right tree rotations to achieve a balanced
535 * tree. This method assumes that at most 2 rotations are necessary to balance
536 * the tree (which is true for AVL-trees that are balanced after each node is
537 * added or removed).
538 *
539 * @param {goog.structs.AvlTree.Node<T>} node Node to begin balance from.
540 * @private
541 */
542 goog.structs.AvlTree.prototype.balance_ = function(node) {
543
544 this.traverse_(function(node) {
545 // Calculate the left and right node's heights
546 var lh = node.left ? node.left.height : 0;
547 var rh = node.right ? node.right.height : 0;
548
549 // Rotate tree rooted at this node if it is not AVL-tree balanced
550 if (lh - rh > 1) {
551 if (node.left.right &&
552 (!node.left.left || node.left.left.height < node.left.right.height)) {
553 this.leftRotate_(node.left);
554 }
555 this.rightRotate_(node);
556 } else if (rh - lh > 1) {
557 if (node.right.left &&
558 (!node.right.right ||
559 node.right.right.height < node.right.left.height)) {
560 this.rightRotate_(node.right);
561 }
562 this.leftRotate_(node);
563 }
564
565 // Recalculate the left and right node's heights
566 lh = node.left ? node.left.height : 0;
567 rh = node.right ? node.right.height : 0;
568
569 // Set this node's height
570 node.height = Math.max(lh, rh) + 1;
571
572 // Traverse up tree and balance parent
573 return node.parent;
574 }, node);
575
576 };
577
578
579 /**
580 * Performs a left tree rotation on the specified node.
581 *
582 * @param {goog.structs.AvlTree.Node<T>} node Pivot node to rotate from.
583 * @private
584 */
585 goog.structs.AvlTree.prototype.leftRotate_ = function(node) {
586 // Re-assign parent-child references for the parent of the node being removed
587 if (node.isLeftChild()) {
588 node.parent.left = node.right;
589 node.right.parent = node.parent;
590 } else if (node.isRightChild()) {
591 node.parent.right = node.right;
592 node.right.parent = node.parent;
593 } else {
594 this.root_ = node.right;
595 this.root_.parent = null;
596 }
597
598 // Re-assign parent-child references for the child of the node being removed
599 var temp = node.right;
600 node.right = node.right.left;
601 if (node.right != null) node.right.parent = node;
602 temp.left = node;
603 node.parent = temp;
604
605 // Update counts.
606 temp.count = node.count;
607 node.count -= (temp.right ? temp.right.count : 0) + 1;
608 };
609
610
611 /**
612 * Performs a right tree rotation on the specified node.
613 *
614 * @param {goog.structs.AvlTree.Node<T>} node Pivot node to rotate from.
615 * @private
616 */
617 goog.structs.AvlTree.prototype.rightRotate_ = function(node) {
618 // Re-assign parent-child references for the parent of the node being removed
619 if (node.isLeftChild()) {
620 node.parent.left = node.left;
621 node.left.parent = node.parent;
622 } else if (node.isRightChild()) {
623 node.parent.right = node.left;
624 node.left.parent = node.parent;
625 } else {
626 this.root_ = node.left;
627 this.root_.parent = null;
628 }
629
630 // Re-assign parent-child references for the child of the node being removed
631 var temp = node.left;
632 node.left = node.left.right;
633 if (node.left != null) node.left.parent = node;
634 temp.right = node;
635 node.parent = temp;
636
637 // Update counts.
638 temp.count = node.count;
639 node.count -= (temp.left ? temp.left.count : 0) + 1;
640 };
641
642
643 /**
644 * Removes the specified node from the tree and ensures the tree still
645 * maintains the AVL-tree balance.
646 *
647 * @param {goog.structs.AvlTree.Node<T>} node The node to be removed.
648 * @private
649 */
650 goog.structs.AvlTree.prototype.removeNode_ = function(node) {
651 // Perform normal binary tree node removal, but balance the tree, starting
652 // from where we removed the node
653 if (node.left != null || node.right != null) {
654 var b = null; // Node to begin balance from
655 var r; // Node to replace the node being removed
656 if (node.left != null) {
657 r = this.getMaxNode_(node.left);
658
659 // Update counts.
660 this.traverse_(function(node) {
661 node.count--;
662 return node.parent;
663 }, r);
664
665 if (r != node.left) {
666 r.parent.right = r.left;
667 if (r.left) r.left.parent = r.parent;
668 r.left = node.left;
669 r.left.parent = r;
670 b = r.parent;
671 }
672 r.parent = node.parent;
673 r.right = node.right;
674 if (r.right) r.right.parent = r;
675 if (node == this.maxNode_) this.maxNode_ = r;
676 r.count = node.count;
677 } else {
678 r = this.getMinNode_(node.right);
679
680 // Update counts.
681 this.traverse_(function(node) {
682 node.count--;
683 return node.parent;
684 }, r);
685
686 if (r != node.right) {
687 r.parent.left = r.right;
688 if (r.right) r.right.parent = r.parent;
689 r.right = node.right;
690 r.right.parent = r;
691 b = r.parent;
692 }
693 r.parent = node.parent;
694 r.left = node.left;
695 if (r.left) r.left.parent = r;
696 if (node == this.minNode_) this.minNode_ = r;
697 r.count = node.count;
698 }
699
700 // Update the parent of the node being removed to point to its replace
701 if (node.isLeftChild()) {
702 node.parent.left = r;
703 } else if (node.isRightChild()) {
704 node.parent.right = r;
705 } else {
706 this.root_ = r;
707 }
708
709 // Balance the tree
710 this.balance_(b ? b : r);
711 } else {
712 // Update counts.
713 this.traverse_(function(node) {
714 node.count--;
715 return node.parent;
716 }, node.parent);
717
718 // If the node is a leaf, remove it and balance starting from its parent
719 if (node.isLeftChild()) {
720 this.special = 1;
721 node.parent.left = null;
722 if (node == this.minNode_) this.minNode_ = node.parent;
723 this.balance_(node.parent);
724 } else if (node.isRightChild()) {
725 node.parent.right = null;
726 if (node == this.maxNode_) this.maxNode_ = node.parent;
727 this.balance_(node.parent);
728 } else {
729 this.clear();
730 }
731 }
732 };
733
734
735 /**
736 * Returns the node in the tree that has k nodes before it in an in-order
737 * traversal, optionally rooted at {@code opt_rootNode}.
738 *
739 * @param {number} k The number of nodes before the node to be returned in an
740 * in-order traversal, where 0 <= k < root.count.
741 * @param {goog.structs.AvlTree.Node<T>=} opt_rootNode Optional root node.
742 * @return {goog.structs.AvlTree.Node<T>} The node at the specified index.
743 * @private
744 */
745 goog.structs.AvlTree.prototype.getKthNode_ = function(k, opt_rootNode) {
746 var root = opt_rootNode || this.root_;
747 var numNodesInLeftSubtree = root.left ? root.left.count : 0;
748
749 if (k < numNodesInLeftSubtree) {
750 return this.getKthNode_(k, root.left);
751 } else if (k == numNodesInLeftSubtree) {
752 return root;
753 } else {
754 return this.getKthNode_(k - numNodesInLeftSubtree - 1, root.right);
755 }
756 };
757
758
759 /**
760 * Returns the node with the smallest value in tree, optionally rooted at
761 * {@code opt_rootNode}.
762 *
763 * @param {goog.structs.AvlTree.Node<T>=} opt_rootNode Optional root node.
764 * @return {goog.structs.AvlTree.Node<T>} The node with the smallest value in
765 * the tree.
766 * @private
767 */
768 goog.structs.AvlTree.prototype.getMinNode_ = function(opt_rootNode) {
769 if (!opt_rootNode) {
770 return this.minNode_;
771 }
772
773 var minNode = opt_rootNode;
774 this.traverse_(function(node) {
775 var retNode = null;
776 if (node.left) {
777 minNode = node.left;
778 retNode = node.left;
779 }
780 return retNode; // If null, we'll stop traversing the tree
781 }, opt_rootNode);
782
783 return minNode;
784 };
785
786
787 /**
788 * Returns the node with the largest value in tree, optionally rooted at
789 * opt_rootNode.
790 *
791 * @param {goog.structs.AvlTree.Node<T>=} opt_rootNode Optional root node.
792 * @return {goog.structs.AvlTree.Node<T>} The node with the largest value in
793 * the tree.
794 * @private
795 */
796 goog.structs.AvlTree.prototype.getMaxNode_ = function(opt_rootNode) {
797 if (!opt_rootNode) {
798 return this.maxNode_;
799 }
800
801 var maxNode = opt_rootNode;
802 this.traverse_(function(node) {
803 var retNode = null;
804 if (node.right) {
805 maxNode = node.right;
806 retNode = node.right;
807 }
808 return retNode; // If null, we'll stop traversing the tree
809 }, opt_rootNode);
810
811 return maxNode;
812 };
813
814
815
816 /**
817 * Constructs an AVL-Tree node with the specified value. If no parent is
818 * specified, the node's parent is assumed to be null. The node's height
819 * defaults to 1 and its children default to null.
820 *
821 * @param {T} value Value to store in the node.
822 * @param {goog.structs.AvlTree.Node<T>=} opt_parent Optional parent node.
823 * @constructor
824 * @final
825 * @template T
826 */
827 goog.structs.AvlTree.Node = function(value, opt_parent) {
828 /**
829 * The value stored by the node.
830 *
831 * @type {T}
832 */
833 this.value = value;
834
835 /**
836 * The node's parent. Null if the node is the root.
837 *
838 * @type {goog.structs.AvlTree.Node<T>}
839 */
840 this.parent = opt_parent ? opt_parent : null;
841
842 /**
843 * The number of nodes in the subtree rooted at this node.
844 *
845 * @type {number}
846 */
847 this.count = 1;
848 };
849
850
851 /**
852 * The node's left child. Null if the node does not have a left child.
853 *
854 * @type {?goog.structs.AvlTree.Node<T>}
855 */
856 goog.structs.AvlTree.Node.prototype.left = null;
857
858
859 /**
860 * The node's right child. Null if the node does not have a right child.
861 *
862 * @type {?goog.structs.AvlTree.Node<T>}
863 */
864 goog.structs.AvlTree.Node.prototype.right = null;
865
866
867 /**
868 * The height of the tree rooted at this node.
869 *
870 * @type {number}
871 */
872 goog.structs.AvlTree.Node.prototype.height = 1;
873
874
875 /**
876 * Returns true iff the specified node has a parent and is the right child of
877 * its parent.
878 *
879 * @return {boolean} Whether the specified node has a parent and is the right
880 * child of its parent.
881 */
882 goog.structs.AvlTree.Node.prototype.isRightChild = function() {
883 return !!this.parent && this.parent.right == this;
884 };
885
886
887 /**
888 * Returns true iff the specified node has a parent and is the left child of
889 * its parent.
890 *
891 * @return {boolean} Whether the specified node has a parent and is the left
892 * child of its parent.
893 */
894 goog.structs.AvlTree.Node.prototype.isLeftChild = function() {
895 return !!this.parent && this.parent.left == this;
896 };