World's most popular travel blog for travel bloggers.

[Solved]: Find node with key of at least n in a binary search tree

, , No Comments
Problem Detail: 

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.

Asked By : iravid

Answered By : D.W.

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)$

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/12971

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback