bst-typed
What
Brief
This is a standalone BST (Binary Search Tree) data structure from the data-structure-typed collection. If you wish to access more data structures or advanced features, you can transition to directly installing the complete data-structure-typed package
How
install
npm
npm i bst-typed --save
yarn
yarn add bst-typed
methods
snippet
TS
import {BST, BSTNode} from 'data-structure-typed';
// /* or if you prefer */ import {BST, BSTNode} from 'bst-typed';
const bst = new BST();
bst instanceof BST; // true
bst.add(11);
bst.add(3);
const idsAndValues = [15, 1, 8, 13, 16, 2, 6, 9, 12, 14, 4, 7, 10, 5];
bst.addMany(idsAndValues);
bst.root instanceof BSTNode; // true
if (bst.root) bst.root.id; // 11
bst.size; // 16
bst.has(6); // true
const node6 = bst.get(6);
node6 && bst.getHeight(6); // 2
node6 && bst.getDepth(6); // 3
const nodeId10 = bst.get(10);
nodeId10?.id; // 10
const nodeVal9 = bst.get(9, 'val');
nodeVal9?.id; // 9
const leftMost = bst.getLeftMost();
leftMost?.id; // 1
const node15 = bst.get(15);
const minNodeBySpecificNode = node15 && bst.getLeftMost(node15);
minNodeBySpecificNode?.id; // 12
const subTreeSum = node15 && bst.subTreeSum(15);
subTreeSum; // 70
const lesserSum = bst.lesserSum(10);
lesserSum; // 45
node15 instanceof BSTNode; // true
const node11 = bst.get(11);
node11 instanceof BSTNode; // true
const dfsInorderNodes = bst.DFS('in', 'node');
dfsInorderNodes[0].id; // 1
dfsInorderNodes[dfsInorderNodes.length - 1].id; // 16
bst.perfectlyBalance();
bst.isPerfectlyBalanced(); // true
const bfsNodesAfterBalanced = bst.BFS('node');
bfsNodesAfterBalanced[0].id; // 8);
bfsNodesAfterBalanced[bfsNodesAfterBalanced.length - 1].id; // 16
const removed11 = bst.remove(11, true);
removed11 instanceof Array; // true
if (removed11[0].deleted) removed11[0].deleted.id; // 11
bst.isAVLBalanced(); // true
bst.getHeight(15); // 1
const removed1 = bst.remove(1, true);
removed1 instanceof Array; // true
if (removed1[0].deleted) removed1[0].deleted.id; // 1
bst.isAVLBalanced(); // true
bst.getHeight(); // 4
const removed4 = bst.remove(4, true);
removed4 instanceof Array; // true
if (removed4[0].deleted) removed4[0].deleted.id; // 4
bst.isAVLBalanced(); // true
bst.getHeight(); // 4
const removed10 = bst.remove(10, true);
if (removed10[0].deleted) removed10[0].deleted.id; // 10
bst.isAVLBalanced(); // false
bst.getHeight(); // 4
const removed15 = bst.remove(15, true);
if (removed15[0].deleted) removed15[0].deleted.id; // 15
bst.isAVLBalanced(); // true
bst.getHeight(); // 3
const removed5 = bst.remove(5, true);
if (removed5[0].deleted) removed5[0].deleted.id; // 5
bst.isAVLBalanced(); // true
bst.getHeight(); // 3
const removed13 = bst.remove(13, true);
if (removed13[0].deleted) removed13[0].deleted.id; // 13
bst.isAVLBalanced(); // true
bst.getHeight(); // 3
const removed3 = bst.remove(3, true);
if (removed3[0].deleted) removed3[0].deleted.id; // 3
bst.isAVLBalanced(); // false
bst.getHeight(); // 3
const removed8 = bst.remove(8, true);
if (removed8[0].deleted) removed8[0].deleted.id; // 8
bst.isAVLBalanced(); // true
bst.getHeight(); // 3
const removed6 = bst.remove(6, true);
if (removed6[0].deleted) removed6[0].deleted.id; // 6
bst.remove(6, true).length; // 0
bst.isAVLBalanced(); // false
bst.getHeight(); // 3
const removed7 = bst.remove(7, true);
if (removed7[0].deleted) removed7[0].deleted.id; // 7
bst.isAVLBalanced(); // false
bst.getHeight(); // 3
const removed9 = bst.remove(9, true);
if (removed9[0].deleted) removed9[0].deleted.id; // 9
bst.isAVLBalanced(); // false
bst.getHeight(); // 3
const removed14 = bst.remove(14, true);
if (removed14[0].deleted) removed14[0].deleted.id; // 14
bst.isAVLBalanced(); // false
bst.getHeight(); // 2
bst.isAVLBalanced(); // false
const bfsIDs = bst.BFS();
bfsIDs[0]; // 2
bfsIDs[1]; // 12
bfsIDs[2]; // 16
const bfsNodes = bst.BFS('node');
bfsNodes[0].id; // 2
bfsNodes[1].id; // 12
bfsNodes[2].id; // 16
JS
const {BST, BSTNode} = require('data-structure-typed');
// /* or if you prefer */ const {BST, BSTNode} = require('bst-typed');
const bst = new BST();
bst instanceof BST; // true
bst.add(11);
bst.add(3);
const idsAndValues = [15, 1, 8, 13, 16, 2, 6, 9, 12, 14, 4, 7, 10, 5];
bst.addMany(idsAndValues);
bst.root instanceof BSTNode; // true
if (bst.root) bst.root.id; // 11
bst.size; // 16
bst.has(6); // true
const node6 = bst.get(6);
node6 && bst.getHeight(6); // 2
node6 && bst.getDepth(6); // 3
const nodeId10 = bst.get(10);
nodeId10?.id; // 10
const nodeVal9 = bst.get(9, 'val');
nodeVal9?.id; // 9
const leftMost = bst.getLeftMost();
leftMost?.id; // 1
const node15 = bst.get(15);
const minNodeBySpecificNode = node15 && bst.getLeftMost(node15);
minNodeBySpecificNode?.id; // 12
const subTreeSum = node15 && bst.subTreeSum(15);
subTreeSum; // 70
const lesserSum = bst.lesserSum(10);
lesserSum; // 45
node15 instanceof BSTNode; // true
const node11 = bst.get(11);
node11 instanceof BSTNode; // true
const dfsInorderNodes = bst.DFS('in', 'node');
dfsInorderNodes[0].id; // 1
dfsInorderNodes[dfsInorderNodes.length - 1].id; // 16
bst.perfectlyBalance();
bst.isPerfectlyBalanced(); // true
const bfsNodesAfterBalanced = bst.BFS('node');
bfsNodesAfterBalanced[0].id; // 8);
bfsNodesAfterBalanced[bfsNodesAfterBalanced.length - 1].id; // 16
const removed11 = bst.remove(11, true);
removed11 instanceof Array; // true
if (removed11[0].deleted) removed11[0].deleted.id; // 11
bst.isAVLBalanced(); // true
bst.getHeight(15); // 1
const removed1 = bst.remove(1, true);
removed1 instanceof Array; // true
if (removed1[0].deleted) removed1[0].deleted.id; // 1
bst.isAVLBalanced(); // true
bst.getHeight(); // 4
const removed4 = bst.remove(4, true);
removed4 instanceof Array; // true
if (removed4[0].deleted) removed4[0].deleted.id; // 4
bst.isAVLBalanced(); // true
bst.getHeight(); // 4
const removed10 = bst.remove(10, true);
if (removed10[0].deleted) removed10[0].deleted.id; // 10
bst.isAVLBalanced(); // false
bst.getHeight(); // 4
const removed15 = bst.remove(15, true);
if (removed15[0].deleted) removed15[0].deleted.id; // 15
bst.isAVLBalanced(); // true
bst.getHeight(); // 3
const removed5 = bst.remove(5, true);
if (removed5[0].deleted) removed5[0].deleted.id; // 5
bst.isAVLBalanced(); // true
bst.getHeight(); // 3
const removed13 = bst.remove(13, true);
if (removed13[0].deleted) removed13[0].deleted.id; // 13
bst.isAVLBalanced(); // true
bst.getHeight(); // 3
const removed3 = bst.remove(3, true);
if (removed3[0].deleted) removed3[0].deleted.id; // 3
bst.isAVLBalanced(); // false
bst.getHeight(); // 3
const removed8 = bst.remove(8, true);
if (removed8[0].deleted) removed8[0].deleted.id; // 8
bst.isAVLBalanced(); // true
bst.getHeight(); // 3
const removed6 = bst.remove(6, true);
if (removed6[0].deleted) removed6[0].deleted.id; // 6
bst.remove(6, true).length; // 0
bst.isAVLBalanced(); // false
bst.getHeight(); // 3
const removed7 = bst.remove(7, true);
if (removed7[0].deleted) removed7[0].deleted.id; // 7
bst.isAVLBalanced(); // false
bst.getHeight(); // 3
const removed9 = bst.remove(9, true);
if (removed9[0].deleted) removed9[0].deleted.id; // 9
bst.isAVLBalanced(); // false
bst.getHeight(); // 3
const removed14 = bst.remove(14, true);
if (removed14[0].deleted) removed14[0].deleted.id; // 14
bst.isAVLBalanced(); // false
bst.getHeight(); // 2
bst.isAVLBalanced(); // false
const bfsIDs = bst.BFS();
bfsIDs[0]; // 2
bfsIDs[1]; // 12
bfsIDs[2]; // 16
const bfsNodes = bst.BFS('node');
bfsNodes[0].id; // 2
bfsNodes[1].id; // 12
bfsNodes[2].id; // 16
API docs & Examples
Data Structures
| Data Structure | Unit Test | Performance Test | API Documentation | Implemented |
|---|---|---|---|---|
| Binary Tree | 
|
|
Binary Tree | |
| Binary Search Tree (BST) | |
|
BST | |
| AVL Tree | |
|
AVLTree | |
| Tree Multiset | |
|
TreeMultiset | |
| Segment Tree | SegmentTree | |
||
| Binary Indexed Tree | |
BinaryIndexedTree | |
|
| Graph | |
|
AbstractGraph | |
| Directed Graph | |
|
DirectedGraph | |
| Undirected Graph | |
|
UndirectedGraph | |
| Linked List | |
|
SinglyLinkedList | |
| Singly Linked List | |
|
SinglyLinkedList | |
| Doubly Linked List | |
|
DoublyLinkedList | |
| Queue | |
|
Queue | |
| Object Deque | |
|
ObjectDeque | |
| Array Deque | |
|
ArrayDeque | |
| Stack | |
Stack | |
|
| Coordinate Set | CoordinateSet | |
||
| Coordinate Map | CoordinateMap | |
||
| Heap | |
|
Heap | |
| Priority Queue | |
|
PriorityQueue | |
| Max Priority Queue | |
|
MaxPriorityQueue | |
| Min Priority Queue | |
|
MinPriorityQueue | |
| Trie | |
Trie | |
Why
Complexities
performance of Big O
| Big O Notation | Type | Computations for 10 elements | Computations for 100 elements | Computations for 1000 elements |
|---|---|---|---|---|
| O(1) | Constant | 1 | 1 | 1 |
| O(log N) | Logarithmic | 3 | 6 | 9 |
| O(N) | Linear | 10 | 100 | 1000 |
| O(N log N) | n log(n) | 30 | 600 | 9000 |
| O(N^2) | Quadratic | 100 | 10000 | 1000000 |
| O(2^N) | Exponential | 1024 | 1.26e+29 | 1.07e+301 |
| O(N!) | Factorial | 3628800 | 9.3e+157 | 4.02e+2567 |
Data Structure Complexity
| Data Structure | Access | Search | Insertion | Deletion | Comments |
|---|---|---|---|---|---|
| Array | 1 | n | n | n | |
| Stack | n | n | 1 | 1 | |
| Queue | n | n | 1 | 1 | |
| Linked List | n | n | 1 | n | |
| Hash Table | - | n | n | n | In case of perfect hash function costs would be O(1) |
| Binary Search Tree | n | n | n | n | In case of balanced tree costs would be O(log(n)) |
| B-Tree | log(n) | log(n) | log(n) | log(n) | |
| Red-Black Tree | log(n) | log(n) | log(n) | log(n) | |
| AVL Tree | log(n) | log(n) | log(n) | log(n) | |
| Bloom Filter | - | 1 | 1 | - | False positives are possible while searching |
Sorting Complexity
| Name | Best | Average | Worst | Memory | Stable | Comments |
|---|---|---|---|---|---|---|
| Bubble sort | n | n2 | n2 | 1 | Yes | |
| Insertion sort | n | n2 | n2 | 1 | Yes | |
| Selection sort | n2 | n2 | n2 | 1 | No | |
| Heap sort | n log(n) | n log(n) | n log(n) | 1 | No | |
| Merge sort | n log(n) | n log(n) | n log(n) | n | Yes | |
| Quick sort | n log(n) | n log(n) | n2 | log(n) | No | Quicksort is usually done in-place with O(log(n)) stack space |
| Shell sort | n log(n) | depends on gap sequence | n (log(n))2 | 1 | No | |
| Counting sort | n + r | n + r | n + r | n + r | Yes | r - biggest number in array |
| Radix sort | n * k | n * k | n * k | n + k | Yes | k - length of longest key |
