💾 Archived View for gemini.robrohan.com › 2021-05-02-binary-tree.md captured on 2022-07-16 at 15:56:58. Gemini links have been rewritten to link to archived content
⬅️ Previous capture (2022-04-28)
-=-=-=-=-=-=-
---
author: Rob Rohan
title: Fun with Binary Trees
date: 2021-04-30 13:25:00+00:00
slug: binary-tree
tags: [kale, maths]
---
This is another contrived post to test out my interactive coding scripts,
and also to test making a d3 tree graph. While this post is probably not
going to be enlightening, I hope it is somewhat entertaining.
One of my favorite data structures is the binary tree. It's not the fastest
at everything, but it does most things you'd need, and it does them
reasonably quickly.
If you have a list of things that you need to sort, search, and also insert
new items into, a binary tree is not a bad thing to consider. While it's
searching is nowhere near as fast as, say, a
[hash table](https://en.wikipedia.org/wiki/Hash_table) and it's sorting isn't
as fast as [timsort](https://en.wikipedia.org/wiki/Timsort) - it's versatility
and simplicity make it one of my goto structures.
Adding one item to a binary search tree is on average an \\(O(\log n)\\)
process. Adding n items is an \\(O(n \log n)\\) process, making tree sorting
a 'fast sort' process. ([Wikipeda][1])
(This of course depends of if it is balanced or unbalanced. And, as I am
sure you already know, [Big Oh][2] (Lower is better) is just a way to
measure how fast an algorithm will "blow out" as you throw more stuff at it)
Instead of me describing a tree in English, let's just build one. Don't
forget to click the play button on each section.
---
The core of a tree is a node. In a binary tree each node has two children -
generally called _left_ and _right_. Here I am instead making an array
called _children_ with 2 elements because, later, it'll make using d3
easier.
await K.Include("https://d3js.org/d3.v4.js");
class Node {
constructor(name, data) {
// This is normally called ID, using name because of d3
this.name = name || undefined;
this.data = data || undefined;
// Usually...
// this.left = undefined;
// this.right = undefined;
this.children = new Array(2);
}
}
return Node;
One neat thing about a tree is everything is a node - we get a lot of value
out of this simple data structure.
To start the tree we just create a _root_ node
const [Node] = arguments; const root = new Node(); return [Node, root];
If you use this in a real problem, some care must be taken here. As we start
adding things to this tree the _root_ node will become the pivot point of
the tree. You want this to be as close to the middle as possible - whatever
you define the _middle_ as. This will help keep the tree balanced. For now,
we'll just ignore that.
We'll make a simple insert function and insert a bunch of numbers into our
tree:
const [[Node]] = arguments;
const root = new Node();
function insert(root, name, data) {
// if nothing here, we'll use this node
if (root.name === undefined) {
root.name = name;
root.data = data;
return true;
}
// Duplicate
if (root.name === name) {
// should also save this data.
// but we'll ignore it in this example
return false;
}
if (name < root.name) {
if (root.children[0] === undefined) {
root.children[0] = new Node(name, data);
return true;
}
return insert(root.children[0], name, data);
}
if (name > root.name) {
if (root.children[1] === undefined) {
root.children[1] = new Node(name, data);
return true;
}
return insert(root.children[1], name, data);
}
return false;
}
for (const i of [4,621,12,451,131,33,22,56,64]) {
insert(root, i, `#${i}`);
}
return root;
This insert function looks at a number, and if it is greater than or less
than the given value, and adds a node to the _left_ or _right_.
To visualize the tree we just made, let's use D3:
const [data, me] = arguments;
const svg = K.GetD3Canvas(me);
svg.selectAll("*").remove();
let width = 360
let height = 260
const g = svg.attr("width", width)
.attr("height", height)
.append("g")
.attr("transform", "translate(40,0)");
// Create the cluster layout:
let cluster = d3.cluster().size([height, width]);
let root = d3.hierarchy(data, function(d) {
if(d) return d.children;
});
cluster(root);
// Add the edges
g.selectAll('path')
.data( root.descendants().slice(1) )
.enter()
.append('path')
.attr("d", function(d) {
const p = "M" + d.y + "," + d.x
+ "C" + (d.parent.y + 10) + "," + d.x
+ " " + (d.parent.y + 10) + "," + d.parent.x
+ " " + d.parent.y + "," + d.parent.x;
return p;
})
.style("fill", 'none')
.attr("stroke", '#ccc')
// Add each node.
g.selectAll("g")
.data(root.descendants())
.enter()
.append("g")
.attr("transform", function(d) {
return "translate(" + d.y + "," + d.x + ")"
})
.append('text')
.attr("dy", ".35em")
.attr("x", function(d) {
if(d) return d.children || d._children ? -13 : 13;
})
.text(function(d) { return (d && d.data) ? d.data.name || "0" : "∅"; });
svg.style("height", "280px");
return data;
If the output doesn't make sense, use the graph output and the insert code
above, have a play with tweaking the values of the array. Maybe make the
array have fewer numbers, or '1,2,3,4' or start with 300 - rerun the code
blocks and see how the tree changes.
Now for the first magic trick.
If we iterate over the nodes in a particular way, they come out sorted. We
can make them ascending or descending depending on which side we visit
first.
Here is ascending:
const [data, me] = arguments;
const sorted = [];
function sort(node, sorted) {
if(node.children && node.children[0]) {
sort(node.children[0], sorted);
}
sorted.push(node);
if(node.children && node.children[1]) {
sort(node.children[1], sorted);
}
}
sort(data, sorted);
K.Print(me, sorted.map(i => i.name).join(', '));
return data;
I remember when I first learned this - it blew my mind. Try adding numbers
to the array and re-running. If you're feeling saucy, see if you can make
the sort order descending.
In most programming languages, you wont need to do this kind of thing by
hand. There will often be built-in libraries or functions you can use. But
if you ever find yourself in some low level language, this can be a useful
trick.
So we've got insert, and sort. Let finish up with find. Find is actually
quite simple, but it's got some recursion which is fun in and of itself:
const [data, me] = arguments;
function find(node, query) {
if (node === undefined || query === undefined) return undefined;
if (node.name === query) {
return node;
}
if (node.name > query) {
return find(node.children[0], query);
}
if (node.name < query) {
return find(node.children[1], query);
}
}
const rtn = find(data, 131);
K.Print(me, rtn?.name || 'Not Found');
The idea here is similar in spirit to the sort function. Have a play.
While this data structure almost never comes up in day to day web
development, I've used it quite a bit in games programming and backend
utilities. It's a fun data structure, and a good trick to keep in your
pocket.
[1]: https://en.wikipedia.org/wiki/Tree_sort
[2]: https://www.desmos.com/calculator/6qwqwc0w4s