algorithm - 通过序号索引访问红黑树

Question

我有一棵红黑树(二叉树，所有的叶子都在2层以内)。 我可以通过节点导航:向左、向右或父节点。 我知道节点的全部数量。

我必须找到树中第 N 个最小的元素。有什么方法比 O(n) 更快？通过索引优化访问的任何想法？

Answer 1

在每个节点 X 中，您应该存储以 X 为根的子树中有多少个节点。

count(LEAF) = 1
count(NODE) = count(NODE->LEFT) + count(NODE->RIGHT) + 1

在每次插入/删除期间，您应该使用此等式来更新受旋转影响的节点中的计数。

解决之后就很简单了

NODE nth(NODE root, int n) {
    if (root->left->count <= n) return nth(root->left, n);
    if ( root->left->count + 1 == n) return root;
    return nth(root->right, n - root->left->count - 1);
}