Max integer with same strings, in a red black tree

Question

I have a tree with a set of numbers, where each number has 2 strings associated :a and b. So the structure looks like:

a-number-b

for each node.

I want to get the maximum number in the tree where a=b in O(log n) worst case run time.

My approach: Tried a Red black tree. This has O(log n) if the number is in right sub-tree. But O(n) if the number is in left sub tree.

Cant use regular BST, as for worst case, it has O(n) as the runtime.

Answer 1

One solution is to maintain two trees; one where a == b and one where a != b. For most functions you will probably need to call in to both trees but this will end up as the same big-O complexity since 2*O(log n) -> O(log n).