// Cloned by Tristan Everitt on 27 Sep 2022 from World "Binary tree" by "Coding Train" project
// Please leave this clone trail here.
//The range of numbers is 3 * 10^y where y is a random value from [1, 2, 3, 5, 8].
// If the tree is small enough it'll draw it with only the path to the result.
// During testing, I can only run up to y=7 on my browser. y=8 crashes the browser/tab
// Modified port of "01_binary_tree_viz" from AI course by Daniel Shiffman
// https://github.com/nature-of-code/NOC-S17-2-Intelligence-Learning/tree/master/week1-graphs
// Daniel Shiffman
// Nature of Code: Intelligence and Learning
// https://github.com/shiffman/NOC-S17-2-Intelligence-Learning
// canvas size
const cw = 900;
const ch = 1024;
const root_x = cw / 2;
const root_y = ch / 10;
const ellipse_size = cw / 25;
// range of numbers
const y = [1, 2, 3, 5, 8];
const randomY = y[Math.floor(Math.random() * y.length)];
const MAX = 3 * Math.pow(10, randomY);
// how many nodes
const NONODES = MAX / 2;
const SHOW_MAX_LEVELS = 10;
// console log how we build the tree or not
const SHOWBUILD = false;
// Binary tree
let tree;
function setup() {
createCanvas(cw, ch);
//$.getScript ( "/uploads/tristan/node.js", function() {
// console.log ("Got node");
//$.getScript ( "/uploads/tristan/tree.js", function() {
// console.log ("Got tree");
// New tree
tree = new Tree();
console.log("=== build tree =================");
let randomIndex = AB.randomIntAtoB(0, NONODES - 1);
let x = null;
let startBuild = new Date();
// Add random values
for (let i = 0; i < NONODES; i++) {
let n = floor(random(0, MAX));
// console.log ("adding node: " + n);
if (randomIndex === i) {
// Search the tree for random number
x = n;
}
tree.addValue(n);
}
let buildTreeRuntime = new Date() - startBuild;
x = AB.randomPick3(x, x, floor(random(0, MAX)));
background("lightgreen");
// Traverse the tree
// tree.traverse();
let msg = "";
msg += "Range of numbers: " + MAX + "<br/>";
console.log("Range of numbers: " + MAX);
msg += "Number of nodes: " + NONODES + "<br/>";
console.log("Number of nodes: " + NONODES);
msg += "Render max level: " + SHOW_MAX_LEVELS + "<br/>";
console.log("Render max level: " + SHOW_MAX_LEVELS);
msg += "Search tree for " + x + "<br/>";
console.log("Search tree for " + x);
let start = new Date();
let result = tree.search(x);
let runtime = new Date() - start;
msg += "--------------<br/>";
console.log("--------------=");
msg += "Build tree runtime: " + buildTreeRuntime + "<br/>";
console.log("Build tree runtime: " + buildTreeRuntime);
msg += "--------------<br/>";
console.log("--------------");
if (result === null) {
msg += x + " not found.";
console.log(x + " not found.");
} else {
msg += x + " found at level " + result.level + " within " + runtime + " milliseconds";
console.log(x + " found at level " + result.level + " within " + runtime + " milliseconds");
}
AB.msg(msg);
//})});
}
function paint(node) {
if (node.level > SHOW_MAX_LEVELS) {
return
}
// console.log('Paint ' + node.value);
stroke("grey");
// Draw a circle
stroke("black");
fill("black");
// console.log ("drawing node " + this.value );
ellipse(node.x, node.y, ellipse_size * 1.5, ellipse_size * 1.5);
// Display the value
fill(node.subject ? "red" : "white");
textAlign(CENTER);
textSize(14);
let v = node.value + " [L:" + node.level + "]";
text(v, node.x, node.y + (ellipse_size / 6));
if (node.parent !== null) {
line(node.parent.x, node.parent.y, node.x, node.y);
paint(node.parent);
}
}
// Adapted from:
// Daniel Shiffman
// Nature of Code: Intelligence and Learning
// https://github.com/shiffman/NOC-S17-2-Intelligence-Learning
// Tree object
function Tree() {
// Just store the root
this.root = null;
}
// Start by searching the root
Tree.prototype.search = function (val) {
// console.log ("Tree.search: start at " + this.root.value );
return this.root.search(val);
}
// Add a new value to the tree
Tree.prototype.addValue = function (val) {
let n = new Node(val);
if (this.root === null) {
if (SHOWBUILD) console.log("root = " + n.value);
this.root = n;
this.root.level = 0;
this.root.parent = null;
// An initial position for the root node
this.root.x = root_x;
this.root.y = root_y;
} else {
this.root.addNode(n);
}
}
// Adapted from:
// Daniel Shiffman
// Nature of Code: Intelligence and Learning
// https://github.com/shiffman/NOC-S17-2-Intelligence-Learning
// Node in the tree
function Node(val, x, y) {
this.value = val;
this.left = null;
this.right = null;
// How far apart should the children nodes be
// This will be based on "level" in the tree
this.distance = 2;
this.x = x;
this.y = y;
this.subject = false;
this.level = 0;
this.parent = null;
this.notes = null;
}
// Search the tree for a value
Node.prototype.search = function (val) {
// console.log ("current " + this.value );
if (val === this.value) {
this.subject = true;
paint(this);
return this;
}
if (val < this.value) {
return this.left !== null ? this.left.search(val) : null;
}
if (val > this.value)
return this.right !== null ? this.right.search(val) : null;
}
// Add a new Node
Node.prototype.addNode = function (n) {
if (n.value === this.value) return;
n.parent = this;
n.level = this.level + 1;
if (SHOWBUILD) console.log("adding node " + n.value + " to current node " + this.value);
if (n.value < this.value) {
if (this.left === null) {
if (SHOWBUILD) console.log("put it here on left");
this.left = n;
// Exponentially shrink the distance between nodes for each level
// minus 1/4 of the width
// minus 1/8 of the width
// ....
this.left.x = this.x - (cw / pow(2, n.distance));
this.left.y = this.y + (ch / 10);
} else {
if (SHOWBUILD) console.log("go left");
n.distance++; // change node.distance at each level
this.left.addNode(n) // recusively keep going
}
} else if (n.value > this.value) {
if (this.right === null) {
if (SHOWBUILD) console.log("put it here on right");
this.right = n;
this.right.x = this.x + (cw / pow(2, n.distance));
this.right.y = this.y + (ch / 10);
} else {
if (SHOWBUILD) console.log("go right");
n.distance++;
this.right.addNode(n);
}
}
};