Algorithm Help

[fartman_900]

Hi. I'm trying to figure out a problem from my homework. Its about Red-Black trees. Also, this can be used for a regular BST.

Heres the problem, I have to come up with an algorithm that finds the n-th element in the Red-Black tree. My teacher said that it should be O(log n), but the best I can think of is O(n). The way I was thinking was doing an ordered search and place each key into an array, and return the n-th one.

I've been thinking all weekend on how to do this in O(log n), but have thought of nothing. I think its impossible since you have to figure out the keys position in the tree, but you have to look at all keys to do this. Like, you just cant start at the root, and from there knowing what index you are looking for, make the right choice on either left or right, then somehow getting to the correct spot.

Anyone have any ideas on how to do this one? I'm stumped

[fartman_900]

I think I may have come up with a solution to this, but I still may need help. So I came up with this. Just add another integer value to each node that stores the index of it. This will solve it, since I can just do a binary search with the indecies, thus O(log n).

The only problem with this is that any time something is added/removed, all the indecies would have to updated, then inserting/deleting is O(n).

What do you guys think about that? Because I know that inserting/deleting are more common then a find-nth element function call, so those should stay O(log n) and find-nth should be O(n).