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.