binary-search-tree - 使用数组的 bst 表示的优势

我一直使用的使用数组的 bst 表示是一个排序数组，它的根在中间，每个孩子都在数组的端点和根的中间

前几天我遇到了一个不同的表示：根是数组的第一个元素（索引 0）。然后，对于索引为 n 的元素，2n+1 是它的左孩子，2n + 2 是它的右孩子

我的问题是后者有什么优势？它们都是平衡树，因此我们确信 log n 搜索复杂性。但是，第一个表示看起来更适合插入/删除，因为这两种表示都需要在树中移动很多元素，而且（对我来说）用第一个表示自然更容易这样做

在第一个表示中按范围搜索也听起来更好，因为元素是连续的

有没有我应该使用第二种表示的情况？（当然，前提是我选择使用数组表示）

标签： binary-search-tree

立即想到的是，如果您将快速连续访问左右孩子，则后一种实现为您提供更好的参考位置。

也就是说，如果孩子们被存储在一个大数组中，它们将位于不同的内存页面中，因此对两者的访问很可能是缓存未命中甚至页面错误。在将两个孩子放在连续位置的布局中，几乎所有对第二个孩子的访问都将在缓存中。这可能会对广度优先搜索的速度产生很大影响。

前一种实现产生一个排序数组，它可以加速许多其他算法。

后者在数组末尾添加新的子节点，因此如果算法填充平衡树的每一层，则第二个布局不需要移动或交换任何节点。