join-forest: join a forest of binary trees

_join-forest_: join a forest of binary trees

Danny Yoo (dyoo@cs.wpi.edu / dyoo@hkn.eecs.berkeley.edu)


This module provides a few functions for joining a forest of binary
trees together, preserving traversal order.  Some joining strategies
work better than others in minimizing the total depth of the concatenation.


Example
-------

    > (require (planet "join-forest.ss" ("dyoo" "join-forest.plt" 1 1)))
    >
    > (define (node-depth a-node)
        (cond
          [(pair? a-node)
           (add1 (max (node-depth (car a-node))
                      (node-depth (cadr a-node))))]
          [else 0]))
    >
    > (define (node-join node-1 node-2)
        (list node-1 node-2))
    >
    > (define tree1 '(1 (2 3)))
    > (define tree2 '((4 5) 6))
    > (define tree3 '((7 8) 9))
    > (define tree4 '10)
    > (define tree5 '11)
    > (define a-forest (list tree1 tree2 tree3 tree4 tree5))
    >
    > (define j1 (naive-join-forest a-forest node-join))
    >
    > (define j2 (simple-join-forest a-forest node-join))
    >
    > (define j3 (optimal-join-forest a-forest node-join node-depth))
    >
    > (define j4 (fib-join-forest a-forest node-join node-depth))
    >
    > (node-depth j1)
    6
    > (node-depth j2)
    5
    > (node-depth j3)
    4
    > (node-depth j4)
    4
    

API
---

> simple-join-forest: (listof X) (X X -> X) -> X

Given a nonempty list of nodes and a node-joining function, returns
the concatenation of all the nodes.  Done by splitting the forest in
half, joining both halves recursively, and then joining the
combination.  O(n).


> naive-join-forest: (listof X) (X X -> X) -> X

Given a nonempty list of nodes and a node-joining function, returns
the concatenation of all the nodes.  Done by left-folding the join
function across the forest.  O(n).


> optimal-join-forest: (listof X) (X X -> X) (X -> natural-number) -> X

Given a nonempty list of nodes, a node-joining function, and a
function defining the depth of a node, returns the concatenation of
all the nodes.  Done by computing an optimal join that minimizes the
total depth of the resulting concatenation.  O(n^3)

Note: there's a built-in assumption in optimal-join-forest that:

    (node-depth (node-join A B)) = (add1 (max (node-depth A) (node-depth B)))

If this is not true, then this function won't do what you want.
However, a more general optimal-joiner is defined in
find-optimal-join.ss.


> fib-join-forest: (listof X) (X X -> X) (X -> natural-number) -> X

Joins a forest using rules similar to those used by fibonacci heaps.
Not guaranteed to be optimal, but still good in terms of maintaining
balance.  O(n log(n)).



find-optimal-join.ss API
------------------------

There is an auxillary module in the join-forest package called
find-optimal-join.ss that's used to implement the optimal-join-forest
function.  It uses a dynamic-programming approach, closely following
the sketch of the optimal matrix-multiplication / parenthesization
algorithm in "Introduction to Algorithms."


> join-forest/cost+: (listof X) (X X -> X) (X -> natural-number) 
                       (natural-number natural-number -> natural-number)
                        -> X

Given a forest, a node-joiner, a node-cost function, and a cost+
function, returns a concatenation that minimizes cost.



> join-forest: (listof X) (X X -> X) (X -> natural-number) -> X

Given a forest,a node-joiner,and a node-cost function, returns a
concatenation that minimizes total cost.  This works under the assumption
that given nodes A and B,

    (node-cost (node-join A B)) = (add1 (max (node-cost A) (node-cost B)))

join-forest is defined in terms of join-forest/cost+:

  (define (join-forest forest join-f depth-f)
    (local [(define (cost+ c1 c2)
              (add1 (max c1 c2)))]
      (join-forest/cost+ forest join-f depth-f cost+)))




References
----------

Cormen, Leiserson, Rivest, Stein.  "Introduction to Algorithms, Second
Edition".  MIT Press and McGraw-Hill, 2001.
        
Hans-Juergen Boehm and Russell R. Atkinson and Michael F. Plass.
"Ropes: an Alternative to Strings."  Software - Practice and
Experience, Volume 25, No. 12.  pp 1315--1330.  (1995).