3
$\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?

Improve this question
$\endgroup$
3
  • 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, 2017 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$
    – Molossus Spondee
    Mar 8, 2017 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, 2017 at 21:14

0

Reset to default

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.