Is this a good way to arrange data in a tree?

Question

I was recently learning about Binary Search Trees(BSTs) and thought it could be made even more efficient by making some changes.

As binary search trees have numbers greater than the root node on the right and the numbers lesser than the node on the left, we can further divide the tree into odd and even numbers to make the search easier(as we have to just check the last bit to verify if a number is odd or even)

Example:

S = {5,12,14,1,7,2,18,9,11,16,22}

This can be arranged in a tree as follows:

Here, if we have to search for element 9, we just have to look at the left side of the root node which is a BST as 9 is odd, and continue a normal binary search.

Does this make the normal BST any better or is it just unnecessary to divide it on the basis of Odd and Even elements?

Answer 1

It doesn't significantly increase the speed, the increase will just be a constant at best. Essentially, you still search the same tree, just in a different ordering, and that means you will still do $O(\log(n))$ operations to search a number.

It might be useful to think of this as just two separate BSTs, one for odd numbers and one for even numbers.

So, this isn't generally better than a normal BST (and is slightly harder to implement), unless you know something really special about the inputs.