node-ds v0.0.10
node-ds
A common data-structure and basic algorithm implemention in javascript
Table of Contents
- Quick Start
- Data Structures
- Linear
- Trees
- Binary Tree
- Binary Search Tree
- Self-balancing binary search tree
- AVL Tree
- Scapegoat Tree
- Red-Black Tree B-trees B+ tree 2-3 tree 2-3-4 tree
- Heap
- Binary heap Weak heap Binomial heap * Fibonacci heap
- Binary Tree
- Graph
- Others
- Algorithms
- Test
- Contributing to node-ds
Quick Start
Installation
Installation is done using the npm install command:
$ npm install node-dsData Structures
Linear
Array
Linked List
insertStart(val)
valany
insertEnd(val)
valany
deleteFirst()
Returns the deleted node.
deleteLast()
Returns the deleted node.
traverse(fn)
fnFunction
Apply fn to each node, and returns an array of elements returned by fn.
length
The number of nodes contained in the list.
head
Gets the first element of the LinkedList.
Doubly Linked List
Same with LinkedList
Linked Queue
Queue implemented by DoublyLinkedList
enqueueNode(node)
nodeDoublyNode
Adds a node to the end of the Queue.
enqueue(val)
valany
Adds an element to the end of the Queue.
dequeueNode()
Removes and returns the node at the beginning of the Queue.
dequeue()
Removes and returns the element at the beginning of the Queue.
traverse(fn)
fnFunction
Apply fn to each node, and returns an array of elements returned by fn.
peek()
Returns the element at the beginning of the Queue without removing it.
clear()
Removes all elements from the Queue.
length
The number of elements contained in the Queue
Linked Stack
Stack implemented by DoublyLinkedList
pushNode(node)
nodeDoublyNode
push(val)
valany
popNode()
Removes and returns the node at the top of the Stack.
pop()
Removes and returns the element at the top of the Stack.
peek()
Returns the element at the top of the Stack without removing it.
clear()
Removes all elements from the Stack.
length
The size of queue
Trees
Binary Tree
Unlike List, Queue, Stack and Hashtable, binary trees store data in a non-linear fashion and is a special kind of tree, on in which all nodes have at most two children, left and right.
*inOrder()
Inorder traversal starts by visiting the current node's left child, then the current node, and then its right child.
*preOrder()
Preorder traversal starts by visiting the current node, then its left child, and then its right child.
*postOrder()
Postorder traversal starts by visiting the current node's left child, then its right child, and finally the current node itself.
*levelOrder()
Levelorder traversal starts by visiting the current node and nodes in the same height, from left to right.
clear()
Remove _root reference in binary tree.
root
Get or set the root node of the binary tree
Binary Search Tree
A binary search tree is a special kind of binary tree, for node n , every descendant node's value in left subtree is less than the value of n, and every descendant nodes' value in the right subtree is greater than the value of n.
add(val)
valany
Insert value according to the rule of BST.
delete(val)
valany
has(val)
valany
Return true or false if exist value.
Scapegoat Tree
A scapegoat tree is a self-balancing binary search tree. Instead of the small incremental rebalancing operations used by most balanced tree algorithms, scapegoat trees rarely but expensively choose a "scapegoat" and completely rebuild the subtree rooted at the scapegoat into a complete binary tree. Thus, scapegoat trees have O(n) worst-case update performance.
contructor(alpha = 0.667)
alphaNumber
α should be 0.5 < α < 1.A high α value results in fewer balances, making insertion quicker but lookups and deletions slower, and vice versa for a low α. Therefore in practical applications, an α can be chosen depending on how frequently these actions should be performed.
add(val)
valany
delete(val)
valany
has(val)
valany
Return true or false if exist value.
Others
Node
nextNodevalany
DoublyNode
prevDoublyNodenextDoublyNodevalany
BinaryTreeNode
leftBinaryTreeNoderightBinaryTreeNodevalany
Algorithms
Sorting Algorithms
Sort the given array in ascending order, which is numerical order for number, alphabetic order for string. For array consisting of other data types, or if a customed order is prefered, a compare funtion must be specified. All sorting algorithms follow the same API. Check it out below.
- SortFamily
- SortFamily.insertionSort(array[, compare, lo, hi]) or SortFamily.insertionSort(array, lo, hi)
- SortFamily.mergeSort(array[, compare, lo, hi]) or SortFamily.mergeSort(array, lo, hi)
- SortFamily.quickSort(array[, compare, lo, hi]) or SortFamily.quickSort(array, lo, hi)
- SortFamily.heapSort(array[, compare, lo, hi]) or SortFamily.heapSort(array, lo, hi)
options:- array: array to sort, must be javascript
Arrayobject - compare: optional, a function(@return 1 or -1 or 0) telling in what order an element should be sorted. If
compare(a, b) > 0, a will be placed after b, vice versa. Ifcompare(a, b) = 0, the order of a and b will depend on the sorting algorithm. Ifcompareis not specified, numbers will be sorted in numerical order, strings will be sorted in alphabetic order(according to gb2312 code point, if string cannot be encoded with gb2312, an error will be thrown) - lo: optional, default
0 - hi: optional, default
array.length - 1
- array: array to sort, must be javascript
Check some examples out below:
Statistics Algorithms
Find out outliers from the given data array based on some basic mathematical calculation(average、stdev).
Grubbs
const Grubbs = require('node-ds/Grubbs.js');
let data = [7, 9, 2, 6, 3, 5, 7, 2, 4, 20];
let grubbs = new Grubbs(data);
grubbs.getOutliers();//outputs [9], means the number 20 is outlierTest
Like most other packages, just run test suite and check code coverage by following commands:
$ npm test
$ npm run cover