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:
Home
previous: a brief look at sum of prime factors
next: maybe we dont need projections
updated: 19/12/2016
by Garry Morrison
email: garry -at- semantic-db.org