Red-Ebony Index Access

Question

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

I need to find the Nth smallest element in the tree. Is there a way to do this faster than in O (n)? Any ideas on optimizing index access?

Answer 1

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

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

During each insertion / deletion, you must use this equation to update counters at nodes affected by rotations.

After that a simple solution

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

Answer 2

you can add one attribute to each node, which shows the number of children of this node. with this attribute you can find the Nth smallest node with O (lgn).

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

Answer 3

For red ebony, you do not need to track the number of nodes on the left, because if it is correctly offset (should be), then the number of left nodes will always consist of a series of Mersenne (1, 3, 7, 15, 31 ...) or 2^depth -1 .

With that in mind, we can write the logic to recursively get the node. In the accepted answer, its button is indicated above . This is the correct implementation in the 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