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

EN

我在AVL Tree Wikipedia page上注意到了下面的评论：

如果每个节点另外记录其子树(包括其自身及其后代)的大小，则也可以在O(log n)时间内通过索引检索节点。

我在谷歌上搜索了一下，找到了一些提到accessing by index的地方，但似乎找不到一个人会写的算法的解释。

非常感谢

更新，谢谢大家。如果找到@templatetypedef答案，结合其中的@user448810 links来特别帮助。尤其是下面这段代码：

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

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

这与其他实现略有不同，如果您认为我有bug，请让我知道！