Memetic Musings A blog on computing

Drawing Trees

January 24, 2014 Comments
Tags: scala functional-programming

Introduction

In the last article we saw one way of implementing Binary Search Trees and Red Black Trees. This data structure can be used to implement a Set (like we saw before), but there are many other use cases if we can augment the data stored on the nodes. One example is a TreeMap which is a key-value store - similar to HashMap but with log(n) time guarantee for operations. Other examples are Interval trees, dynamic order statistics etc.

How to Augment the Data

Recall that a Node in our RBT looked like the following:

case class Node[+T : Orderable](color: Color, v: T, left: RBT[T], right: RBT[T])

One way to augment the data is to subclass Node and add relevant data to that class. But there is a simpler approach. Note that in the above declaration, the data stored has an abstract type T whose only constraint is that it should be Orderable. So we could package all the data we need in T itself and provide appropriate ordering logic. For example, in case of a TreeMap, T can be a pair of (K, V) so that ordering is only done on K. A generic AugmentedData class can be written as follows:

case class AugmentedData[T : Orderable, U](v: T, data: U)
                              extends Ordered[AugmentedData[T, U]] {
  def compare(that: AugmentedData[T, U]): Int = this.v.compare(that.v)
}

So an AugmentedData would have a value v which is orderable and additional data of some type U.

Example - Drawing Trees

Let's look at an example where we augment data. Let's say we need to draw a given RBT (or BST). There are two logical steps to it:

  • Identify position of each Node in the picture
  • Draw the picture

We separate these two steps because drawing a picture can be done in different ways - as an image, in a terminal etc.

Step 1 - Finding positions

First we need to Augment the data stored in a Node to include its position (x,y) as well. Then we need to find and populate the positions.

We could just use the depth of a node in the tree as its vertical position (y-coordinate). Finding a horizontal position (x-coordinate) is slightly tricky and there are many different ways to do it. We will use the simple approach of taking a node's position in the inorder traversal of the tree. By definition, node on the left comes first and will have a lower x coordinate value than its root which will be lesser than its right child etc. This is not the best approach but suffices for our discussion.

We are going to define a function which takes a RBT node and gives back an RBT node which is the root of tree with augmented data. So it will look like:

def toPos[T : Orderable](node: RBT[T], d: Int = 80, start: Int = 30) : RBT[AugmentedData[T, (Int, Int)]] = ???

It has two additional parameters; to adjust the space between nodes: d and start position: start. To simplify things, we can use a helper function calcPos which finds the position and propogates it back.

def toPos[T : Orderable](node: RBT[T], d: Int = 80, start: Int = 30) : RBT[AugmentedData[T, (Int, Int)]] = {
  def calcPos(n: RBT[T], x: Int, y: Int) : (RBT[AugmentedData[T, (Int, Int)]], Int) = {
    n match {
      case Leaf => (Leaf, x)
      case Node(c, v, left, right) =>
        val (leftTree, myX) = calcPos(left, x, y+d)
        val (rightTree, nextX) = calcPos(right, myX+d, y+d)
        (Node(c, AugmentedData(v, (myX, y)), leftTree, rightTree), nextX)
    }
  }
  calcPos(node, start, start)._1
}

Step 2 - Drawing the Tree

Once we have the positions, drawing a tree is trivial. A natural way to represent the tree is using SVG format. Since it is xml the tree structure can be directly represented. Scala also support XML literals which makes things easier.

def toSvg[T : Orderable](node: RBT[AugmentedData[T, (Int, Int)]],
                         width : Int = 640, height : Int = 480): NodeSeq = {

  val rgb = Map[Color, String](Black -> "#000000", Red -> "#7f0000")

  def genNode(n: RBT[AugmentedData[T, (Int, Int)]], x: Int, y: Int): NodeSeq =
    n match {
      case Node(_, AugmentedData(_, (lx, ly)), _, _) =>
        <line id="svg_1" y2={y.toString} x2={x.toString} y1={ly.toString}
              x1={lx.toString} stroke-width="3" stroke="#000000" fill="none"/> ++
        genSvg(n)
      case Leaf => <!-- leaf -->
  }

  def genSvg(n: RBT[AugmentedData[T, (Int, Int)]]) : NodeSeq = n match {
    case Node(c, AugmentedData(t, (x, y)), left, right) =>
      genNode(left, x, y) ++
      genNode(right, x, y) ++
      <ellipse stroke={rgb(c)} fill={rgb(c)} cy={y.toString} cx={x.toString}
               ry="20" rx="20" stroke-width="5"/> ++
      <text xml:space="preserve" text-anchor="middle" font-family="serif"
            font-size="24" y={(y+7).toString} x={x.toString} stroke="#ffffff"
            fill="#ffffff">{t}</text>
    case Leaf => <!-- leaf -->
  }
  <svg width={width.toString} height={height.toString} xmlns="http://www.w3.org/2000/svg">
    <g>
      <title>RBT</title>
      {genSvg(node)}
    </g>
  </svg>
}

This produces svg images like the following:

1

See the complete code here.

<< A basic, immutable Set in Scala
>> Purely functional Priority Queue

Comments

blog comments powered by Disqus