Tag: binary tree
-
I love binary trees
A few years ago I was very proud of myself for managing to translate the original Pascal of the Reingold-Tilford algorithm into C/C++ and every since then I have had a fascination for drawing binary trees. The one drawn here was actually done “by hand” in Metapost – I realised only as I finished…
-
Reviving this blog … with a question about binary trees
Work changes and a determination to actually finish my PhD mean I really should make a bit of an effort here and so I will. Here is a puzzle that has been bothering me about binary trees which has come from my PhD research… In that research I am investigating how to implement virtual memory…
-
Delays in a binary memory tree queue
This is a bit niche, but I spent a fair bit of this weekend working out what the algorithm to calculate how long a memory request packet would take to traverse a binary tree (from a leaf to the root) was. And now I have written a Groovy script (testable in your browser at https://groovyconsole.appspot.com/script/5109475228778496 –…
-
Plunging deeper
For the last month I have been working hard on some C/C++ code to simulate a 16 core computer. I had already got some code that did this – written in Groovy – but the limitations of the Java VM made it just too difficult to write efficient code to do what I really wanted…
-
The Reingold-Tilford algorithm revisited
A while ago, as part of early research into what became my MSc project, I wrote code to create and then draw red-black trees using C++. To draw the trees I used the venerable Reingold-Tilford algorithm, which is more or less the standard approach. I wrote some blogs about it and pages here seem to…
-
Red-black trees
Binary trees are seen and used frequently in computing science and computing. They are a good abstraction for many naturally occurring relationships (most of our mathematics is based on binary operations, for instance) and have O(log n) complexity (ie if you went from searching a tree of 1000 elements to a tree of 100,000 elements…
cartesian product ... stuff about computing mostly 