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…