2
$\begingroup$

Treesort sorts input by putting input into a binary search tree and then flattening the tree. In some cases the tree can become unbalanced and so a self-balancing tree is required. There is no requirement for a self-balancing tree if the input is first randomly jumbled up first. However, one cannot shuffle a stream of data without waiting for all the data which is undesirable sometimes.

If I take inputs two at a time and randomly swap them before inserting them how unbalanced will the tree tend to become over time?

|cite|improve this question
$\endgroup$
  • 2
    $\begingroup$ Welcome to CS.SE! What have you tried? Have you tried seeing what happens when you feed your proposed algorithm a stream of numbers that are already in sorted order; or that are in reverse-sorted order? Have you tried writing some code to simulate what happens and run a few random simulations? You should be able to get a pretty good idea by trying this! $\endgroup$ – D.W.♦ Mar 8 '17 at 2:05
  • $\begingroup$ @D.W Yes. It seems to have height proportional to $\frac{n}{\log_2 m}$ where $n$ is the length of the input and $m$ you take before you shuffle and add. But I can't figure out how to prove this. $\endgroup$ – Steven Stewart-Gallus Mar 8 '17 at 19:59
  • $\begingroup$ It seems your question focuses on the case of swapping two at a time, so I assume that means $m=2$, i.e., you experimentally seem to think the height is proportional to $n$. Try proving this. Can you prove something about the height, for the special case where the inputs are in already-sorted order, or in reverse-sorted order? Hint: look at everything but the least significant bit of each number of the input. I'd suggest you spend a little more time trying to solve this yourself, then edit the question to show your work so far and your progress and where you got stuck. $\endgroup$ – D.W.♦ Mar 8 '17 at 21:14

Your Answer

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

Browse other questions tagged or ask your own question.