Idea: An array is a composite data type - it can store multiple values, and so is in the collection category. The stored values are called elements and are accessed by a sequence of indices.
The implementation of arrays is based on setting the bounds of indices of the array, the size of the array, normally by allocating a contiguous region of memory to hold the elements of the array, and using simple offset calculations on the indices from the origin of the memory to access memory elements.
Common operations defined on arrays include: 1) indexing (accessing an array element by its indices); 2) slicing (producing a subarray by putting some constraint on the indices); 3) iteration over the array's elements.
Access is O(1), appending is O(1), and insertion is O(n) for a single item.
Idea: A linked list is a collection of nodes that form linear sequence. Each node contains data and reference (link) to another nodes.
Linked lists have a "head" (the first node in the list) and sometimes a "tail" (the last node).
A singly-linked list allows traversal in one direction - forward. Each node contains a link to the next node. The last node points to null. Singly-linked list has O(1) insertion time [insertion itself is O(1), but node finding is O(n)] and O(n) removal time.
A doubly-linked list allows traversal in two directions - forward and back. Each node contains links to both the previous and next nodes. Doubly-linked list has O(1) removal and insertion times.
/* Singly-linked list */
// node of the list
function Node(data) {
this.data = data; // node's data
this.next = null; // pointer (link) to the next node
}
// singly-linked list
function SLList() {
this.head = new Node("head");
this.append = append;
this.prepend = prepend;
this.insertAfter = insertAfter;
this.insertBefore = insertBefore;
this.remove = remove;
this.print = print;
// helper functions
this.find = find;
this.findPrev = findPrev;
}
// find node with data == item
function find(item) {
var current = this.head;
while (current.data != item) {
current = current.next;
}
return current;
}
// find previous node to node with data == item
function findPrev(item) {
var current = this.head;
while (current.next.data != item) {
current = current.next;
}
return current;
}
// add element to the end
function append(element) {
var newEnd = new Node(element);
// find last
var current = this.head;
while (current.next != null) {
current = current.next;
}
current.next = newEnd;
}
// add element to the beginning
function prepend(element) {
var newHead = new Node(element);
newHead.next = this.head.next;
this.head.next = newHead;
}
// insert element after specific item
function insertAfter(element, item) {
var newNode = new Node(element);
var current = this.find(item);
newNode.next = current.next;
current.next = newNode;
}
// insert element before specific item
function insertBefore(element, item) {
var newNode = new Node(element);
var current = this.findPrev(item);
newNode.next = current.next;
current.next = newNode;
}
// remove node with data == item
function remove(item) {
var current = this.findPrev(item);
// link prev node to the node after item
if (current.next != null) {
current.next = current.next.next;
}
}
// print list
function print() {
var current = this.head;
while (current.next != null) {
console.log(current.next.data);
current = current.next;
}
}
Idea: A queue is a linear FIFO (First-In-First-Out) abstract data structure. That is, elements are added (enqueued) at one side and removed (dequeued) from the other in the order of insertion.
Space and search complexity is O(n), insertion/deletion is O(1).
// Queue implementation using circular array
// next index in circular array of size N is (i+1)%N
// thus for i=N-1 next index is N%N=0
// prev index is (i+N-1)%N
// https://www.youtube.com/watch?v=okr-XE8yTO8
function Queue(size = 10) {
this.SIZE = size;
this.data = new Array(this.SIZE);
// -1 represents invalid index of an empty queue
this.front = -1; // front element index
this.rear = -1; // rear element index
this.isEmpty = isEmpty;
this.isFull = isFull;
this.enqueue = enqueue;
this.dequeue = dequeue;
this.head = head;
this.print = print;
}
// check if queue is epmty
function isEmpty() {
// if front == -1, queue is empty
return this.front == -1;
}
// check if queue is full
function isFull() {
return ((this.rear+1)%this.SIZE == this.front);
}
// add element to tail
function enqueue(element) {
if (this.isFull()) {
console.log("Error: Queue is full");
return;
}
if (this.isEmpty()) {
this.front = 0;
this.rear = 0;
} else {
this.rear = (this.rear+1)%this.SIZE;
}
this.data[this.rear] = element;
}
// remove element from head
function dequeue() {
if (this.isEmpty()) {
console.log("Error: Queue is empty");
return;
}
else if (this.front == this.rear) { // queue becomes empty
this.front = -1;
this.rear = -1;
} else {
this.front = (this.front+1)%this.SIZE;
}
}
// return head element
function head() {
if (this.isEmpty()) {
console.log("Error: Queue is empty");
return;
}
return this.data[this.front];
}
// print queue
function print() {
if (this.isEmpty()) return;
var i = this.front;
while (i <= this.rear) {
console.log(this.data[i]);
i++;
}
}
Idea: A stack is a linear LIFO (Last-In-First-Out) abstract data structure. That is, elements are added (pushed) and removed (poped) from one end called top of the stack.
Space and search complexity is O(n), insertion/deletion is O(1).
// Stack implementation using array
// https://www.youtube.com/watch?v=sFVxsglODoo
function Stack(size = 5) {
this.SIZE = size;
this.data = new Array(this.SIZE);
// top of the stack, -1 represents empty stack
this.topIndex = -1;
this.push = push;
this.pop = pop;
this.topElem = topElem;
this.isEmpty = isEmpty;
this.isFull = isFull;
this.print = print;
}
// add item to stack
function push(item) {
if (this.isFull()) {
console.log("Error: stack overflow");
return;
}
this.topIndex++;
this.data[this.topIndex] = item;
}
// remove item from stack
function pop() {
if (this.isEmpty()) {
console.log("Error: no element to pop");
}
this.topIndex--;
}
// return top item
function topElem() {
return this.data[this.topIndex];
}
// check if stack is empty
function isEmpty() {
return (this.topIndex == -1);
}
// check if stack is full
function isFull() {
return (this.topIndex == this.SIZE - 1);
}
// print stack
function print() {
if (this.isEmpty()) return;
var i = this.topIndex;
while (i >= 0) {
console.log(this.data[i]);
i--;
}
}
Idea: A tree is a revursive data structure with a root and one or more children - nodes which may have thier own subtrees. Number of direct descendants of the node defines its power (order). Max power of the nodes define the power of the tree. A tree is perfectly balanced if for every node number of nodes in left and right subtrees differs by no more than 1.
Binary tree is a set of nodes that consits of a root and two children - left and right binary subtrees.
Binary search tree (BST) is ordered data structure which has the following properties: 1) left subtree of a node contains only nodes with keys lesser than or equal to the node’s key; 2) right subtree of a node contains only nodes with keys greater than the node’s key; 3) left and right subtree each must also be a binary search tree.
Balanced tree (AVL tree - Adelson-Velsky and Landis) is a self-balancing binary search tree where the heights of the two child subtrees of any node differ by at most one; if at any time they differ by more than one, rebalancing is done to restore this property.
Search, insertion and deletion is O(log n) in average case and O(n) in worst case. Space is O(n).
// https://www.youtube.com/watch?v=pYT9F8_LFTM
// https://www.youtube.com/watch?v=COZK7NATh4k
// https://www.freecodecamp.org/news/data-structures-101-binary-search-tree-398267b6bff0/
// node
function Node(data) {
this.data = data;
this.left = null; // link to the left child
this.right = null; // link to the right child
}
// tree
function BSTree() {
this.root = null;
}
// insert node (recursive)
BSTree.prototype.insertRec = function(data) {
var node = new Node(data);
var insertRecHelper = function(root, node) {
if (node.data <= root.data) { // go to the left subtree
// we've reached a leaf node, insert
if (root.left === null) root.left = node;
else insertRecHelper(root.left, node);
} else { // go to the right subtree
if (root.right === null) root.right = node;
else insertRecHelper(root.right, node);
}
}
// if tree is empty
if (this.root === null) this.root = node;
// if tree is not empty
else insertRecHelper(this.root, node);
}
// insert node (non-recursive)
BSTree.prototype.insert = function(data) {
var node = new Node(data);
// if tree is empty
if (this.root === null) this.root = node;
else { // if tree is not empty
var current = this.root;
while (current) {
// go down to left subtree
if (node.data <= current.data) {
if (current.left === null) {
current.left = node;
break;
}
current = current.left;
}
// go down to right subtree
else if (node.data > current.data) {
if (current.right === null) {
current.right = node;
break;
}
current = current.right;
} else break;
}
}
};
// remove node
BSTree.prototype.remove = function(data) {
var that = this;
var removeNode = function(node, data) {
if (node === null) return null; // tree is empty
if (data < node.data) { // go left subtree
node.left = removeNode(node.left, data);
return node;
} else if (data > node.data) { // go right subtree
node.right = removeNode(node.right, data);
return node;
} else { // data == node data
// case 1: node has no children
if (node.left === null && node.right === null) {
node = null;
return null;
}
// case 2: 1 child
if (node.left === null) { // right child
node = node.right;
return node;
}
if (node.right === null) { // left child
node = node.left;
return node;
}
// case 3: 2 children
// find left-most node of right subtree (min)
// or right-most child of left subtree (max)
var temp = that.getMin(node.right);
node.data = temp;
node.right = removeNode(node.right, temp);
return node;
}
};
this.root = removeNode(this.root, data);
};
// get minimum value - find the leftmost node of left subtree
BSTree.prototype.getMin = function(node) {
if (!node) node = this.root;
while (node.left) node = node.left;
return node.data;
};
// get maximum value - find the righttmost node of right subtree
BSTree.prototype.getMax = function() {
var node = this.root;
while (node.right) node = node.right;
return node.data;
};
// check if tree contains a node
BSTree.prototype.contains = function(data) {
var current = this.root;
while (current) {
if (data === current.data) return true;
if (data <= current.data) current = current.left;
else current = current.right;
}
return false;
};
// height of the three
BSTree.prototype.getHeight = function(node=this.root) {
if (!node) return -1;
var left = this.getHeight(node.left);
var right = this.getHeight(node.right);
return Math.max(left, right) + 1;
};
// root-left-right traverse
BSTree.prototype.preOrder = function(node, func) {
if (node) {
if (func) func(node); // root
this.preOrder(node.left, func); // left child
this.preOrder(node.right, func); // right child
}
};
// left-root-right traverse (smallest to largest in this case)
BSTree.prototype.inOrder = function(node, func) {
if (node) {
this.inOrder(node.left, func); // left child
if (func) func(node); // root
this.inOrder(node.right, func); // right child
}
};
// left-right-root traverse
BSTree.prototype.postOrder = function(node, func) {
if (node) {
this.postOrder(node.left, func); // left child
this.postOrder(node.right, func); // right child
if (func) func(node); // root
}
};
// Depth-First Search
BSTree.prototype.traverseDFS = function(func, method) {
var current = this.root;
if (method) this[method](current, func);
else this.preOrder(current, func);
};
// Breadth-First Search
BSTree.prototype.traverseBFS = function(func) {
this.queue = [];
this.queue.push(this.root);
while (this.queue.length) {
var node = this.queue.shift();
if (func) func(node);
if (node.left) this.queue.push(node.left);
if (node.right) this.queue.push(node.right);
}
};
// size - number of elements
BSTree.prototype.size = function() {
var length = 0;
this.traverseDFS(function(node) {
length++;
}, "inOrder");
return length;
};
// print
BSTree.prototype.print = function() {
var newLine = new Node("|");
var queue = [this.root, newLine];
var string = "";
while (queue.length) {
var node = queue.shift();
string += node.data.toString() + " ";
if (node === newLine && queue.length) {
queue.push(newLine);
}
if (node.left) queue.push(node.left);
if (node.right) queue.push(node.right);
}
console.log(string.slice(0, -2).trim());
};
Idea: A red–black tree is a self-balancing binary search tree. Each node of the tree has an extra bit often interpreted as the color (red or black) of the node. These color bits are used to ensure the tree remains approximately balanced during insertions and deletions.
Balance is preserved by painting each node with red or black color in a way that satisfies certain properties:
1) Each node is either red or black.
2) The root is black.
3) All leaves (NULL nodes) are black.
4) If a node is red, then both its children are black.
5) Every path from a given node to any of its descendant NULL nodes contains the same number of black nodes.
The balancing of the tree is not perfect, but it is good enough to allow searching in O(log n) time. The insertion and deletion operations, along with the tree rearrangement and recoloring, are also performed in O(log n) time.
// https://www.youtube.com/watch?v=UaLIHuR1t8Q
// https://www.youtube.com/watch?v=CTvfzU_uNKE
// In Red-Black tree, we use 2 tools to do balancing:
// 1) recoloring
// 2) rotation
// Notation: new node X, it's parent P, grandparent G, uncle U
// The insertion algorithm has 2 main cases
// depending on the color of U:
// 1) if U = red, we do recoloring
// 2) if U = black, we do rotations and/or recoloring
// Insertion algorithm:
// 1. Insert new node X and color it red
// 2. Recolor and rotate nodes to fix violations
// Four cases:
// 1) X = root -> color black
// 2) X.U = red -> recolor P, G, U
// 3) X.U = black (triangle) -> rotate X.P
// 4) X.U = black (line) -> rotate X.G & recolor
// Deletion algorithm:
// 1. Find the node to be deleted X using BST traversal
// 2. If X has 2 non-null children,
// replace it with its inorder successor,
// then delete successor
// 3. If X is red, delete it
// 4. If X is black with one red child,
// replace it with that child and
// change color of the child to black
// 5. Otherwise (X is black with 2 black null leaves)
// handle the double-black node situation with 6 cases
// https://medium.com/@julianknodt/red-black-trees-in-javascript-c20eec1d5d1c
const identity = i => i;
const RIGHT = 1;
const LEFT = 0;
const oppDir = dir => dir === RIGHT ? LEFT : RIGHT;
class BinaryTree {
constructor(value, identifier=identity) {
this.value = value;
this.children = [];
this.identifier = identifier;
this.parent = undefined;
}
get right() { return this.children[RIGHT]; }
get left() { return this.children[LEFT]; }
set right(value) { this.children[RIGHT] = value; }
set left(value) { this.children[LEFT] = value; }
get isRightChild() {
return this.parent ? this.parent.right === this : false;
}
get isLeftChild() {
return this.parent ? this.parent.left === this : false;
}
get isRoot() { return this.parent === undefined; }
get uncle() {
return this.grandparent ? (this.parent.isRightChild ? this.grandparent.left : this.grandparent.right) : undefined;
}
get sibling() {
return this.parent ? (this.isRightChild ? this.parent.left : this.parent.right) : undefined;
}
get grandparent() {
return this.parent ? this.parent.parent : undefined;
}
get isLeaf() {
return this.children.every(child => child === undefined);
}
get hasOneChild() {
return (this.right !== undefined && this.left === undefined)
|| (this.right === undefined && this.left !== undefined);
}
get hasTwoChildren() {
return (this.right !== undefined && this.left !== undefined);
}
_swapWithParent () {
//need to create a new node to replace old one;
let replacement = new BinaryTree(this.value, this.identifier);
replacement.parent = this.parent;
replacement.children = this.children;
if (this.parent !== undefined) {
if (this.isRightChild) {
this.parent.right = replacement;
} else {
this.parent.left = replacement;
}
}
this.value = replacement.parent.value;
this.children = replacement.parent.children;
this.parent = replacement.parent.parent;
//update references to this
this.children.forEach(chiLd => {
if (child) child.parent = this;
});
//update references to replacement
this.children.forEach(child => {
if (child) child.children.forEach(kid => {
if (kid) kid.parent = child;
});
});
}
rotateRight() {
this._rotate(RIGHT);
this._swapWithParent();
}
rotateLeft() {
this._rotate(LEFT);
this._swapWithParent();
}
_rotate(dir) {
let opposite = oppDir(dir);
let pivot = this.children[opposite];
this.children[opposite] = pivot.children[dir];
pivot.children[dir] = this;
pivot.parent = this.parent;
pivot.children.forEach(child => {
if (child) child.parent = pivot;
});
this.children.forEach(child => {
if (child) child.parent = this;
});
}
insert(value) {
if (this.value === undefined) {
this.value = value;
return this;
} else {
let dir;
if (this.identifier(value) > this.identifier(this.value)) {
dir = RIGHT;
} else dir = LEFT;
if (this.children[dir] === undefined) {
let newTree = new BinaryTree(value, this.identifier);
newTree.parent = this;
this.children[dir] = newTree;
return newTree;
} else {
return this.children[dir].insert(value);
}
}
}
find(value) {
let identifiedValue = this.identifier(value);
let thisValue = this.identifier(this.value);
if (thisValue === identifiedValue) {
return this.value;
} else {
let dir;
if (thisValue < identifiedValue) dir = RIGHT;
else dir = LEFT;
if (this.children[dir] === undefined) return undefined;
else return this.children[dir].find(value);
}
}
contains(value) {
return this.find(value) !== undefined;
}
_minimumChild() {
let current = this;
while (current.left !== undefined) {
current = current.left;
}
return current;
}
minimum() {
return this._minimumChild().value;
}
_maximumChild() {
let current = this;
while (current.right !== undefined) {
current = current.right;
}
return current;
}
maximum() {
return this._maximumChild().value;
}
remove(value) {
let identifiedValue = this.identifier(value);
let thisValue = this.identifier(this.value);
if (thisValue === identifiedValue) {
if (this.isLeaf) {
if (this.isRoot) {
this.value = undefined;
} else if (this.isRightChild) {
this.parent.right = undefined;
} else if (this.isLeftChild) {
this.parent.left = undefined;
}
} else if (this.hasOneChild) {
let rmDir = this.right ? LEFT : RIGHT;
this.right ? this.rotateLeft() : this.rotateRight();
this.children[rmDir] = undefined;
} else if (this.hasTwoChildren) {
let replacement = this.right._minimumChild();
this.value = replacement.value;
this.right.remove(replacement.value);
}
} else {
let dir;
if (thisValue < identifiedValue) dir = RIGHT;
else dir = LEFT;
if (this.children[dir] === undefined) return undefined;
else return this.children[dir].remove(value);
}
}
}
// Red-Black Tree
const BLACK = "b";
const RED = "r";
class RedBlackTree extends BinaryTree {
constructor(value, identifier=identity, color=BLACK) {
super(value, identifier);
this.color = color;
}
_swapWithParent() {
// need to create a new node to replace old one
let replacement = new RedBlackTree(this.value, this.identifier, this.color);
replacement.parent = this.parent;
replacement.children = this.children;
if (this.parent !== undefined) {
if (this.isRightChild) this.parent.right = replacement;
else this.parent.left = replacement;
}
this.value = replacement.parent.value;
this.children = replacement.parent.children;
this.parent = replacement.parent.parent;
this.color = replacement.parent.color;
// update references to this
this.children.forEach(child => {
if (child) child.parent = this;
});
// update references to replacement
this.children.forEach(child => {
if (child) child.children.forEach(kid => {
if (kid) kid.parent = child;
});
});
}
paintBlack() { this.color = BLACK; }
paintRed() { this.color = RED; }
get isBlack() { return this.color === BLACK; }
get isRed() { return this.color === RED; }
paint() { return this._insert1(); }
// node is the root of the tree, paint it black
_insert1() {
if (this.parent === undefined) {
this.paintBlack();
return;
} else this._insert2();
}
// parent is black, leave the node as is
_insert2() {
if (this.parent.isBlack) return;
else this._insert3();
}
// If the parent is red and the uncle is red,
// repaint them both black, and repaint the grandparent red.
// In this case, the grandparent might violate some of the rules,
// for example if its parent is red.
// Thus, repaint the grandparent as if it was being inserted.
_insert3() {
let uncle = this.uncle;
if (uncle ? uncle.isRed : false) {
this.parent.paintBlack();
uncle.paintBlack();
this.grandparent.paintRed();
this.grandparent.paint();
return;
} else this._insert4();
}
// If the parent is red and the uncle is black
// (must be true because the previous case was not true),
// rotate the inserted node up, so that it now sits atop the parent.
// This will still leave both of these nodes red,
// violating the rule that every red must have two black children.
// This case will always continue to case five,
// where that issue will be resolved.
_insert4() {
if (this.isRightChild && this.parent.isLeftChild) {
this.parent.rotateLeft();
return;
} else if (this.isLeftChild && this.parent.isRightChild) {
this.parent.rotateRight();
return;
}
this._insert5();
}
// This case has the same scenario as the previous case,
// but here paint the inserted node’s grandparent black, and its parent red.
// Then (because of the guarantee that this is the left child
// if the parent is a left or vice-versa for right from the previous case)
// rotate the parent up and the grandparent down.
_insert5() {
this.parent.paintBlack();
this.grandparent.paintRed();
if (this.isLeftChild) {
this.grandparent.rotateRight();
} else {
this.grandparent.rotateLeft();
}
return;
}
insert(value) {
if (this.value === undefined) {
this.value = value;
this.paintBlack();
return;
}
let dir;
if (this.identifier(value) > this.identifier(this.value)) {
dir = RIGHT;
} else dir = LEFT;
if (this.children[dir] !== undefined) {
return this.children[dir].insert(value);
} else {
let child = new RedBlackTree(value, this.identifier, RED);
child.parent = this;
let parent = child.parent;
this.children[dir] = child;
child.paint();
return child;
}
}
remove(value) {
let identifiedValue = this.identifier(value);
let thisValue = this.identifier(this.value);
if (thisValue === identifiedValue) {
this.rmPaint(value);
return;
} else {
let dir;
if (thisValue < identifiedValue) dir = RIGHT;
else dir = LEFT;
if (this.children[dir] === undefined) return undefined;
else return this.children[dir].remove(value);
}
}
standardRemove(value) {
if (this.isLeaf) {
if (this.isRoot) {
this.value = undefined;
this.paintBlack();
} else if (this.isRightChild) {
this.parent.right = undefined;
} else if (this.isLeftChild) {
this.parent.left = undefined;
}
} else if (this.hasOneChild) {
let rmDir = this.right ? LEFT : RIGHT;
this.right ? this.rotateLeft() : this.rotateRight();
this.children[rmDir] = undefined;
} else if (this.hasTwoChildren) {
let replica = this.right._minimumChild();
this.value = replica.value;
this.right.remove(replica.value);
}
}
rmPaint(value) {
if (!this.hasTwoChildren) this._remove0();
this.standardRemove(value);
}
// This case is only called once when starting to remove values,
// and is not included in any recursive calls.
// If the removed node is red, or the child is red,
// then paint the child red and remove the node
// because no rules will be violated when it is removed.
// All subsequent cases therefore are guaranteed that the removed node is black.
_remove0() {
let childIsRed = this.hasOneChild ? (this.right ? this.right.isRed : this.left.isRed) : false;
if (this.isBlack) {
if (childIsRed) {
this.right ? this.right.paintBlack() : this.left.paintBlack();
} else {
if (this.parent ? this.parent.isBlack : false) {
this._remove1();
}
}
}
}
// If the removed node is the root,
// remove the value and ensure that it is black.
_remove1() {
if (this.parent !== undefined) this._remove2();
}
// If the removed node’s sibling is red,
// paint the parent red and the sibling black.
// Then, rotate the parent down and the sibling up,
// such that parent is still above the removed node.
// Now, the path that the removed node is on will be short one black node,
// so this case always continue to case three.
_remove2() {
let sib = this.sibling;
if (sib && sib.isRed) {
this.parent.paintRed();
sib.paintBlack();
if (this.isLeftChild) this.parent.rotateLeft();
else if (this.isRightChild) this.parent.rotateRight();
}
this._remove3();
}
// If the removed node’s sibling is black,
// then repaint the sibling red.
// This has the effect of reducing the number of black nodes
// on paths through the sibling to be reduced by one.
// When the node to be removed is removed,
// this will balance both sides of the parent
// to have the same number of black nodes.
// This still has the issue of paths which don’t pass
// through the parent will have one greater black node.
// By recursively call painting on the parent, the issue is fixed.
_remove3() {
let sib = this.sibling;
let sibIsBlack = sib ? sib.isBlack : true;
let sibLeftBlack = sib ? (sib.left ? sib.left.isBlack : true) : true;
let sibRightBlack = sib ? (sib.right ? sib.right.isBlack : true) : true;
if (this.parent.isBlack && sib && sibIsBlack && sibLeftBlack && sibRightBlack) {
sib.paintRed();
this.parent._remove1();
} else this._remove4();
}
// If the removed node’s sibling is black and the parent is red,
// swap the sibling and the parent’s colors.
// This makes it such the black nodes on paths
// through the sibling will remain the same,
// but the number of black nodes on the path through the removed node
// will increase by one, and then decrease by one
// when the node is removed.
_remove4() {
let sib = this.sibling;
let sibIsBlack = sib ? sib.isBlack : true;
let sibLeftBlack = sib ? (sib.left ? sib.left.isBlack : true) : true;
let sibRightBlack = sib ? (sib.right ? sib.right.isBlack : true) : true;
if (this.parent.isRed && sib && sibIsBlack && sibLeftBlack && sibRightBlack) {
sib.paintRed();
this.parent.paintBlack();
} else this._remove5();
}
// If the removed node’s sibling is the right child, black,
// its left child is red, and the other is black
// (or vice-versa for directions), rotate the sibling right,
// and swap its color with the left child.
// This sets us up for sixth case, where the sibling is black,
// and its right child is red(if the sibling is a right child).
_remove5() {
let sib = this.sibling;
if (this.isLeftChild && (sib.right ? sib.right.isBlack : true) && (sib.left ? sib.left.isRed : false)) {
sib.paintRed();
sib.left.paintBlack();
sib.rotateRight();
} else if (this.isRightChild && (sib.left ? sib.left.isBlack : true) && sib.right ? sib.right.isRed : false) {
sib.paintRed();
sib.right.paintBlack();
sib.rotateLeft();
}
this._remove6();
}
// If the removed node’s sibling is the right child, black,
// its right child is red, rotate the parent left,
// and swap the sibling and the parent’s color.
// Then, paint the sibling(the new parent) black.
// That rotation added an extra black node to the path
// which the removed node was on, and retained the original color
// of the parent, ensuring all properties were retained.
_remove6() {
let sib = this.sibling;
if (sib) this.parent.isBlack ? sib.paintBlack() : sib.paintRed(); this.parent.paintBlack();
if (this.isLeftChild) {
sib.right.paintBlack();
this.parent.rotateLeft();
} else {
sib.left.paintBlack();
this.parent.rotateRight();
}
}
countBlackToRoot(count=0) {
if (this.parent === undefined) return count;
else {
return this.isBlack ? this.parent.countBlackToRoot(count+1) : this.parent.countBlackToRoot(count);
}
}
}
Idea: A trie (after the middle syllable of reTRIEval) (alse called prefix tree) is an ordered search tree used to store a dynamic set or associative array where the keys are usually strings. Unlike a binary search tree, no node in the tree stores the key associated with that node; instead, its position in the tree defines the key with which it is associated. All the descendants of a node have a common prefix of the string associated with that node, and the root is associated with the empty string. Keys tend to be associated with leaves, though some inner nodes may correspond to keys of interest.
// https://www.youtube.com/watch?v=AXjmTQ8LEoI
// https://www.youtube.com/watch?v=CX777rfuZtM
// Trie node
class TrieNode {
constructor(char = "") {
this.value = char;
this.children = {}; // children nodes
this.isEndWord = false; // whether the node completes a word
}
}
// Trie
class Trie {
constructor() {
this.rootNode = new TrieNode();
}
insert(word) {
var node = this.rootNode;
// iterate through word
for (var i = 0; i < word.length; i++) {
var currChar = word[i];
// map word's chars to a path in the tree
if (node.children[currChar]) {
node = node.children[currChar];
} else { // if no path exists, create one
var newNode = new TrieNode(currChar);
node.children[currChar] = newNode;
node = newNode;
}
}
// indicate that the last char of word completes a string
node.isEndWord = true;
}
find(word) {
var node = this.rootNode;
for (var i = 0; i < word.length; i++) {
var currChar = word[i];
if (node.children[currChar]) {
node = node.children[currChar];
} else {
return false;
}
}
return true;
}
remove(word) {
var node = this.rootNode;
// remove only unique suffixes of word
var suffixes = [];
// no part of word can be removed from trie
for (var i = 0; i < word.length; i++) {
var currChar = word[i];
if (node.children[currChar]) {
node = node.children[currChar];
suffixes.unshift(node);
if (i === word.length && Object.keys(node.children).length) {
return "Suffixes in trie depend on '" + word + "'";
}
}
}
// some parts of word can be removed from trie
for (var j = 1; j < suffixes.length; j++) {
var parent = suffixes[j];
var child = word[suffixes.length - j];
delete parent.children[child];
if (parent.isEndWord || Object.keys(parent.children).length) {
return "Some suffixes of '" + word + "' removed from trie";
}
}
// all parts of word can be removed from trie
delete this.rootNode.children[word[0]];
return "Removed '" + word + "'. No other '" + word[0] + "' words remain";
}
}
Idea: A hash table is a data structure that implements an associative array - a structure that can map keys to values. It uses a hash function to compute an index into an array of buckets, where the desired value can be found.
Ideally, the hash function will assign each key to a unique bucket, but most hash table designs use an imperfect hash function, which might cause collisions where the hash function generates the same index for more than one key. Such collisions must be resolved in some way (probing, chaining, etc).
Search, insertion and deletion is O(1) in average case and O(n) in worst case. Space complexity is O(n).
// https://www.youtube.com/watch?v=KyUTuwz_b7Q
// https://www.hackerearth.com/ru/practice/data-structures/hash-tables/basics-of-hash-tables/tutorial/
// https://gist.github.com/alexhawkins/f6329420f40e5cafa0a4
// Hashing is often done in two steps:
// hash = hashfunc(key)
// index = hash % array_size
// The hash is independent of the array size,
// and it is then reduced to an index
// (a number between 0 and array_size − 1)
// using the modulo operator (%).
// Hash Table (simple)
var HashTable = function(maxSize=101) {
this.maxSize = maxSize;
this.storage = new Array(maxSize);
// counts amount of buckets to decide if resizing is needed
this.counter = 0;
};
// Hashing function
HashTable.prototype.hashFunc = function(str, max) {
var index = 0; // hash index
for (var i = 0; i < str.length; i++) {
var char = str[i];
index = (index << 5) + char.charCodeAt(0);
index = (index & index) % max;
}
return index;
};
// insert data
HashTable.prototype.insert = function(key, value) {
var index = this.hashFunc(key, this.maxSize);
//retrieve the bucket at this index in storage, if one exists
// [ [[k,v], [k,v], [k,v]], [[k,v], [k,v]], [[k,v] ]]
var bucket = this.storage[index];
if (!bucket) {
var bucket = [];
this.storage[index] = bucket;
}
// iterate through bucket to see if there are any conflicts
// if there are any, override them
var override = false;
for (let i = 0; i < bucket.length; i++) {
var tuple = bucket[i];
if (tuple[0] === key) { // tuple[0] is key
tuple[1] = value; // tuple[1] is value
override = true;
}
}
if (!override) {
// create new tuple in the bucket
bucket.push([key, value]);
this.counter++;
// check if storage resizing is needed
if (this.counter > this.maxSize * 0.75) {
this.resize(this.maxSize * 2);
}
}
return this;
};
// remove data
HashTable.prototype.remove = function(key) {
var index = this.hashFunc(key, this.maxSize);
var bucket = this.storage[index];
if (!bucket) return null;
for (var i = 0; i < bucket.length; i++) {
var tuple = bucket[i];
// check if key is inside the bucket
if (tuple[0] === key) {
// if it is, remove this tuple
bucket.splice(i, 1);
this.counter--;
if (this.counter < this.maxSize * 0.25) {
this.resize(this.maxSize / 2);
}
return tuple[1];
}
}
};
// resize hash table if it's too big or too small
HashTable.prototype.resize = function(newSize) {
var oldStorage = this.storage;
this.maxSize = newSize;
this.storage = new Array(newSize);
this.counter = 0;
oldStorage.forEach(function(bucket) {
if (!bucket) return;
for (var i = 0; i < bucket.length; i++) {
var tuple = bucket[i];
this.insert(tuple[0], tuple[1]);
}
}.bind(this));
};
// retrieve a record from a table
HashTable.prototype.get = function(key) {
var index = this.hashFunc(key, this.maxSize);
var bucket = this.storage[index];
if (!bucket) return null;
for (var i = 0; i < bucket.length; i++) {
var tuple = bucket[i];
if (tuple[0] === key) return tuple[1];
}
return null;
};
HashTable.prototype.getAll = function() {
for (var i = 0; i < this.maxSize; i++) {
if (this.storage[i]) {
this.storage[i].forEach(function(element) {
console.log(element[0], element[1]);
});
}
}
}
Idea: A graph is a non-linear abstract data structure that consists of a set of vertices (nodes) and a set of edges (lines) which connect the pairs of vertices. Edges may have direction and weight.
// https://www.youtube.com/watch?v=gXgEDyodOJU
// https://www.youtube.com/watch?v=bIA8HEEUxZI
// Graph (adjacency list representation)
function Graph() {
this.vertices = [];
this.edges = [];
this.numberOfEdges = 0;
}
Graph.prototype.addVertex = function(vertex) {
this.vertices.push(vertex);
this.edges[vertex] = [];
};
Graph.prototype.removeVertex = function(vertex) {
var index = this.vertices.indexOf(vertex);
if (~index) { // if index != -1 (because ~n == -(n+1), ~-1 == 0)
// remove 1 vertex
this.vertices.splice(index, 1);
}
// remove edges
while (this.edges[vertex].length) {
var adjacentVertex = this.edges[vertex].pop();
this.removeEdge(adjacentVertex, vertex);
}
};
Graph.prototype.addEdge = function(vertex1, vertex2) {
this.edges[vertex1].push(vertex2);
this.edges[vertex2].push(vertex1);
this.numberOfEdges++;
};
Graph.prototype.removeEdge = function(vertex1, vertex2) {
var index1 = this.edges[vertex1] ? this.edges[vertex1].indexOf(vertex2) : -1;
var index2 = this.edges[vertex2] ? this.edges[vertex2].indexOf(vertex1) : -1;
if (~index1) {
this.edges[vertex1].splice(index1, 1);
this.numberOfEdges--;
}
if (~index2) {
this.edges[vertex2].splice(index2, 1);
}
};
Graph.prototype.size = function() {
return this.vertices.length;
};
Graph.prototype.relations = function() {
return this.numberOfEdges;
};
// depth-first traversal
Graph.prototype.traverseDFS = function(vertex, func) {
if (!~this.vertices.indexOf(vertex)) { // if index == -1
return console.log("Vertex not found");
}
var visited = [];
this._traverseDFS(vertex, visited, func);
};
Graph.prototype._traverseDFS = function(vertex, visited, func) {
visited[vertex] = true;
if (this.edges[vertex] !== undefined) {
func(vertex);
}
for (var i = 0; i < this.edges[vertex].length; i++) {
if (!visited[this.edges[vertex][i]]) { // if vertex not visited
this._traverseDFS(this.edges[vertex][i], visited, func);
}
}
};
// breadth-first traversal
Graph.prototype.traverseBFS = function(vertex, func) {
if (!~this.vertices.indexOf(vertex)) {
return console.log("Vertex not found");
}
var queue = [];
queue.push(vertex);
var visited = [];
visited[vertex] = true;
while (queue.length) {
vertex = queue.shift();
func(vertex);
for (var i = 0; i < this.edges[vertex].length; i++) {
if (!visited[this.edges[vertex][i]]) {
visited[this.edges[vertex][i]] = true;
queue.push(this.edges[vertex][i]);
}
}
}
};
Graph.prototype.findPath = function(vertexFrom, vertexTo) {
if (!~this.vertices.indexOf(vertexFrom)) {
return console.log("Vertex not found");
}
var queue = [];
queue.push(vertexFrom);
var visited = [];
visited[vertexFrom] = true;
var paths = [];
while (queue.length) {
var vertex = queue.shift();
for (var i = 0; i < this.edges[vertex].length; i++) {
if (!visited[this.edges[vertex][i]]) {
visited[this.edges[vertex][i]] = true;
queue.push(this.edges[vertex][i]);
// save paths between vertices
paths[this.edges[vertex][i]] = vertex;
}
}
}
if (!visited[vertexTo]) return undefined;
var path = [];
for (var j = vertexTo; j !== vertexFrom; j = paths[j]) {
path.push(j);
}
path.push(j);
return path.reverse().join("-");
};
Graph.prototype.print = function() {
console.log(this.vertices.map(function(vertex) {
return (vertex + " -> " + this.edges[vertex].join(", ")).trim();
}, this).join(" | "));
};
Idea: A blockchain is a continuously growing list of records, called blocks, which are linked and secured using cryptography. Each block contains a cryptographic hash of the previous block, a timestamp and transaction data.
By design, a blockchain is resistant to modification of the data. It is an open, decentralized and distributed ledger typically managed by a peer-to-peer network collectively. Once recorded, the data in any given block cannot be altered retroactively without alteration of all subsequent blocks, which requires consensus of the network majority.
// https://www.youtube.com/watch?v=SSo_EIwHSd4
// https://www.youtube.com/watch?v=zVqczFZr124
// https://www.youtube.com/watch?v=HneatE69814
// Blockchain implementation (with Proof-of-Work)
// import SHA256 crypto function
// (available after installing crypto-js via npm)
const SHA256 = require("crypto-js/sha256.js");
class Block {
constructor(timestamp, data, prevHash = "") {
this.timestamp = timestamp;
this.data = data;
this.prevHash = prevHash;
this.hash = this.calculateHash();
// number which has nothing to do with a block
// but is changed while mining block to a given difficulty
// (calculating hash with certain amount of 0s)
// as we can't change timestamp, data, prevHash
this.nonce = 0;
}
calculateHash() {
return SHA256(this.timestamp + JSON.stringify(this.data) + this.prevHash + this.nonce).toString();
}
mineBlock(difficulty) {
// while amount of 0s in hash != to difficulty (proof of work)
while (this.hash.substring(0, difficulty) !== new Array(difficulty+1).join("0")) {
this.nonce++;
this.hash = this.calculateHash();
}
console.log("Block mined: " + this.hash);
}
}
class Blockchain {
constructor() {
this.chain = [this.createGenesisBlock()];
this.difficulty = 4; // amount of 0s in hash - proof of work
}
createGenesisBlock() { // 1st block in the blockchain
return new Block("01/01/2017", "Genesis Block", "0");
}
getLatestBlock() {
return this.chain[this.chain.length-1];
}
addBlock(newBlock) {
newBlock.prevHash = this.getLatestBlock().hash;
newBlock.mineBlock(this.difficulty);
this.chain.push(newBlock);
}
isChainValid() {
for (var i = 1; i < this.chain.length; i++) {
const currentBlock = this.chain[i];
const prevBlock = this.chain[i-1];
if (currentBlock.hash !== currentBlock.calculateHash()) {
return false;
}
if (currentBlock.prevHash !== prevBlock.hash) {
return false;
}
return true;
}
}
}