Monday 14 December 2015

the easy way to make a big binary tree

A big binary tree would be a bit of work to define fully by hand. So in this short post, an example of how to build one easily.

The BKO:
sa: context bigger binary tree
sa: child |*> #=> left |_self> + right |_self>
sa: left-op |*> #=> merge-labels(|_self> + |0>)
sa: right-op |*> #=> merge-labels(|_self> + |1>)
sa: left |x> => |0>
sa: right |x> => |1>
sa: left |0> => |00>
sa: right |0> => |01>
sa: left |1> => |10>
sa: right |1> => |11>
That gives us a seed tree, now we can grow it rapidly. First note the results of applying child^k to |x>:
sa: child |x>
|0> + |1>

sa: child^2 |x>
|00> + |01> + |10> + |11>
Now, we use this to grow the tree!
  map[left-op,left] child^2 |x>
  map[right-op,right] child^2 |x>

  map[left-op,left] child^3 |x>
  map[right-op,right] child^3 |x>

  map[left-op,left] child^4 |x>
  map[right-op,right] child^4 |x>

  map[left-op,left] child^5 |x>
  map[right-op,right] child^5 |x>

  map[left-op,left] child^6 |x>
  map[right-op,right] child^6 |x>
And now we are done. And it is trivial to make even bigger trees using the same method.
Here is the result:
sa: dump
----------------------------------------
|context> => |context: bigger binary tree>

child |*> #=> left |_self> + right |_self>
left-op |*> #=> merge-labels(|0> + |_self>)
right-op |*> #=> merge-labels(|1> + |_self>)

child |*> #=> left |_self> + right |_self>
left-op |*> #=> merge-labels(|_self> + |0>)
right-op |*> #=> merge-labels(|_self> + |1>)

left |x> => |0>
right |x> => |1>

left |0> => |00>
right |0> => |01>

left |1> => |10>
right |1> => |11>

left |00> => |000>
right |00> => |001>

left |01> => |010>
right |01> => |011>

left |10> => |100>
right |10> => |101>

left |11> => |110>
right |11> => |111>

left |000> => |0000>
right |000> => |0001>

left |001> => |0010>
right |001> => |0011>

left |010> => |0100>
right |010> => |0101>

left |011> => |0110>
right |011> => |0111>

left |100> => |1000>
right |100> => |1001>

left |101> => |1010>
right |101> => |1011>

left |110> => |1100>
right |110> => |1101>

left |111> => |1110>
right |111> => |1111>

left |0000> => |00000>
right |0000> => |00001>

left |0001> => |00010>
right |0001> => |00011>

left |0010> => |00100>
right |0010> => |00101>

left |0011> => |00110>
right |0011> => |00111>

left |0100> => |01000>
right |0100> => |01001>

left |0101> => |01010>
right |0101> => |01011>

left |0110> => |01100>
right |0110> => |01101>

...
And here is the picture:

No comments:

Post a Comment