AVL树:如何进行索引访问？

Question

我在AVL Tree Wikipedia页面上注意到以下评论:

"如果每个节点另外记录其子树的大小(包括它自己及其后代),那么也可以通过索引在O(log n)时间内检索节点."

我用google搜索并找到了一些提到索引访问的地方,但似乎无法找到人们会编写的算法的解释.

非常感谢

[更新]谢谢大家.如果发现@templatetypedef与@ user448810之一的链接结合起来特别有帮助.特别是这个剪辑:

"这两个函数的关键是节点的索引是它的左子节点的大小.只要我们通过它的左子节点下降树,我们只需要取节点的索引.但是当我们必须移动时通过正确的孩子在树下,我们必须调整大小,以包括我们排除的树的一半."

因为我的实现是不可变的,所以在重新平衡时我不需要做任何额外的工作,因为每个节点计算它的构造大小(与方案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();}
}

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

Answer 1

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

• 要在BST中查找其根节点在其左子树中具有k个元素的第n个元素:
  • 如果k = n,则返回根节点(因为这是树中的第0个节点)
  • 如果n≤k,则递归地查找左子树中的第n个元素.
  • 否则,在右子树中查找(n - k - 1)st元素.

这需要时间O(h),其中h是树的高度.在AVL树中,这个O(log n).在CLRS中,这种结构被探索应用于红/黑树,他们称这些树为"秩序统计树".

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

希望这可以帮助!