> I know that "on line" was not part of the initial spec, but the on line
> algorithm is simpler than some that have been proposed, so I suggest
> looking for it.
I came across this problem (a college senior of mine was asked this
very
question in his Amazon interview).
I settled for the following solution,
Assume that they are all positive integers (reals will definitely cause
a problem
and negatives might just, check, I'm too lazy to ;)
Now, pop numbers of the initial tree, one at a time, and insert the
binary
reversed number into the new tree.
"binary reversed" is a really weak term, what I mean is, consider the
binary
form of the decimal, reverse it, insert that number into the tree.
So say, we're dealing with 3 bit numbers, and our tree has
1 - 2 - 3 - 4 - 5 - 6 - 7, then we insert into the new tree,
4 ( reverse(001) = 100 base 2 = 4), 2, 6, 1, 5, 3, 7
So the resulting tree would be,
4
2 6
1 3 5 7 ---- Perfectly balanced.
NOTE this solution doesn't *always* give good results,
though it does improve the fully skewed mega crap
binary search tree into something a little more balanced .
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
