Tag: Reingold-Tilford algorithm
-
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…
-
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 tree generated by memball and treedraw
This is a (much reduced in scale) red-black tree of processes running on my main desktop, ordered by allocated memory (produced by my memball and treedraw programs – so the tree is structured using the Reingold-Tilford algorithm). If you count you will see that the path from the root (the little black ball at…
-
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 