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:

1
let tree
2

3
function setup() {
4
  noCanvas()
5

6
  tree = new Tree()
7

8
  tree.add(5)
9
  tree.add(12)
10
  tree.add(4)
11
  tree.add(1)
12

13
  console.log(tree)
14
}
15

16
class Tree {
17
  constructor() {
18
    this.root = null
19
  }
20

21
  add(val) {
22
    const node = new Node(val)
23

24
    // if tree is null assign current node as root
25
    if (this.root === null) {
26
      this.root = node
27
    } else {
28
      // otherwise append node to existing node
29
      this.root.add(node)
30
    }
31
  }
32
}
33

34
class Node {
35
  constructor(val) {
36
    this.value = val
37
    this.left = null
38
    this.right = null
39
  }
40

41
  add(node) {
42
    // check the value is less than the current node
43
    if (node.value < this.value) {
44
      // if the left node is null then assign
45
      if (this.left === null) this.left = node
46
      // otherwise we call the add function on the existing node
47
      else this.left.add(node)
48
    } else if (node.value > this.value) {
49
      // do the same for he right as we did for the left
50
      if (this.right === null) this.right = node
51
      else this.right.add(node)
52
    }
53
  }
54
}

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:

1
visit() {
2
  if (this.left !== null) {
3
    this.left.visit()
4
  }
5

6
  console.log(this.value)
7

8
  if (this.right !== null) {
9
    this.right.visit()
10
  }
11
}

We can then add a function called traverse on the tree which will just call the visit function on the root node:

1
traverse(){
2
  if (this.root !== null) {
3
    this.root.visit()
4
  }
5
}

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:

1
search(val) {
2
  // if the current node is the one we're looking for then return
3
  if (this.value === val){
4
    return this
5

6
  // else check the left node if smaller than current
7
  } else if (this.left !== null && this.value > val) {
8
    return this.left.search(val)
9

10
  // else check the right node
11
  } else if (this.right !== null && this.value < val) {
12
    return this.right.search(val)
13
  } else {
14
    return null
15
  }
16
}

And then the search function on the tree as a proxy:

1
search(val) {
2
  if (this.root !== null) {
3
    return this.root.search(val)
4
  }
5
}

Visualize Tree

We can visualize the tree (poorly) using something like the following:

1
let tree
2

3
function setup() {
4
  createCanvas(700, 450)
5
  background(50)
6

7
  tree = new Tree()
8

9
  for (let i = 0; i < 20; i++) {
10
    tree.add(Math.floor(random(-100, 100)))
11
  }
12

13
  tree.traverse()
14
}
15

16
class Tree {
17
  constructor() {
18
    this.root = null
19
  }
20

21
  add(val) {
22
    const node = new Node(val)
23

24
    // if tree is null assign current node as root
25
    if (this.root === null) {
26
      this.root = node
27
      this.root.x = width / 2
28
      this.root.y = 24
29
    } else {
30
      // otherwise append node to existing node
31
      this.root.add(node)
32
    }
33
  }
34

35
  traverse() {
36
    if (this.root !== null) {
37
      this.root.visit(this.root)
38
    }
39
  }
40

41
  search(val) {
42
    if (this.root !== null) {
43
      return this.root.search(val)
44
    }
45
  }
46
}
47

48
class Node {
49
  constructor(val) {
50
    this.value = val
51
    this.left = null
52
    this.right = null
53
  }
54

55
  add(node) {
56
    // check the value is less than the current node
57
    if (node.value < this.value) {
58
      // if the left node is null then assign
59
      if (this.left === null) {
60
        this.left = node
61
        this.left.x = this.x - 35 + random(1, 20)
62
        this.left.y = this.y + 35 + random(1, 20)
63
      }
64
      // otherwise we call the add function on the existing node
65
      else this.left.add(node)
66
    } else if (node.value > this.value) {
67
      // do the same for the right as we did for the left
68
      if (this.right === null) {
69
        this.right = node
70
        this.right.x = this.x + 35 + random(1, 20)
71
        this.right.y = this.y + 35 + random(1, 20)
72
      } else this.right.add(node)
73
    }
74
  }
75

76
  visit(parent) {
77
    stroke('red')
78
    strokeWeight(1)
79
    line(parent.x, parent.y, this.x, this.y)
80

81
    strokeWeight(0)
82

83
    ellipse(this.x, this.y, 25)
84

85
    textAlign('CENTER')
86
    text(this.value, this.x - 6, this.y + 5)
87

88
    if (this.left !== null) {
89
      this.left.visit(this)
90
    }
91

92
    console.log(this.value)
93

94
    if (this.right !== null) {
95
      this.right.visit(this)
96
    }
97
  }
98

99
  search(val) {
100
    // if the current node is the one we're looking for then return
101
    if (this.value === val) {
102
      return this
103

104
      // else check the left node if smaller than current
105
    } else if (this.left !== null && this.value > val) {
106
      return this.left.search(val)
107

108
      // else check the right node
109
    } else if (this.right !== null && this.value < val) {
110
      return this.right.search(val)
111
    } else {
112
      return null
113
    }
114
  }
115
}

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