推 Biboy:講解的好清楚! 終於弄懂這是如何觀察出來的了! 謝謝! 05/03 20:34
1
10 11
100 101 110 111
1000 1001 1010 1011 1100 1101 1110 1111
根據這棵樹的定義，一個點 (x) 的兩個子節點分別為 (2x) 和 (2x + 1)
或是 (x << 1) 和 ((x << 1) + 1) ，也就是說，一個點的子節點有著和自己一樣的開頭
Ex:
2 (10) 的子節點是 4 (100) 和 5 (101) ，開頭都是 10
而且， xxx0 一定是 xxx 的左子節點， xxx1 一定是 xxx 的右子節點
再來看走訪的順序：對每個子樹都是先走左邊再走右邊再走左邊......
以 1 來說，從他出發往下走，一定是 10..., 11..., 10..., 11...
換句話說，
第奇數個球一定是掉在 10... 這個終端節點，
第偶數個球一定是掉在 11... 這個終端節點
再換句話說，
(I - 1) 的最後一個 bit 就是終端節點的第二個 bit (第一個 bit 一定是 1)
再來看看第二層，先看 10 這個節點，從他往下走一定是
100..., 101..., 100..., 101...
而從 11 往下走一定是
110..., 111..., 110..., 111...
我們看一下 (I - 1)：當 (I - 1) 是 ...0 的時候，終端節點是 10...
(I - 1) = ...00:
10 這個節點是 false ，往左走 => 100...
(I - 1) = ...10:
10 這個節點是 true ，往右走 => 101...
(I - 1) = ...0 的時候也類似，
我們可以歸納出 (I - 1) 的倒數第二個 bit 就是終端節點的第 3 個 bit
再來就是用歸納法，
已知 (I - 1) 的倒數第 1 ~ k 個 bit 是終端節點的第 2 ~ (k + 1) 個 bit
那 (I - 1) 的倒數第 k + 1 個 bit 是終端節點的第 k + 2 個 bit。
所以，把 (I - 1) 的 bit 倒過來排，最前面再補一個 1 ，就是終端節點的編號
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.49.204