有哪些有趣的樹結構的表示方法？

12-30

Succinct Binary Trie, 由Jacobson在1989年發表於論文&, 簡單了解可以看MIT公開課: https://www.youtube.com/watch?v=3Y2weLDiUWw

A 1:1 |-B 2:2 |- D 4:4 |- NIL 8 |- NIL 9 |- E 5:5 |- NIL 10 |- NIL 11 |-C 3:3 |- F 6:6 |- NIL 12 |- NIL 13 |- G 7:7 |- H 8:14 |- NIL 16 |- NIL 17 |- NIL 15

英文字母代表key, 數字A:數字B, A是rank, B是position.

rank的意思是key在整個樹的大小, rank = 1表示是最小的.

position的意思是把整個樹拉平成vector, 在其中的位置.

我用~代表NIL, 上面的樹就是ABCDEFG~~~~~~H~~~, 等於做了一個BFS, 完全不需要任何指針, 一切信息都內隱了. 這裡唯一從資訊理論角度冗餘的信息是需要標註NIL(空節點).

A的left position = rank * 2 = 1 * 2 = 2, 2就是B; right position = rank * 2 + 1 = 1 * 2 +1 = 3, 3即C. top position是逆運算, 不贅述.

正確性:

一個節點要麼有2個child, 要麼全沒有(NIL)
如果rank = position, 說明之前的樹是完美平衡的, 第一層一定有1個節點, 第二層一定有1的二倍個節點 = 2, 第三層一定有4個節點, 以此類推. position操作自然成立.
如果rank != position, 說明之前的樹肯定有NIL. 以Node H為例, rank是8, position是14, rank缺了6, 說明有6個NIL, NIL又沒有任何child. 所以先假設NIL不存在, 然後再把NIL佔用的部分剔除掉就可以了. 令NIL不存在, H的rank應該是14, left position = 14 * 2, 但實際上有6個NIL不貢獻任何child, 14 * 2 - 6 * 2 = (14 - 6) * 2 = 8 * 2 = 16.
使用歸納法, n層的情況可以擴展到n+1層, 故證明完畢.

從rank獲得position的信息叫做rank(pos)操作

從position還原rank叫做select(rank)操作

如果肯付出一些額外的空間佔用, 那麼這兩個操作可以在O(1)內完成. 如果不願意, 清點vector仍然是一個常數項很小的O(n).

鞋腰

說個超級不常見的。為了寫這個回答專門重操了一把舊業：