Red-black tree access by ordinal index

问题:

I have a red-black tree (binary tree, all the leaves are within 2 levels). I can navigate through nodes: to left, right or parent. I know the entire count of nodes.

I have to find the N-th smallest element in a tree. Is there any way to do this faster than in O(n)? Any ideas of optimizing access by index?

回答1:

In each node X you should store, how many nodes are in subtree with X as a root.

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

During each insert/delete you should use this equation to update counts in nodes affected by rotations.

After that solution is simple

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);
}

回答2:

you can add one attribute in each node that shows number of childrens of this node . with this attribute you can find N-th smallest node with O(lgn) .

now just you need to handle this attribute when you insert (or delete) any node into the tree. if there is no rotation then it's easy to handle but when you have rotation it's a little difficult but you can do it.

回答3:

For red black tree you do not need to track the number of nodes on the left because if it's right biased (should be) then the number of left nodes will always form a mersenne series ( 1, 3, 7, 15, 31 ...) or 2^depth -1.

With that in mind we can write down the logic to recursively get the node. The accepted answer above has its sign switched. This is the correct implementation in elixir. For package

def nth(%Rbtree{node: r}, n), do: do_nth(r, n)
defp do_nth({_,h,k,v,l,r}, n) do
  l_count = left_count(h)
  cond do
    l_count > n ->
      case l do
        nil -> {k,v}
        _ -> do_nth(l, n)
      end
    l_count == n -> {k,v}
    true ->
      case r do
        nil -> {k,v}
        _ -> do_nth(r, n - l_count - 1)
      end
  end
end
defp left_count(1), do: 0
defp left_count(0), do: 0
defp left_count(h), do: :math.pow(2,h-1)-1 |> round