Updated: 03 September 2023
Notes from The Coding Train YouTube Channel
Intelligence and Learning
From the Intelligence and Learning Series
Algorithms and Graphs
A Graph system is made up of two systems:
- Nodes
- Edges
Binary Search Tree
A Binary Tree is a data structure that makes use of a node-based structure in which each node has only two connections in which the data is sorted in some way
When visiting nodes we do the following:
- Go to the left as far as possible
- Take node
- Go up one
- Go to the right node, if can’t go to anohter new node take node
- Start from 1 again
Doing this will result in us retrieving a sorted node list
Searching through a structure like this is much faster than searching a single linear array for an element due to the rules by which the tree is sorted
Define Tree and Nodes
We can program a Binary Tree structure which makes use of the add
function on a Node
or the Tree
to add a new node to the tree, while recursively finding the correct place in the tree to add the node:
let tree
function setup() {
noCanvas()
tree = new Tree()
tree.add(5)
tree.add(12)
tree.add(4)
tree.add(1)
console.log(tree)
}
class Tree {
constructor() {
this.root = null
}
add(val) {
const node = new Node(val)
// if tree is null assign current node as root
if (this.root === null) {
this.root = node
} else {
// otherwise append node to existing node
this.root.add(node)
}
}
}
class Node {
constructor(val) {
this.value = val
this.left = null
this.right = null
}
add(node) {
// check the value is less than the current node
if (node.value < this.value) {
// if the left node is null then assign
if (this.left === null) this.left = node
// otherwise we call the add function on the existing node
else this.left.add(node)
} else if (node.value > this.value) {
// do the same for he right as we did for the left
if (this.right === null) this.right = node
else this.right.add(node)
}
}
}
Traverse Tree
We can also create a function that allows us to retrieve all the values from the different nodes defined on the Node
which will again recursively visit all children on the Node:
visit() {
if (this.left !== null) {
this.left.visit()
}
console.log(this.value)
if (this.right !== null) {
this.right.visit()
}
}
We can then add a function called traverse
on the tree which will just call the visit
function on the root node:
traverse(){
if (this.root !== null) {
this.root.visit()
}
}
Search Tree
Next, we can define a function search
on the node which allows us to search a node as well as its children for a specific value as well as print out the current node when found:
search(val) {
// if the current node is the one we're looking for then return
if (this.value === val){
return this
// else check the left node if smaller than current
} else if (this.left !== null && this.value > val) {
return this.left.search(val)
// else check the right node
} else if (this.right !== null && this.value < val) {
return this.right.search(val)
} else {
return null
}
}
And then the search function on the tree as a proxy:
search(val) {
if (this.root !== null) {
return this.root.search(val)
}
}
Visualize Tree
We can visualize the tree (poorly) using something like the following:
let tree
function setup() {
createCanvas(700, 450)
background(50)
tree = new Tree()
for (let i = 0; i < 20; i++) {
tree.add(Math.floor(random(-100, 100)))
}
tree.traverse()
}
class Tree {
constructor() {
this.root = null
}
add(val) {
const node = new Node(val)
// if tree is null assign current node as root
if (this.root === null) {
this.root = node
this.root.x = width / 2
this.root.y = 24
} else {
// otherwise append node to existing node
this.root.add(node)
}
}
traverse() {
if (this.root !== null) {
this.root.visit(this.root)
}
}
search(val) {
if (this.root !== null) {
return this.root.search(val)
}
}
}
class Node {
constructor(val) {
this.value = val
this.left = null
this.right = null
}
add(node) {
// check the value is less than the current node
if (node.value < this.value) {
// if the left node is null then assign
if (this.left === null) {
this.left = node
this.left.x = this.x - 35 + random(1, 20)
this.left.y = this.y + 35 + random(1, 20)
}
// otherwise we call the add function on the existing node
else this.left.add(node)
} else if (node.value > this.value) {
// do the same for the right as we did for the left
if (this.right === null) {
this.right = node
this.right.x = this.x + 35 + random(1, 20)
this.right.y = this.y + 35 + random(1, 20)
} else this.right.add(node)
}
}
visit(parent) {
stroke('red')
strokeWeight(1)
line(parent.x, parent.y, this.x, this.y)
strokeWeight(0)
ellipse(this.x, this.y, 25)
textAlign('CENTER')
text(this.value, this.x - 6, this.y + 5)
if (this.left !== null) {
this.left.visit(this)
}
console.log(this.value)
if (this.right !== null) {
this.right.visit(this)
}
}
search(val) {
// if the current node is the one we're looking for then return
if (this.value === val) {
return this
// else check the left node if smaller than current
} else if (this.left !== null && this.value > val) {
return this.left.search(val)
// else check the right node
} else if (this.right !== null && this.value < val) {
return this.right.search(val)
} else {
return null
}
}
}
Breadth-First Search
This is a search algorithm for looking at the nearest node from the start node first and helps us traverse a tree in order to find the shortest number of steps to a specific node