arrays - 我可以使用 Day-Stout-Warren 来重新平衡在数组中实现的二叉搜索树吗？

Question

因此，我实现了一个由数组支持的二叉搜索树。完整的实现是 here .

因为树是由数组支持的，所以我通过对当前索引执行算术来确定左右 child 。

private Integer getLeftIdx(Integer rootIndex) {
    return 2 * rootIndex + 1;
}

private Integer getRightIdx(Integer rootIndex) {
    return 2 * rootIndex + 2;
}

我已经意识到，随着树变得不平衡，这可能会变得非常低效，部分原因是数组将稀疏填充，部分原因是树的高度会增加，导致搜索趋向于 O(n)。

我正在寻找重新平衡树的方法，但我不断遇到像 Day-Stout-Warren 这样的算法这似乎依赖于树的链表实现。

这只是数组实现的权衡吗？如果不创建第二个数组，我似乎想不出一种重新平衡的方法。

Answer 1

假设您有一个长度为 M 的数组，其中包含位于不同位置的 N 个项目(当然 N < M)，并且您想要将它们重新分配到“有效位置”而不更改它们的顺序。

要做到这一点，您可以首先从头到尾遍历数组，在末尾将所有项目打包在一起，然后从头到尾遍历数组，将一个项目移动到您找到的每个有效位置，直到您运行没有元素。

这个简单的问题与您的问题相同，只是您不想按“索引顺序”遍历数组，而是想按二进制顺序遍历数组订单。

您想将所有项目移动到“有效位置”，即索引< N 对应的数组部分，并且您不想更改它们的有序遍历顺序。

因此，以相反的顺序遍历数组，将项目打包到顺序最后可能的位置。然后按顺序向前遍历这些项目，将每个项目放入顺序优先的可用有效位置有效位置，直到用完所有项目。

但请注意:考虑这一点很有趣，但它不会使您的树高效地进行插入——您必须进行过多的重新平衡才能将数组保持在合理的大小。

但请注意:您实际上不必重新平衡整棵树。当插入没有空闲位置时，您只需重新平衡路径上有额外空间的最小子树。我依稀记得一个我认为适用的结果，它表明当您的数组具有固定数量的额外级别时，使用此方法插入的摊销成本为 O(log^2 N)。当我有时间时，我会计算并计算出实际成本。