Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit133953a

Browse files
committed
Update docs
1 parentbf8b433 commit133953a

File tree

122 files changed

+1084
-283
lines changed

Some content is hidden

Large Commits have some content hidden by default. Use the searchbox below for content that may be hidden.

122 files changed

+1084
-283
lines changed

‎combinatorics_cartesianproduct.js.html

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -91,7 +91,7 @@ <h2><a href="index.html">Home</a></h2><h3>Modules</h3><ul><li><a href="module-co
9191
<brclass="clear">
9292

9393
<footer>
94-
Documentation generated by<ahref="https://github.com/jsdoc3/jsdoc">JSDoc 3.3.0-alpha13</a> onFri Feb 27 201509:39:04 GMT-0800 (PST)
94+
Documentation generated by<ahref="https://github.com/jsdoc3/jsdoc">JSDoc 3.3.0-alpha13</a> onTue Mar 10 201511:52:43 GMT-0700 (PDT)
9595
</footer>
9696

9797
<script>prettyPrint();</script>

‎combinatorics_combinations.js.html

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -96,7 +96,7 @@ <h2><a href="index.html">Home</a></h2><h3>Modules</h3><ul><li><a href="module-co
9696
<brclass="clear">
9797

9898
<footer>
99-
Documentation generated by<ahref="https://github.com/jsdoc3/jsdoc">JSDoc 3.3.0-alpha13</a> onFri Feb 27 201509:39:04 GMT-0800 (PST)
99+
Documentation generated by<ahref="https://github.com/jsdoc3/jsdoc">JSDoc 3.3.0-alpha13</a> onTue Mar 10 201511:52:43 GMT-0700 (PDT)
100100
</footer>
101101

102102
<script>prettyPrint();</script>

‎combinatorics_permutations.js.html

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -105,7 +105,7 @@ <h2><a href="index.html">Home</a></h2><h3>Modules</h3><ul><li><a href="module-co
105105
<brclass="clear">
106106

107107
<footer>
108-
Documentation generated by<ahref="https://github.com/jsdoc3/jsdoc">JSDoc 3.3.0-alpha13</a> onFri Feb 27 201509:39:04 GMT-0800 (PST)
108+
Documentation generated by<ahref="https://github.com/jsdoc3/jsdoc">JSDoc 3.3.0-alpha13</a> onTue Mar 10 201511:52:43 GMT-0700 (PDT)
109109
</footer>
110110

111111
<script>prettyPrint();</script>

‎combinatorics_variations-repetition.js.html

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -97,7 +97,7 @@ <h2><a href="index.html">Home</a></h2><h3>Modules</h3><ul><li><a href="module-co
9797
<brclass="clear">
9898

9999
<footer>
100-
Documentation generated by<ahref="https://github.com/jsdoc3/jsdoc">JSDoc 3.3.0-alpha13</a> onFri Feb 27 201509:39:04 GMT-0800 (PST)
100+
Documentation generated by<ahref="https://github.com/jsdoc3/jsdoc">JSDoc 3.3.0-alpha13</a> onTue Mar 10 201511:52:43 GMT-0700 (PDT)
101101
</footer>
102102

103103
<script>prettyPrint();</script>

‎data-structures_avl-tree.js.html

Lines changed: 123 additions & 34 deletions
Original file line numberDiff line numberDiff line change
@@ -121,6 +121,94 @@ <h1 class="page-title">Source: data-structures/avl-tree.js</h1>
121121
return true;
122122
};
123123

124+
/**
125+
* Gets the nodes to be restructured during an AVL restructure
126+
* after a remove/delete takes place.
127+
*
128+
* @public
129+
* @method
130+
* @param {Array} traveledNodes Array of previously traveled nodes
131+
* that are used to help determine the nodes to be restructured.
132+
*/
133+
exports.AVLTree.prototype._getNodesToRestructureRemove =
134+
function (traveledNodes) {
135+
// z is last traveled node - imbalance found at z
136+
var zIndex = traveledNodes.length;
137+
zIndex -= 1;
138+
var z = traveledNodes[zIndex];
139+
// y should be child of z with larger height
140+
// (cannot be ancestor of removed node)
141+
var y;
142+
if (z._left !== null &amp;&amp; z._right !== null){
143+
y = (z._left === y) ? z._right : z._left;
144+
}else if (z._left !== null &amp;&amp; z._right === null){
145+
y = z._left;
146+
}else if (z._right !== null &amp;&amp; z._left === null){
147+
y = z._right;
148+
}
149+
// x should be tallest child of y.
150+
// If children same height, x should be child of y
151+
// that has same orientation as z to y.
152+
var x;
153+
if (y._left !== null &amp;&amp; y._right !== null){
154+
if (y._left._height> y._right._height){
155+
x = y._left;
156+
}else if (y._left._height &lt; y._right._height){
157+
x = y._right;
158+
}else if (y._left._height === y._right._height){
159+
x = (z._left === y) ? y._left : y._right;
160+
}
161+
}else if (y._left !== null &amp;&amp; y._right === null){
162+
x = y._left;
163+
}else if (y._right !== null &amp;&amp; y._left === null){
164+
x = y._right;
165+
}
166+
return [x, y, z];
167+
};
168+
169+
/**
170+
* Gets the nodes to be restructured during an AVL restructure
171+
* after an insert takes place.
172+
*
173+
* @public
174+
* @method
175+
* @param {Array} traveledNodes Array of previously traveled nodes
176+
* that are used to help determine the nodes to be restructured.
177+
*/
178+
exports.AVLTree.prototype._getNodesToRestructureInsert =
179+
function (traveledNodes) {
180+
// z is last traveled node - imbalance found at z
181+
var zIndex = traveledNodes.length;
182+
zIndex -= 1;
183+
var z = traveledNodes[zIndex];
184+
// y should be child of z with larger height
185+
// (must be ancestor of inserted node)
186+
// therefore, last traveled node is correct.
187+
var yIndex = traveledNodes.length;
188+
yIndex -= 2;
189+
var y = traveledNodes[yIndex];
190+
// x should be tallest child of y.
191+
// If children same height, x should be ancestor
192+
// of inserted node (in traveled path).
193+
var x;
194+
if (y._left !== null &amp;&amp; y._right !== null){
195+
if (y._left._height> y._right._height){
196+
x = y._left;
197+
}else if (y._left._height &lt; y._right._height){
198+
x = y._right;
199+
}else if (y._left._height === y._right._height){
200+
var xIndex = traveledNodes.length;
201+
xIndex -= 3;
202+
x = traveledNodes[xIndex];
203+
}
204+
}else if (y._left !== null &amp;&amp; y._right === null){
205+
x = y._left;
206+
}else if (y._right !== null &amp;&amp; y._left === null){
207+
x = y._right;
208+
}
209+
return [x, y, z];
210+
};
211+
124212
/**
125213
* Maintains the height balance property by
126214
* walking to root and checking for invalid height
@@ -130,21 +218,20 @@ <h1 class="page-title">Source: data-structures/avl-tree.js</h1>
130218
* @public
131219
* @method
132220
* @param {Node} node Started node.
221+
* @param {Boolean} isRemove Represents if method was called after remove.
133222
*/
134-
exports.AVLTree.prototype._maintainHeightBalanceProperty = function (node) {
223+
exports.AVLTree.prototype._maintainHeightBalanceProperty =
224+
function (node, isRemove) {
135225
var current = node;
136-
varpath = []; //During restructure, use last 3 nodes traveled.
226+
vartraveledNodes = [];
137227
while (current !== null){
138-
path.push(current);
228+
traveledNodes.push(current);
139229
current._height = this._getHeightAtNode(current);
140230
if (!this._isBalancedAtNode(current)){
141-
if (path.length>= 3){
142-
var nodesToRestructure = path.slice(0, 3);
143-
var x = nodesToRestructure[0];
144-
var y = nodesToRestructure[1];
145-
var z = nodesToRestructure[2];
146-
this._restructure(x, y, z);
147-
}
231+
var nodesToBeRestructured = (isRemove)
232+
? this._getNodesToRestructureRemove(traveledNodes)
233+
: this._getNodesToRestructureInsert(traveledNodes);
234+
this._restructure(nodesToBeRestructured);
148235
}
149236
current = current._parent;
150237
}
@@ -156,11 +243,13 @@ <h1 class="page-title">Source: data-structures/avl-tree.js</h1>
156243
*
157244
* @public
158245
* @method
159-
* @param {Node} x node with lowest height to be restructured.
160-
* @param {Node} y parent of x parameter.
161-
* @param {Node} z grandparent of x, largest height.
246+
* @param {Array} nodesToBeRestructured
247+
* array of nodes, in format, [x, y, z], to be restructured
162248
*/
163-
exports.AVLTree.prototype._restructure = function (x, y, z) {
249+
exports.AVLTree.prototype._restructure = function (nodesToBeRestructured) {
250+
var x = nodesToBeRestructured[0];
251+
var y = nodesToBeRestructured[1];
252+
var z = nodesToBeRestructured[2];
164253
//Determine Rotation Pattern
165254
if (z._right === y &amp;&amp; y._right === x){
166255
this._rightRight(x, y, z);
@@ -365,7 +454,7 @@ <h1 class="page-title">Source: data-structures/avl-tree.js</h1>
365454
}
366455
if (!current[insertKey]) {
367456
current[insertKey] = new exports.Node(value, null, null, current);
368-
this._maintainHeightBalanceProperty(current[insertKey]);
457+
this._maintainHeightBalanceProperty(current[insertKey], false);
369458
} else {
370459
this.insert(value, current[insertKey]);
371460
}
@@ -509,9 +598,11 @@ <h1 class="page-title">Source: data-structures/avl-tree.js</h1>
509598
*/
510599
exports.AVLTree.prototype._replaceChild =
511600
function (parent, oldChild, newChild) {
512-
if (!parent) {
601+
if (parent === null) {
513602
this._root = newChild;
514-
this._root._parent = null;
603+
if (this._root !== null){
604+
this._root._parent = null;
605+
}
515606
} else {
516607
if (parent._left === oldChild) {
517608
parent._left = newChild;
@@ -529,33 +620,31 @@ <h1 class="page-title">Source: data-structures/avl-tree.js</h1>
529620
* Average runtime complexity: O(log N).
530621
*
531622
* @public
532-
* @param {Node} node to be removed
623+
* @param {Number|String} value of node to be removed
533624
* @returns {Boolean} True/false depending
534625
* on whether the given node is removed.
535626
*/
536-
exports.AVLTree.prototype.remove = function (node) {
627+
exports.AVLTree.prototype.remove = function (value) {
628+
var node = this.find(value);
537629
if (!node) {
538630
return false;
539631
}
540-
541632
if (node._left &amp;&amp; node._right) {
542633
var min = this._findMin(node._right);
543634
var temp = node.value;
544-
545635
node.value = min.value;
546636
min.value = temp;
547637
return this.remove(min);
548638
} else {
549-
if (node._parent !== null) {
550-
if (node._left) {
551-
this._replaceChild(node._parent, node, node._left);
552-
} else if (node._right) {
553-
this._replaceChild(node._parent, node, node._right);
554-
} else {
555-
this._replaceChild(node._parent, node, null);
556-
}
557-
}else {
558-
this._root = null;
639+
if (node._left) {
640+
this._replaceChild(node._parent, node, node._left);
641+
this._maintainHeightBalanceProperty(node._left, true);
642+
} else if (node._right) {
643+
this._replaceChild(node._parent, node, node._right);
644+
this._maintainHeightBalanceProperty(node._right, true);
645+
} else {
646+
this._replaceChild(node._parent, node, null);
647+
this._maintainHeightBalanceProperty(node._parent, true);
559648
}
560649
return true;
561650
}
@@ -684,12 +773,12 @@ <h1 class="page-title">Source: data-structures/avl-tree.js</h1>
684773
* @returns {Node} The lowest common ancestor of the two nodes or null.
685774
*/
686775
exports.AVLTree.prototype.lowestCommonAncestor =
687-
function (firstNode, secondNode) {
776+
function (firstNode, secondNode) {
688777
return this._lowestCommonAncestor(firstNode, secondNode, this._root);
689778
};
690779

691780
exports.AVLTree.prototype._lowestCommonAncestor =
692-
function (firstNode, secondNode, current) {
781+
function (firstNode, secondNode, current) {
693782
var firstNodeInLeft = this._existsInSubtree(firstNode, current._left);
694783
var secondNodeInLeft = this._existsInSubtree(secondNode, current._left);
695784
var firstNodeInRight = this._existsInSubtree(firstNode, current._right);
@@ -735,7 +824,7 @@ <h2><a href="index.html">Home</a></h2><h3>Modules</h3><ul><li><a href="module-co
735824
<brclass="clear">
736825

737826
<footer>
738-
Documentation generated by<ahref="https://github.com/jsdoc3/jsdoc">JSDoc 3.3.0-alpha13</a> onFri Feb 27 201509:39:04 GMT-0800 (PST)
827+
Documentation generated by<ahref="https://github.com/jsdoc3/jsdoc">JSDoc 3.3.0-alpha13</a> onTue Mar 10 201511:52:43 GMT-0700 (PDT)
739828
</footer>
740829

741830
<script>prettyPrint();</script>

‎data-structures_binary-search-tree.js.html

Lines changed: 47 additions & 14 deletions
Original file line numberDiff line numberDiff line change
@@ -253,7 +253,9 @@ <h1 class="page-title">Source: data-structures/binary-search-tree.js</h1>
253253
function (parent, oldChild, newChild) {
254254
if (!parent) {
255255
this._root = newChild;
256-
this._root._parent = null;
256+
if (this._root !== null){
257+
this._root._parent = null;
258+
}
257259
} else {
258260
if (parent._left === oldChild) {
259261
parent._left = newChild;
@@ -279,25 +281,19 @@ <h1 class="page-title">Source: data-structures/binary-search-tree.js</h1>
279281
if (!node) {
280282
return false;
281283
}
282-
283284
if (node._left &amp;&amp; node._right) {
284285
var min = this._findMin(node._right);
285286
var temp = node.value;
286-
287287
node.value = min.value;
288288
min.value = temp;
289289
return this.remove(min);
290290
} else {
291-
if (node._parent !== null) {
292-
if (node._left) {
293-
this._replaceChild(node._parent, node, node._left);
294-
} else if (node._right) {
295-
this._replaceChild(node._parent, node, node._right);
296-
} else {
297-
this._replaceChild(node._parent, node, null);
298-
}
299-
}else {
300-
this._root = null;
291+
if (node._left) {
292+
this._replaceChild(node._parent, node, node._left);
293+
} else if (node._right) {
294+
this._replaceChild(node._parent, node, node._right);
295+
} else {
296+
this._replaceChild(node._parent, node, null);
301297
}
302298
return true;
303299
}
@@ -362,6 +358,13 @@ <h1 class="page-title">Source: data-structures/binary-search-tree.js</h1>
362358
return this._findMax(this._root);
363359
};
364360

361+
/**
362+
* Checks if a given node is balanced.
363+
*
364+
* @private
365+
* @param {Node} current Node to have balance checked.
366+
* @returns {Boolean} Boolean of whether or not provided node is balanced.
367+
*/
365368
exports.BinaryTree.prototype._isBalanced = function (current) {
366369
if (!current) {
367370
return true;
@@ -411,6 +414,13 @@ <h1 class="page-title">Source: data-structures/binary-search-tree.js</h1>
411414
return this._getHeight(this._root);
412415
};
413416

417+
/**
418+
* Recursive worker function for getHeight()
419+
*
420+
* @private
421+
* @param {Node} node Node at current recursive frame.
422+
* @returns {Number} Height of the Node in the parameter.
423+
*/
414424
exports.BinaryTree.prototype._getHeight = function (node) {
415425
if (!node) {
416426
return 0;
@@ -423,13 +433,28 @@ <h1 class="page-title">Source: data-structures/binary-search-tree.js</h1>
423433
* Finds the lowest common ancestor of two nodes.
424434
*
425435
* @public
436+
* @param {Node} firstNode First node to be considered when checking
437+
* for ancestor.
438+
* @param {Node} secondNode Second node to be considered when checking
439+
* for ancestor.
426440
* @returns {Node} The lowest common ancestor of the two nodes or null.
427441
*/
428442
exports.BinaryTree.prototype.lowestCommonAncestor =
429443
function (firstNode, secondNode) {
430444
return this._lowestCommonAncestor(firstNode, secondNode, this._root);
431445
};
432446

447+
/**
448+
* Obtains the lowest common ancestor for the given nodes.
449+
*
450+
* @private
451+
* @param {Node} firstNode First node to be considered when checking
452+
* for ancestor.
453+
* @param {Node} secondNode Second node to be considered when checking
454+
* for ancestor.
455+
* @param {Node} current Current node.
456+
* @returns {Node} The lowest common ancestor of the two nodes or null.
457+
*/
433458
exports.BinaryTree.prototype._lowestCommonAncestor =
434459
function (firstNode, secondNode, current) {
435460
var firstNodeInLeft = this._existsInSubtree(firstNode, current._left);
@@ -449,6 +474,14 @@ <h1 class="page-title">Source: data-structures/binary-search-tree.js</h1>
449474
return null;
450475
};
451476

477+
/**
478+
* Checks if a given node exists in a subtree.
479+
*
480+
* @private
481+
* @param {Node} node Node to check for.
482+
* @param {Node} root Root node of a given subtree.
483+
* @returns {Node} The lowest common ancestor of the two nodes or null.
484+
*/
452485
exports.BinaryTree.prototype._existsInSubtree = function (node, root) {
453486
if (!root) {
454487
return false;
@@ -477,7 +510,7 @@ <h2><a href="index.html">Home</a></h2><h3>Modules</h3><ul><li><a href="module-co
477510
<brclass="clear">
478511

479512
<footer>
480-
Documentation generated by<ahref="https://github.com/jsdoc3/jsdoc">JSDoc 3.3.0-alpha13</a> onFri Feb 27 201509:39:04 GMT-0800 (PST)
513+
Documentation generated by<ahref="https://github.com/jsdoc3/jsdoc">JSDoc 3.3.0-alpha13</a> onTue Mar 10 201511:52:43 GMT-0700 (PDT)
481514
</footer>
482515

483516
<script>prettyPrint();</script>

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp