6

我在AVL 树维基百科页面上注意到以下评论：

“如果每个节点还记录了其子树的大小（包括它自己及其后代），那么这些节点也可以在 O(log n) 时间内通过索引检索。”

我用谷歌搜索并找到了一些提到按索引访问的地方，但似乎找不到人们会写的算法的解释。

非常感谢

[更新] 谢谢大家。如果找到@templatetypedef 答案与@user448810链接之一相结合，特别有帮助。特别是这个snipit：

“这两个函数的关键是节点的索引是它的左孩子的大小。只要我们通过它的左孩子下降一棵树，我们只需要节点的索引。但是当我们必须移动时通过它的右子树向下，我们必须调整大小以包括我们排除的树的一半。”

因为我的实现是不可变的，所以在重新平衡时我不需要做任何额外的工作，因为每个节点都会计算它的构造大小（与方案 impl 链接相同）

我的最终实现最终是：

class Node<K,V> implements AVLTree<K,V> { ...
    public V index(int i) {
        if (left.size() == i) return value;
        if (i < left.size()) return left.index(i);
        return right.index(i - left.size() - 1);
    }
}

class Empty<K,V> implements AVLTree<K,V> { ...
    public V index(int i) { throw new IndexOutOfBoundsException();}
}

这与其他实现略有不同，如果您认为我有错误，请告诉我！

4

1 回答 1

11

这种构造背后的一般思想是采用现有的 BST 并通过将节点数存储在左子树中来扩充每个节点。完成此操作后，您可以使用以下递归算法查找树中的第 n 个节点：

  • 要查找根节点在其左子树中有 k 个元素的 BST 中的第 n 个元素：
    • 如果 k = n，则返回根节点（因为这是树中的第 0 个节点）
    • 如果 n ≤ k，递归查找左子树中的第 n 个元素。
    • 否则，在右子树中查找第 (n - k - 1) 个元素。

这需要时间 O(h)，其中 h 是树的高度。在 AVL 树中，这个 O(log n)。在 CLRS 中，这种构造被探索为应用于红/黑树，他们称这种树为“顺序统计树”。

您必须在树旋转期间添加一些额外的逻辑来调整左子树中缓存的元素数量，但这并不是特别困难。

希望这可以帮助！

于 2012-06-08T21:04:35.427 回答