Building binary trees from inorder-depth lists - Eli Bendersky's website

I ran into an interesting algorithm while hacking on Advent of Code a while ago. This post is a summary of what I'velearned.

Consider a binary tree that represents nested pairs, where each pair consistsof two kinds of elements: a number, or another pair. For example, the nestedpair ((6 9) ((3 4) 2)) is represented with this tree [1]:

(ignore the numbered lines on the right for now, we'll get to them shortly)

Trees representing such pairs have the following characteristics:

• Leaves hold numbers, while internal nodes don't hold numbers, but onlypointers to child nodes.
• Each node in the tree has either 0 or 2 children.
• A non-empty tree has at least one internal node.

While looking for alternative solutions to aproblem, I ran across Tim Visée's Rustsolution which uses an interesting representation of this tree. It's representedby an in-order traversal of the tree, with a list of (value depth) pairswhere value is a leaf value and depth is its depth in the tree. Thedepth starts from 0 at the root - this is what the numbered lines in the diagramabove represent.

For our sample tree, the inorder-depth representation is as follows:

(6 2) (9 2) (3 3) (4 3) (2 2)

The surprising realization (at least for me) is that the original tree canbe reconstructed from this representation! Note that it's just a list of leafvalues - the internal nodes are not specified. It's well known that we can'treconstruct a tree just from its in-order traversal, but a combination of theadded depth markers and the restrictions on the tree make it possible.

I'll present a recursive algorithm to reconstruct the tree (based on Tim Visée'scode, which does not explicitly rebuild the tree but computes something on it);this algorithm is very clever and isn't easy to grok. Then, I'll present aniterative algorithm which IMHO is easier to understand and explain.

But first, let's start with the data structures. The full (Go) code is availableon GitHub.

type DItem struct {  Value int  Depth int}type DList []DItem

This is our representation of the inorder-depth list - a slice of DItemvalues, each of which has a numeric value and depth.

The tree itself is just what you'd expect in Go:

type Tree struct {  Value       int  Left, Right *Tree}

Here is the recursive version of the tree reconstruction algorithm:

func (dl DList) BuildTreeRec() *Tree {  cursor := 0  var builder func(depth int) *Tree  builder = func(depth int) *Tree {    if cursor >= len(dl) {      return nil    }    var left *Tree    if dl[cursor].Depth == depth {      left = &Tree{Value: dl[cursor].Value}      cursor++    } else {      left = builder(depth + 1)    }    var right *Tree    if dl[cursor].Depth == depth {      right = &Tree{Value: dl[cursor].Value}      cursor++    } else {      right = builder(depth + 1)    }    return &Tree{Left: left, Right: right}  }  return builder(1)}

I find this algorithm fairly tricky to understand; the combination of doublerecursion with mutable state is powerful. Some tips:

• cursor represents the next item in the inorder-depth list; it mayhelp thinking of it as a queue; taking dl[cursor] and advancing cursoris akin to popping from the head of the queue.
• The depth parameter represents the depth in the tree the builder iscurrently on. If the next item in the queue has a matching depth, we constructa leaf from it. Otherwise, we recurse with higher depth to construct aninternal node starting from it.
• The basic recursive invariant for builder is: the remaining items indl represent a pair: build its left side, then build its right side.

If it's still not 100% clear, that's OK. In what follows, I'll describe analternative formulation of this algorithm - without recursion. IMHO this versionis easier to follow, and once one gets it - it's also easier to understand therecursive approach.

To get some intuition for how the algorithm works, let's first work through theexample we've using throughout this post. We'll take the inorder-depthrepresentation:

(6 2) (9 2) (3 3) (4 3) (2 2)

And will see how to construct a tree from it, step by step. In what follows, thenumbered list walks through inserting the first 6 child nodes into the tree,and the steps correspond one-to-one to the diagrams below the list. Each stepof the algorithm inserts one node into the tree (either an internal node ora leaf node with the value). The red "pointer" in the diagrams corresponds tothe node inserted by each step.

Let's assume we begin with the root node already created.

1. To insert (6 2) we have to get to depth 2. The children of the root nodewould be at depth 1, so we have to create a new internal node first. Sincethe list is in-order, we create the left child first and move our pointer toit.
2. Now our current node's children are depth 2, so we can insert (6 2).Since the current node has no left child, we insert 6 as its left child.
3. The next node to insert is (9 2). The node we've just inserted is a leaf,so we backtrack to its parent. Its children are depth two, and it has noright child, so we insert 9 as its right child.
4. The next node to insert is (3 3). The current node is a leaf so it can'thave children; we climb up to the parent, which already has both its childrenlinks created. So we climb up again, to the root. The root has a left child,but no right child. We create the right child.
5. Since the current node's children are depth 2, we can't insert (3 3) yet.The current node has no left child, so we create it and move into it.
6. The current node's children are depth 3, so we can insert 3 as its leftchild.

And so on, until we proceed to insert all the values.

The main thing to notice here is that the insertion follows a strict in-order.We go left as far as possible, then backtrack through the parent and turn right.How much is "possible" is determined by the depth markers in the representation,so there's actually no ambiguity [2].

Before we move on to the code, one important point about reaching a parentfrom a given node. There are at least two common ways to do this: one is keepingparent links in the nodes, and another is using a stack of parents whileconstructing the tree. In the code shown below, I opt for the second option -an explicit stack of parent nodes. This code can be easily rewritten with parentlinks instead (try it as an exercise!)

With all that in place, the code shouldn't be hard to understand; here it is,with copious comments:

// BuildTree builds a Tree from a DList using an iterative algorithm.func (dl DList) BuildTree() *Tree {  if len(dl) == 0 {    return nil  }  // result is the tree this function is building. The result pointer always  // points at the root, so we can return it to the caller. t points to the  // current node being constructed throughout the algorithm.  result := &Tree{}  t := result  // depth is the current depth of t's children.  depth := 1  // stack of parent nodes to implement backtracking up the tree once we're done  // with a subtree.  var stack []*Tree  // The outer loop iterates over all the items in a DList, inserting each one  // into the tree. Loop invariant: all items preceding this item in dl have  // already been inserted into the tree, and t points to the node where the  // last insertion was made.nextItem:  for _, item := range dl {    // The inner loop find the right place for item in the tree and performs    // insertion.    // Loop invariant: t points at the node where we're trying to insert, depth    // is the depth of its children and stack holds a stack of t's parents.    for {      // Check if item can be inserted as a child of t; this can be done only if      // our depth matches the item's and t doesn't have both its children yet.      // Otherwise, t is not the right place and we have to keep looking.      if item.Depth == depth && t.Left == nil {        t.Left = &Tree{Value: item.Value}        continue nextItem      } else if item.Depth == depth && t.Right == nil {        t.Right = &Tree{Value: item.Value}        continue nextItem      }      // We can't insert at t.      // * If t does not have a left child yet, create it and repeat loop with      //   this left child as t.      // * If t does not have a right child yet, create it and repeat loop with      //   this right child as t.      // * If t has both children, we have to backtrack up the tree to t's      //   parent.      if t.Left == nil {        stack = append(stack, t)        t.Left = &Tree{}        t = t.Left        depth++      } else if t.Right == nil {        stack = append(stack, t)        t.Right = &Tree{}        t = t.Right        depth++      } else {        // Pop from the stack to make t point to its parent        t, stack = stack[len(stack)-1], stack[:len(stack)-1]        depth--      }    }  }  return result}

If you take some time to convince yourself that the iterative algorithm works,it becomes easier to understand the recursive one... because it's doing theexact same thing! The loops are replaced by recursion; the explicit parent stackis replaced by an implicit call stack of the recursive function, but otherwise -it's the same algorithm [3].

Finally, some credits are due. Thanks to my wife for helping me come up with theiterative formulation of the algorithm. Thanks to Tim Visée for the inspirationfor this post.

本文章由 flowerss 抓取自RSS，版权归源站点所有。

查看原文：Building binary trees from inorder-depth lists - Eli Bendersky's website