Skip to content

Commit a986809

Browse files
JakeHPJakeHP
committed
Added more docs for datastructures.
1 parent 7bebda6 commit a986809

5 files changed

Lines changed: 104 additions & 4 deletions

File tree

‎src/data-structures/avl-tree.js‎

Lines changed: 18 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -93,6 +93,15 @@
9393
return true;
9494
};
9595

96+
/**
97+
* Gets the nodes to be restructured during an AVL restructure
98+
* after a remove/delete takes place.
99+
*
100+
* @public
101+
* @method
102+
* @param {Array} traveledNodes Array of previously traveled nodes
103+
* that are used to help determine the nodes to be restructured.
104+
*/
96105
exports.AVLTree.prototype._getNodesToRestructureRemove =
97106
function (traveledNodes) {
98107
// z is last traveled node - imbalance found at z
@@ -129,6 +138,15 @@
129138
return [x, y, z];
130139
};
131140

141+
/**
142+
* Gets the nodes to be restructured during an AVL restructure
143+
* after an insert takes place.
144+
*
145+
* @public
146+
* @method
147+
* @param {Array} traveledNodes Array of previously traveled nodes
148+
* that are used to help determine the nodes to be restructured.
149+
*/
132150
exports.AVLTree.prototype._getNodesToRestructureInsert =
133151
function (traveledNodes) {
134152
// z is last traveled node - imbalance found at z

‎src/data-structures/binary-search-tree.js‎

Lines changed: 37 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -330,6 +330,13 @@
330330
return this._findMax(this._root);
331331
};
332332

333+
/**
334+
* Checks if a given node is balanced.
335+
*
336+
* @private
337+
* @param {Node} current Node to have balance checked.
338+
* @returns {Boolean} Boolean of whether or not provided node is balanced.
339+
*/
333340
exports.BinaryTree.prototype._isBalanced = function (current) {
334341
if (!current) {
335342
return true;
@@ -379,6 +386,13 @@
379386
return this._getHeight(this._root);
380387
};
381388

389+
/**
390+
* Recursive worker function for getHeight()
391+
*
392+
* @private
393+
* @param {Node} node Node at current recursive frame.
394+
* @returns {Number} Height of the Node in the parameter.
395+
*/
382396
exports.BinaryTree.prototype._getHeight = function (node) {
383397
if (!node) {
384398
return 0;
@@ -391,13 +405,28 @@
391405
* Finds the lowest common ancestor of two nodes.
392406
*
393407
* @public
408+
* @param {Node} firstNode First node to be considered when checking
409+
* for ancestor.
410+
* @param {Node} secondNode Second node to be considered when checking
411+
* for ancestor.
394412
* @returns {Node} The lowest common ancestor of the two nodes or null.
395413
*/
396414
exports.BinaryTree.prototype.lowestCommonAncestor =
397415
function (firstNode, secondNode) {
398416
return this._lowestCommonAncestor(firstNode, secondNode, this._root);
399417
};
400418

419+
/**
420+
* Obtains the lowest common ancestor for the given nodes.
421+
*
422+
* @private
423+
* @param {Node} firstNode First node to be considered when checking
424+
* for ancestor.
425+
* @param {Node} secondNode Second node to be considered when checking
426+
* for ancestor.
427+
* @param {Node} current Current node.
428+
* @returns {Node} The lowest common ancestor of the two nodes or null.
429+
*/
401430
exports.BinaryTree.prototype._lowestCommonAncestor =
402431
function (firstNode, secondNode, current) {
403432
var firstNodeInLeft = this._existsInSubtree(firstNode, current._left);
@@ -417,6 +446,14 @@
417446
return null;
418447
};
419448

449+
/**
450+
* Checks if a given node exists in a subtree.
451+
*
452+
* @private
453+
* @param {Node} node Node to check for.
454+
* @param {Node} root Root node of a given subtree.
455+
* @returns {Node} The lowest common ancestor of the two nodes or null.
456+
*/
420457
exports.BinaryTree.prototype._existsInSubtree = function (node, root) {
421458
if (!root) {
422459
return false;

‎src/data-structures/linked-list.js‎

Lines changed: 12 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -222,6 +222,12 @@
222222
return temp;
223223
};
224224

225+
/**
226+
* Reverses the linked list recursively
227+
*
228+
* @public
229+
* @method
230+
*/
225231
exports.LinkedList.prototype.recursiveReverse = function () {
226232

227233
function inverse(current, next) {
@@ -242,6 +248,12 @@
242248
this.last = temp;
243249
};
244250

251+
/**
252+
* Reverses the linked list iteratively
253+
*
254+
* @public
255+
* @method
256+
*/
245257
exports.LinkedList.prototype.reverse = function () {
246258
if (!this.first || !this.first.next) {
247259
return;

‎src/data-structures/splay-tree.js‎

Lines changed: 34 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -58,6 +58,7 @@
5858
* @private
5959
* @method
6060
* @param {Node} node Node to be splayed.
61+
* @returns {Node} The same node from the parameter, post splayed.
6162
*/
6263
exports.SplayTree.prototype._splay = function (node) {
6364
while (this._root !== node) {
@@ -87,6 +88,7 @@
8788
* @private
8889
* @method
8990
* @param {Node} node Node to be zig-zig'd.
91+
* @returns {Node} The same node from the parameter, post splayed.
9092
*/
9193
exports.SplayTree.prototype._zigZig = function (node) {
9294

@@ -136,6 +138,7 @@
136138
* @private
137139
* @method
138140
* @param {Node} node Node to be zig-zag'd.
141+
* @returns {Node} The same node from the parameter, post splayed.
139142
*/
140143
exports.SplayTree.prototype._zigZag = function (node) {
141144

@@ -185,6 +188,7 @@
185188
* @private
186189
* @method
187190
* @param {Node} node Node to be zig'd.
191+
* @returns {Node} The same node from the parameter, post splayed.
188192
*/
189193
exports.SplayTree.prototype._zig = function (node) {
190194

@@ -334,7 +338,7 @@
334338
* Average time complexity: O(log N).
335339
*
336340
* @public
337-
* @param {Number|String} Value of the node which should be found.
341+
* @param {Number|String} value of the node which should be found.
338342
*/
339343
exports.SplayTree.prototype.search = function (value) {
340344
var node = this._search(value, this._root);
@@ -346,7 +350,7 @@
346350
* Average time complexity: O(log N).
347351
*
348352
* @public
349-
* @param {Number|String} Value of the node which should be found.
353+
* @param {Number|String} value of the node which should be found.
350354
*/
351355
exports.SplayTree.prototype._splaylessSearch = function (value) {
352356
return this._search(value, this._root);
@@ -357,8 +361,8 @@
357361
* Average time complexity: O(log N).
358362
*
359363
* @private
360-
* @param {Number|String} Value of the node which should be found.
361-
* @param {Node} Current node to be checked.
364+
* @param {Number|String} value of the node which should be found.
365+
* @param {Node} current node to be checked.
362366
*/
363367
exports.SplayTree.prototype._search = function (value, current) {
364368
if (!current) {
@@ -512,6 +516,13 @@
512516
return this._getHeight(this._root);
513517
};
514518

519+
/**
520+
* Recursive worker function for getHeight()
521+
*
522+
* @public
523+
* @param {Node} node The node of the current recursive frame.
524+
* @returns {Number} The height of the tree.
525+
*/
515526
exports.SplayTree.prototype._getHeight = function (node) {
516527
if (!node) {
517528
return 0;
@@ -531,6 +542,17 @@
531542
return this._lowestCommonAncestor(firstNode, secondNode, this._root);
532543
};
533544

545+
/**
546+
* Obtains the lowest common ancestor for the given nodes.
547+
*
548+
* @private
549+
* @param {Node} firstNode First node to be considered when checking
550+
* for ancestor.
551+
* @param {Node} secondNode Second node to be considered when checking
552+
* for ancestor.
553+
* @param {Node} current Current node.
554+
* @returns {Node} The lowest common ancestor of the two nodes or null.
555+
*/
534556
exports.SplayTree.prototype._lowestCommonAncestor =
535557
function (firstNode, secondNode, current) {
536558
var firstNodeInLeft = this._existsInSubtree(firstNode, current._left);
@@ -551,6 +573,14 @@
551573
return null;
552574
};
553575

576+
/**
577+
* Checks if a given node exists in a subtree.
578+
*
579+
* @private
580+
* @param {Node} node Node to check for.
581+
* @param {Node} root Root node of a given subtree.
582+
* @returns {Node} The lowest common ancestor of the two nodes or null.
583+
*/
554584
exports.SplayTree.prototype._existsInSubtree = function (node, root) {
555585
if (!root) {
556586
return false;

‎src/sorting/heapsort.js‎

Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -14,6 +14,8 @@
1414
* @param {Array} array Array.
1515
* @param {Number} index Index of the element which palce in
1616
* the max heap should be found.
17+
* @param {Number} heapSize Size of the heap.
18+
* @param {function} cmp Comparison function.
1719
*/
1820
function heapify(array, index, heapSize, cmp) {
1921
var left = 2 * index + 1;
@@ -41,6 +43,7 @@
4143
*
4244
* @private
4345
* @param {Array} array Array which should be turned into max heap.
46+
* @param {function} cmp Comparison function.
4447
* @return {Array} array Array turned into max heap.
4548
*/
4649
function buildMaxHeap(array, cmp) {

0 commit comments

Comments
 (0)