algorithm - 什么是防止缓存未命中的快速、紧凑的树结构表示？

Question

图形应用程序通常将图像表示为平面数组，而不是二维数组。如果我没记错的话，这样做是因为平面阵列紧凑且避免缓存未命中，因此速度要快得多。示例:

dimensional_array = [[1,2],[3,4],[4,5]]
four = dimensional_array[1,1]

flat_array = [1,2,3,4,5,6]
four = flat_array[1 + 2*1]

是否存在类似(或不存在)允许相同类型性能提升的自由形式树的表示？

free_form_tree = [[1,2,3],4,5,[[6,7],8]]

Answer 1

如果你的树相当完整(或者你不太关心浪费空间)并且可以放入内存，那么你可以将树存储在一个数组中。您可以使用基于数组的堆用于“搜索”树的相同公式。

• root 位于索引 0
• child 总是在索引 (2*i + 1) 和 (2*i + 2) 处，其中 i 是您当前的索引。
• 他们的 parent 是 floor((i − 1) ∕ 2) 其中 i 是 child 的索引。

Storing binary tree as an array .

此外，请参阅堆详细信息 here .