_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).