如何使用van Emde Boas佈局來計算二叉樹中的指針

Question

我想使用隱式指針來實現使用van Emde Boas佈局存儲在數組中的緩存遺忘二叉樹。樹中的所有項目都是32位整數，樹會變得相當大，因此存儲指針意味着至少增加3倍的數據量。

問題是，我想不出任何非迭代方式來計算指向左側和右側兒童的指針，給定一個節點索引（我可以在遍歷樹時跟蹤任何信息）。許多論文/講座都提到了帶有隱式指針的樹，但我沒有看到用於計算指針的算法。有沒有一種有效的方法來做到這一點？

Answer 1

鮑勃科普蘭有一個很好的執行van Emde Boas trees at GitHub。他使用隱式指針並通過首先計算寬度優先指針來計算指針，之後，vEB指針是一個簡單的條件指針。