Gneale at 15:43, 17 November 2023

2023-11-17T15:43:41Z

← Older revision		Revision as of 15:43, 17 November 2023
Line 21:		Line 21:
	256 510 257 511		256 510 257 511

	<H2>Binary Tree example and explanation(as per Jakub Hadamcik 2021-07-10)</H2>		<H2>Binary Tree example and explanation(as per Jakub Hadamcik @hadamcik 2021-07-10)</H2>

	Btw there is (fairly) simple way how to calculate which # you want just by looking at solution (instead of writing very deep tree).		Btw there is (fairly) simple way how to calculate which # you want just by looking at solution (instead of writing very deep tree).

Gneale: Created page with "===== Return to: Chialisp ===== 1 / \ / \ / \ / \ / \ / \ 2 3 / \ / \ / \ / \ 4 6 5 7 / \ / \ / \ / \ 8 12 10 14..."

2023-11-17T15:42:49Z

Created page with "===== Return to: Chialisp ===== 1 / \ / \ / \ / \ / \ / \ 2 3 / \ / \ / \ / \ 4 6 5 7 / \ / \ / \ / \ 8 12 10 14..."

New page

===== Return to: [[Chialisp|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

<H2>Binary Tree example and explanation(as per Jakub Hadamcik 2021-07-10)</H2>

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 <code>(1 2 (((5 6) 4) 3))</code> 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 <code>(2 (((5 6) 4) 3))</code> 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 <code>(((5 6) 4) 3)</code> => `R`

So whole process is:

`1` and rest <code>(2 (((5 6) 4) 3))</code> => `R`

`2` and rest <code>((((5 6) 4) 3))</code> => `R`

<code>(((5 6) 4) 3)</code> and rest <code>()</code> => `L`

<code>((5 6) 4)</code> and rest <code>(3)</code>=> `L`

<code>(5 6)</code> and rest <code>(4)</code> => `L`

`5` and rest <code>(6)</code> => `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 <code>brun '163' '(1 2 (((5 6) 4) 3))'</code> 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

Binary Tree - Revision history

Gneale at 15:43, 17 November 2023

Gneale: Created page with "===== Return to: Chialisp ===== 1 / \ / \ / \ / \ / \ / \ 2 3 / \ / \ / \ / \ 4 6 5 7 / \ / \ / \ / \ 8 12 10 14..."