Working on a project for my Data Structures class.

I've implemented a Red/Black tree in Java. One of the operations required of the data structure is "find a node which has a key of at least n". The leaves of the tree are the sentinel node.

My initial thought was using the regular search with modifications:

  1. Search for a node with key == n
  2. If result == sentinel, call getSuccessor on parent until a node with key > n is found

I -think- this is $O(m*lgm)$ ($m$ being number of nodes in the tree) at the worst case.

Inspired by the getSuccessor code - if right subtree of target node is empty, find smallest ancestor which has a left child also an ancestor - was wondering if there is a better way to do this.

Would appreciate any advice; thanks.

  • $\begingroup$ How about this trick: always remember what the largest element inserted so far is. Then you can always return a correct answer in constant time. Of course if the largest element gets removed, you have to update it. Depending on your application, this might work really well. $\endgroup$ – Juho Jun 29 '13 at 21:36
  • $\begingroup$ Not quite - I need to support a query such as tree.findAtLeast(12) which will return either a node with key == 12, or a node with the consecutive key. Perhaps I misunderstood your suggestion? $\endgroup$ – iravid Jun 29 '13 at 21:38
  • 1
    $\begingroup$ Right, in that case you don't want to find the key whose value is at least $n$. Instead, you want to find the least value greater than $n$. $\endgroup$ – Juho Jun 29 '13 at 21:45

Try a binary search tree. The leaves will be in sorted order. In $O(\lg m)$ time, you can either find a node with value $n$, or you can find the next node larger than $n$.

EDIT: If you don't find the $n$ valued node you'll reach a $nil$ node, WLOG if you reach it from the right then it's successor is the consecutive node, if you reached it from the left then the first successor in the tree of the leaf you reached which is on the right of where you reach it from is the consecutive node. Each traversal is no more than the height of the tree so you're still within $O(\lg m)$

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.