Binary Tree
Return to: Chialisp
1
/ \
/ \
/ \
/ \
/ \
/ \
2 3
/ \ / \
/ \ / \
4 6 5 7
/ \ / \ / \ / \
8 12 10 14 9 13 11 15
^ ^ ^ ^ ^ ^ ^ ^
16-24 20-28 18-26 22-30 17-25 21-29 19-27 23-31
32-48 62 33 47-63
64-96 126 65 95-127
128 254 129 255
256 510 257 511
Binary Tree example and explanation(as per Jakub Hadamcik @hadamcik 2021-07-10)
Btw there is (fairly) simple way how to calculate which # you want just by looking at solution (instead of writing very deep tree).
If you have for example (1 2 (((5 6) 4) 3)) and you want to know which # gets you atom for position of number 6 in that solution you just need to decode it into set of left/right (first/rest.. whatever works for you, it's same)
So you start with `1` as first and (2 (((5 6) 4) 3)) as rest and ask "is number I want on the left or right".. in this case it's right so you write down `R`
And you continue `2` and rest (((5 6) 4) 3) => `R`
So whole process is:
`1` and rest (2 (((5 6) 4) 3)) => `R`
`2` and rest ((((5 6) 4) 3)) => `R`
(((5 6) 4) 3) and rest () => `L`
((5 6) 4) and rest (3)=> `L`
(5 6) and rest (4) => `L`
`5` and rest (6) => `R`
`6` and rest `nil` => `L`
so result is `RRLLLRL` this you can convert to binary where `R` => 1 and `L` = 0 so `1100010`
For each position you then need to calculate `2^position*(binary + 1)` and sum those together (sounds harder than it is 😃)
Example for `1100010`:
`1`: `2^0 * (1 + 1)` = `2`
`1`: `2^1 * (1 + 1)` = `4`
`0`: `2^2 * (0 + 1)` = `4`
`0`: `2^3 * (0 + 1)` = `8`
`0`: `2^4 * (0 + 1)` = `16`
`1`: `2^5 * (1 + 1)` = `64`
`0`: `2^6 * (0 + 1)` = `64`
and when you sum results: `2+4+4+8+16+64+64` = `162` and add 1 to it (always; because 1 is for root) so final is `163` and brun '163' '(1 2 (((5 6) 4) 3))' gets you `6`
——————————————
Simpler format is in 2 rows. Top row is 2^position and bottom row is binary where if it's `L` you just take number from top row and if it's `R` you multiply it by 2. So:
1 2 4 8 16 32 64 ... 1 1 0 0 0 1 0
2 + 4 + 4 + 8 + 16 + 64 + 64 = 162