Week 02 → Day 008 → Wednesday → August 16, 2017
Index
Code Challenge #7 forLoopTimeout.js
Code Challenge #6 waterJugs.md Review
Solution Lecture ⋰
Sprint Review
Lecture ⋰ Trees ⋰ BST ⋰ Graphs ⋰ Directed Graph ⋰ Weighted Graphs
Feedback Docs
Mini Sprint Review
Resources
BST Visualizer – https://www.cs.usfca.edu/~galles/visualization/BST.html
Graph Visualizer – http://www.webgraphviz.com/
Graph Data Structure – http://blog.benoitvallon.com/data-structures-in-javascript/the-graph-data-structure/
Binary Search Tree in JavaScript – https://www.nczonline.net/blog/2009/06/09/computer-science-in-javascript-binary-search-tree-part-1/
Data Structures in JavaScript – https://code.tutsplus.com/series/data-structures-in-javascript--cms-772
Data Structures in JavaScript – https://blog.syncano.io/data-structures-in-javascript/
Tree
Tree represents the nodes connected by edges. We will discuss binary tree or binary search tree specifically.
const tree = {
value: 5,
children: [
{
value: 10,
children: []
},
{
value: 12,
children: []
},
{
value: 2,
children: []
}
]
}
Binary Search Tree – O(log N)
Binary search time complexity
╔═══════════╦══════════╦════════════╗
║ Algorithm ║ Average ║ Worst Case ║
╠═══════════╬══════════╬════════════╣
║ Space ║ O(n) ║ O(n) ║
║ Search ║ O(log n) ║ O(n) ║
║ Insert ║ O(log n) ║ O(n) ║
║ Delete ║ O(log n) ║ O(n) ║
╚═══════════╩══════════╩════════════╝
A tree is a data structure composed of nodes It has the following characteristics:
- Each tree has a root node (at the top).
- The root node has zero or more child nodes.
- Each child node has zero or more child nodes, and so on.
A_binarysearch_tree adds these two characteristics:
- Each node has up to two children.
- For each node, its left descendents are less than the current node, which is less than the right descendents.
Binary search trees keep their keys in sorted order, so that lookup and other operations can use the principle of binary search time proportional to: when looking for a key in a tree (or a place to insert a new key), they traverse the tree from root to leaf, making comparisons to keys stored in the nodes of the tree and deciding, based on the comparison, to continue searching in the left or right subtrees. On average, this means that each comparison allows the operations to skip about half of the tree, so that each lookup, insertion or deletion takes logarithm linear time the hash tables of the number of items stored in the tree. This is much better than the required to find items by key in an (unsorted) array, but slower than the corresponding operations on .
Binary Search Trees have a non-linear insertion algorithm. A binary search tree is similar to a doubly linked list in that each node contains some data as well as two pointers to other nodes; they differ in the way that those nodes relate to one another. A binary search tree node’s pointers are typically called “left” and “right” to indicate subtrees of values relating to the current value. A simple JavaScript implementation of such a node is as follows:
var node = {
value: 5,
left: {
value: 2,
left: {
value: 1,
left: null,
right: null
},
right: {
value: 7,
left: null,
right: {
value: 8,
left: null,
right: null
}
}
},
right: {
value: 9,
left: null,
right: null
}
};
As can be discerned from the name, a binary search tree is organized into a hierarchical tree structure. The first item becomes the root node and each additional value is added into the tree as an ancestor of that root. The unique part of a binary search tree, however, is that the nodes are ordered based on the value they contain: any values that are part of a node’s left subtree are always less than the node’s value and any values in the right subtree are always greater than the node’s value. In this way, finding a value in a binary search tree becomes quite simple, go left whenever the value you’re looking for is less than the node you’re processing or go right if the value is greater. There can be no duplicates in a binary search tree because duplicates would destroy this relationship. The following diagram represents a simple binary search tree.
This diagram represents a binary search tree whose root value is 8. When the value 3 was added, it became the left child of the root because 3 is less than 8. When the value 1 was added, it became the left child of 3 because 1 is less than 8 (so go left) and then 1 is less than 3 (go left again). When the value 10 was added, it became the right child of the root because 10 is greater than 8. This process continued with the values 6, 4, 7, 14, and 13. This binary search tree has a depth of 3, meaning that the farthest values from the root are three nodes away.
To build a binary search tree implementation in JavaScript, the first step is to define the basic interface:
function BinarySearchTree() {
this._root = null;
}
BinarySearchTree.prototype = {
//restore constructor
constructor: BinarySearchTree,
add: function (value){
},
contains: function(value){
},
remove: function(value){
},
size: function(){
},
toArray: function(){
},
toString: function(){
}
};
The basic interface is similar to other data structures, with methods for adding and removing values. I’ve also added a few convenience methods, size(), toArray(), andtoString(), that are useful for JavaScript.
To get a handle on using a binary search tree, the best method to begin with is contains(). The contains() method accepts a value as an argument and returns true if the value is present in the tree or false if not. This method follows the basic binary search algorithm to determine whether or not the value is present:
BinarySearchTree.prototype = {
//more code
contains: function(value){
var found = false,
current = this._root
//make sure there's a node to search
while(!found && current){
//if the value is less than the current node's, go left
if (value < current.value){
current = current.left;
//if the value is greater than the current node's, go right
} else if (value > current.value){
current = current.right;
//values are equal, found it!
} else {
found = true;
}
}
//only proceed if the node was found
return found;
},
//more code
};
The search starts from the root of the tree. Since there may not be a root if no data has been added, this must be checked. Traversing the tree follows the simple algorithm discussed earlier: go left if the value to find is less than the current node, go right if the value is greater. The current pointer is overwritten each time through until either the value is found (in which case found is set to true) or there are no more nodes to search in that direction (in which case the value isn’t in the tree).
The approach using in contains() can also be used to insert a new value into the tree. The primary difference is that you’ll be looking for the spot in which to place the new value instead of looking for the value in the tree:
BinarySearchTree.prototype = {
//more code
add: function(value){
//create a new item object, place data in
var node = {
value: value,
left: null,
right: null
},
//used to traverse the structure
current;
//special case: no items in the tree yet
if (this._root === null){
this._root = node;
} else {
current = this._root;
while(true){
//if the new value is less than this node's value, go left
if (value < current.value){
//if there's no left, then the new node belongs there
if (current.left === null){
current.left = node;
break;
} else {
current = current.left;
}
//if the new value is greater than this node's value, go right
} else if (value > current.value){
//if there's no right, then the new node belongs there
if (current.right === null){
current.right = node;
break;
} else {
current = current.right;
}
//if the new value is equal to the current one, just ignore
} else {
break;
}
}
}
},
//more code
};
Graph
Adjacency list (graph) time complexity
╔═══════════════╦════════════╗
║ Algorithm ║ Time ║
╠═══════════════╬════════════╣
║ Storage ║ O(|V|+|E|) ║
║ Add Vertex ║ O(1) ║
║ Add Edge ║ O(1) ║
║ Remove Vertex ║ O(|V|+|E|) ║
║ Remove Edge ║ O(|E|) ║
║ Query ║ O(|V|) ║
╚═══════════════╩════════════╝
A Graph data structure consists of a finite (and possibly mutable) set of vertices or nodes or points, together with a set of unordered pairs of these vertices for an undirected Graph or a set of ordered pairs for a directed Graph. These pairs are known as edges, arcs, or lines for an undirected Graph and as arrows, directed edges, directed arcs, or directed lines for a directed Graph. The vertices may be part of the Graph structure, or may be external entities represented by integer indices or references.
A Graph data structure may also associate to each edge some edge value, such as a symbolic label or a numeric attribute (cost, capacity, length, etc.).
Following two are the most commonly used representations of graph.
- Adjacency Matrix
- Adjacency List
Adjacency Matrix
Data are stored in a two-dimensional matrix, in which the rows represent source vertices and columns represent destination vertices. The data on the edges and vertices must be stored externally.
Adjacency Matrix representation of the above graph.
Adjacency List
For every vertex a list of adjacent vertices is stored. This can be viewed as storing the list of edges. This data structure allows the storage of additional data on the vertices and edges.
Sample Graph & JavaScript Code that uses 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) {
this.vertices.splice(index, 1);
}
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;
};
Graph.prototype.traverseDFS = function(vertex, fn) {
if(!~this.vertices.indexOf(vertex)) {
return console.log('Vertex not found');
}
var visited = [];
this._traverseDFS(vertex, visited, fn);
};
Graph.prototype._traverseDFS = function(vertex, visited, fn) {
visited[vertex] = true;
if(this.edges[vertex] !== undefined) {
fn(vertex);
}
for(var i = 0; i < this.edges[vertex].length; i++) {
if(!visited[this.edges[vertex][i]]) {
this._traverseDFS(this.edges[vertex][i], visited, fn);
}
}
};
Graph.prototype.traverseBFS = function(vertex, fn) {
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();
fn(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.pathFromTo = function(vertexSource, vertexDestination) {
if(!~this.vertices.indexOf(vertexSource)) {
return console.log('Vertex not found');
}
var queue = [];
queue.push(vertexSource);
var visited = [];
visited[vertexSource] = 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[vertexDestination]) {
return undefined;
}
var path = [];
for(var j = vertexDestination; j != vertexSource; 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(' | '));
};
var graph = new Graph();
graph.addVertex(1);
graph.addVertex(2);
graph.addVertex(3);
graph.addVertex(4);
graph.addVertex(5);
graph.addVertex(6);
graph.print(); // 1 -> | 2 -> | 3 -> | 4 -> | 5 -> | 6 ->
graph.addEdge(1, 2);
graph.addEdge(1, 5);
graph.addEdge(2, 3);
graph.addEdge(2, 5);
graph.addEdge(3, 4);
graph.addEdge(4, 5);
graph.addEdge(4, 6);
graph.print(); // 1 -> 2, 5 | 2 -> 1, 3, 5 | 3 -> 2, 4 | 4 -> 3, 5, 6 | 5 -> 1, 2, 4 | 6 -> 4
console.log('graph size (number of vertices):', graph.size()); // => 6
console.log('graph relations (number of edges):', graph.relations()); // => 7
graph.traverseDFS(1, function(vertex) { console.log(vertex); }); // => 1 2 3 4 5 6
console.log('---');
graph.traverseBFS(1, function(vertex) { console.log(vertex); }); // => 1 2 5 3 4 6
graph.traverseDFS(0, function(vertex) { console.log(vertex); }); // => 'Vertex not found'
graph.traverseBFS(0, function(vertex) { console.log(vertex); }); // => 'Vertex not found'
console.log('path from 6 to 1:', graph.pathFromTo(6, 1)); // => 6-4-5-1
console.log('path from 3 to 5:', graph.pathFromTo(3, 5)); // => 3-2-5
graph.removeEdge(1, 2);
graph.removeEdge(4, 5);
graph.removeEdge(10, 11);
console.log('graph relations (number of edges):', graph.relations()); // => 5
console.log('path from 6 to 1:', graph.pathFromTo(6, 1)); // => 6-4-3-2-5-1
graph.addEdge(1, 2);
graph.addEdge(4, 5);
console.log('graph relations (number of edges):', graph.relations()); // => 7
console.log('path from 6 to 1:', graph.pathFromTo(6, 1)); // => 6-4-5-1
graph.removeVertex(5);
console.log('graph size (number of vertices):', graph.size()); // => 5
console.log('graph relations (number of edges):', graph.relations()); // => 4
console.log('path from 6 to 1:', graph.pathFromTo(6, 1)); // => 6-4-3-2-1