Visual Binary Trees with Swift 3, Part II
08 Sep 2016
- Introduction & Summary
- Part I: QuickLook-able Binary Tree with Pluggable Traversals
- Part II: The Drawing Architecture, Customization, and Tree Layouts
This blog is a part of the series on visualizing binary trees with Swift 3. The introduction provides an overall context and summary, including a short demo taken in the Swift Playground for iPad app. The playground with sample code and practical examples is available at github.
In the previous part of the series, we defined base protocol for a QuickLook-able Binary Swift Tree. Any tree implementation that conforms to that protocol can now be visualized in the playground as well as in the Xcode debugger.
While this is already enough to start using the playground with your own tree implementations, what if you need to change the default visualization? Maybe just to use your own presets for things like fonts, lines thickness and colors, turning the grid off, etc. Or, choose a different 2D / 3D technology such as SpriteKit or SceneKit. Or leverage your own favorite algorithms for laying our a binary tree. Speaking of which, who said that the tree needs to be binary and not N-ary?
The good news is all of these options are possible and also relatively straightforward. After reading through this part, you should have a solid understanding of the drawing architecture and be in a good position to customize its components as outlined above.
Let’s go top-down and start with the high-level drawing architecture first. In a somewhat simplified form, it looks like this:
TreeDrawing there is a struct that conforms to
Drawable protocol, along with other drawables such as
Rectangle. Each drawable can draw itself using a provided
Sounds kind of familiar so far? Well, if you saw the WWDC 2015 Protocol-Oriented Programming session it definitely should be. That is also the reason why Crusty’s friendly picture is all over this blog series.
To draw a tree, our
TreeDrawing needs the tree layout information that is provided to it by an implementation of
TreeDrawing then do its thing processing the layout, switching states and passing on the drawing instructions to the
This base architecture already gives us plenty of flexibility and customization points.
For example, the default
Renderer implementation uses Core Graphics to draw the tree and a single animated
CAShapeLayer to visualize traversals. Switching to a different
Renderer would give us entire different presentation, e.g. 3D visualization with technology like SceneKit. Or, perhaps someone would prefer a plain ASCII art instead? I’m sure Crusty would be most pleased with these… 🤓
Renderers is outside of this blog’s scope (if anyone feels like a little exercise – the contributions to the playground most welcomed!), we could also do plenty of customization for the basic drawing aspects such as fonts, lines thickness, colors, grid, etc.
Customizing the drawing
In the previous part of the series, we defined QuickLookable Binary Tree protocol along with the extensions covering all of its requirements. One of these was specifically responsible for the visual tree representation:
At that point it should be a good time to look at what this
DefaultTreeDrawingConfig.configureTreeView thing really is:
Turns out it is nothing more than a little configuration helper, which assembles the key pieces of the above architecture and feeds values to available customization points.
So in case you want’d to change any of these, writing your own configuration struct along with overriding the
QuickLookableBinaryTree.quickLookView variable on your tree type should be real easy.
Tree Layout Model
Now that we covered the overall drawing architecture, let’s take a closer look on what’s behind laying out an efficient visual tree representation.
In general, the goal of all tree layout algorithms is to build a tree model where each node is assigned a unique
(x,y) coordinate so that it can be drawn in a visually meaningful way.
The following are the rules for what is considered to be “visually meaningful”:
Tree Layout requirements
- The layout reflects exact hierarchical structure of the tree
- The edges do not cross each other
- A parent node is centered over its children
- The nodes on the same level are as close as possible
- The drawing of a subtree does not depend on its position
Before diving into the next layer of specifics, let see start with the Swift definition of the tree layout model:
A few things to notice there:
TreeLayoutitself is a Traversable Tree and is initialized with a tree node that conforms to the base BinaryTree protocol. If that tree node also happens to be a Traversable Tree, its traversal is copied during initialization. Then the layout simply builds itself after the tree node, with some initial
Since the base tree structure of layout model will not change after initialization,
TreeLayoutoverrides the default implementation of its
heightproperty. That helps avoid quadratic time during
initas well as in all future usages of the property.
The layout is meant to be built in logical coordinates of
Inttype. These can be easily mapped to physical dimensions later on, with some useful extension properties:
- Finally, for the astute readers wondering about the purpose of that
extrasvar. Some of the more complex algorithms need to define various additional layout properties, and this is a way of enabling just that. Subclassing the model would obviously be another option, however it’d be by far less clean and effective (as should become apparent in next few moments).
The history of Tree Layouts
At that point, we’ve defined our layout model and the only thing remaining is to actually give it some valid
Half of that already looks trivial, as for each node we should be able to easily figure out its
y coordinate based on the node’s depth. So what is all the fuss about the remaining
Well, turns out it is quite fascinating by itself and for general case happens to be one of the classic NP-complete problems with a relatively long history and many contributions from leading computer scientists.
One of the first tree layout algorithms was described by Donald Knuth1, and basically is a simple in-order traversal while incrementing a single x-position counter.
Here is how it looks when used in the playground. While being among the simplest and fastest algorithms, the drawback is that the x-coordinate is never reused and thus the layout is quickly doing wide. It can also easily digress into some weird tree shapes.
A few years after Knuth, Charles Wetherell and Alfred Shannon2 came up with a number of interesting concepts including another simple and efficient technique for generating minimal width layouts. Instead of a single x-counter, they used independent counters per level. While processing the tree in pre-level order, each counter is updated independently and therefore the layout width grows conservatively:
From looking at the generated drawing of the same tree, the immediate observations are:
The minimal width property is indeed quite impressive
It’s hard to describe this layout as even remotely “visually meaningful” 😱
For larger trees, the layout quickly becomes real hard to follow
Two years later, Edward Reingold and John Tilford3 continued building on the existing research and came up with several new ideas and the eventual algorithm producing nicely shaped layouts according to the above requirements while still running in O(n) time.
That algorithm is used as the default in the playground, and can be roughly described as the following:
Recursively build the left and right model sub-trees
Shift the right model sub-tree until on some layer it is as close to the right of the left model sub-tree as possible
Place the root vertically one level above and horizontally half-way between its children. If there is only one child, place the root at the same x as the child
While conceptually in the “almost simple” category 🤓, the hard problem with the algorithm was how to make it run in linear time. Shifting subtrees via straightforward recursion would not work, as it would inevitably result in quadratic times.
To solve this, Reingold and Tilford started with breaking the problem into two parts:
- Computation of the new positions for shifted subtrees
- Actual subtree shifting
To address the first part, they introduced the concepts of tree contours and threads.
Tree contours are sequences of left-most and right-most nodes for each level.
A node’s thread represents an additional relationship to the successor node in the same contour. While the name can be somewhat confusing, the threads are just extra links between the contour nodes that are not already in direct parent / child relationship. The threads purpose is to help reduce the amount of time needed to scan subtrees for their contours.
Next, to solve moving nodes in a subtree they applied the
mods property introduced earlier in the already mentioned paper by Charles Wetherell and Alfred Shannon. A
mod is an additional property for each node, used to calculate positions of its children. These are then calculated in two passes, by first giving each node a preliminary position along with the mod during the bottom-up sweep and then adjusting these positions during a top-down traversal via adding aggregated sum of mods on the path from the root.
Still with me? Let’s see how these extra properties look in Swift code:
TreeLayoutBuilderReingold struct listing is a bit on the longish side, and is not shown here for practical purposes. For anyone curious to see how all of the above concepts are implemented, the code lives here and should have enough comments for the key parts of the algorithm.
There is a detailed description of the Reingold’s et al. algorithm in a great paper of C. Buchheim, M. J Unger, and S. Leipert4. That paper by itself takes the art of tree drawing to yet another level, via describing an efficient, O(n) algorithm of laying out arbitrary N-ary trees.
Another valuable resource on the subject is a Python magazine article by Bill Mill5, which is also available online in Bill’s blog.6 In addition to going through the concepts, Bill is providing lots of Python code samples that help understand things from the perspective of a pragmatic developer.
This was the final part of the series on visualizing binary trees with Swift 3.
At that point, you should be familiar with using the the playground with your own tree implementations, as well as with customizing the tree drawings with your own preset configurations and changing the architectural components for specific needs of your project.