Деревья AVL: Как сделать доступ к индексу?

Я заметил на Страница Википедии AVL Treeследующий комментарий:

«Если каждый узел дополнительно записывает размер своего поддерева (включая самого себя и его потомков), то узлы можно получить по индексу за O(log n ) и время».

Я погуглил и нашел несколько мест, где упоминается доступ по индексу, но не могу найти объяснение алгоритма, который можно было бы написать.

Большое спасибо.

[ОБНОВЛЕНИЕ] Спасибо, люди.Если найден ответ @templatetypedef в сочетании с одной из ссылок @user448810 , это особенно поможет. Особенно этот фрагмент:

«Ключ к обеим этим функциям заключается в том, что индекс узла равен размеру его левого дочернего элемента. Пока мы спускаемся по дереву через его левый дочерний элемент, мы просто берем индекс узла ... Но когда нам нужно спуститься по дереву через его правого дочернего элемента, мы должны настроить размер, чтобы включить половину дерева, которое мы исключили».

Поскольку моя реализация является неизменной, мне не нужно было выполнять какую-либо дополнительную работу при перебалансировке, так как каждый узел вычисляет свой размер при построении (так же, как в схеме, связанной с внедрением).

Моя окончательная реализация была следующей:

class Node implements AVLTree { ...
    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 implements AVLTree { ...
    public V index(int i) { throw new IndexOutOfBoundsException();}
}

Который немного отличается от других реализаций, дайте мне знать, если вы думаете, что у меня ошибка!