1
$\begingroup$

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?

$\endgroup$
4
  • $\begingroup$ So... basically a LSB radix tree, then? $\endgroup$
    – Pseudonym
    Jun 13 at 14:02
  • $\begingroup$ i guess radix trees have the complexity of O(n) but i observe this one to have O(lg n).. (please correct me if i am wrong) $\endgroup$ Jun 13 at 15:18
  • $\begingroup$ Good point. How about Patricia tries? $\endgroup$
    – Pseudonym
    Jun 14 at 5:51
  • $\begingroup$ Yes, I guess thats a good example $\endgroup$ Jun 14 at 8:16
1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Ohh okay. That cleared things out. Thanks! $\endgroup$ Jun 13 at 15:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.