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:
- Search for a node with key == n
- 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.