CODEWITHSUNDEEP
cdata-structuresbinary-search-treeglibclibc
Alessandro Villa
Alessandro Villa

Reputation: 33

How to find the maximum value(s) in a RB tree

I'm working on a project which requires me to create and frequently search a RB tree using the glibc functions found in search.h. I have no problem creating the tree nor searching it; however, I just can't figure out a way of finding the maximum value of the tree in O(log n) time. AFAIK the right way is to just walk all the way down the right wing of the tree up until the first leaf; I really can't figure out how to implement it.

Upvotes: 3

Views: 309

Answers (1)

John Bollinger
John Bollinger

Reputation: 180103

I have no problem creating the tree nor searching it; however, I just can't figure out a way of finding the maximum value of the tree in O(log n) time. AFAIK the right way is to just walk all the way down the right wing of the tree up until the first leaf; I really can't figure out how to implement it.

I'm afraid you're out of luck. The tree-manipulation functions of (POSIX) search.h do not provide an interface directly serving the find-maximum (or find-minimum) operation, and the internal data structures they use to represent the tree are not publicly exposed, so you cannot implement the usual approach manually. You can find the maximum with use of twalk(), but doing so will require traversing the entire tree, and therefore will scale as O(n). Even finding the minimum will cost O(n), despite the fact that the depth-first walk will reach the minimum element in O(log n) steps, because it won't stop there.

Upvotes: 4

Related Questions