analysis.txt

Notes:

* keyroots are all nodes that have a left sibling.
* The trees in the paper are BINARY, so it's not clear for more than 2 children.
* In the first iteration of the "Main loop", i = 3, j = 2 (working on "c" and "b")
  As the preorder number is different, this means that there are three nodes in T1[1..3],
  yet 2 nodes in the sub forest T2[1..2]. We are essentially trying to compare
  c in T1 with b in T2, and now notice the difference.
  So, the first for-loop adds in deletions. "forestdist" is a 2d array,
  with the first column being 3 rows in length. We know that to get to the
  "3" in preorder number, the worse case is each previous preorder deleted.
  So { 0, 1, 2 }. I.e., the cost of deleting none, deleting 1, delete 2.
  I would assume that for nodes with higher preorder mean that more nodes
  are being deleted, i.e., deleting node 2, then node 3 from T1[1..3].
  For the second for-loop, we add in inserts.


tree		preorder #	Left	keyroot

( f ( d a ( c b ) ) e )			{ 3, 5, 6 } = { c, e, f }
--------------------------------------------------------------------
f		6		1 (a)	
  d		4		2 (b)
    a		1		2 (b)
    c		3		1 (a)
      b		2		5 (e)
  e		5		1 (a)
--------------------------------------------------------------------

( f ( c ( d a b ) ) e )			{ 2, 5, 6 } = { b, e, f }
--------------------------------------------------------------------
f		6		1 (a)
  c		4		2 (b)
    d		3		1 (a)
      a		1		1 (a)
      b		2		5 (e)
  e		5		1 (a)
--------------------------------------------------------------------