What are drawbacks of Tree Sort algorithm (with balanced tree) vs Tree Sort (with unbalanced tree)?

Question

Tree Sort algorithm with unbalanced tree may yield $O(n^2)$ worst-case time complexity/performance. But Tree Sort algorithm with balanced tree guarantees $O(n\log n)$ worst-case time performance.

So I do not see any practical use-cases to prefer unbalanced tree variant of Tree Sort algorithm - Tree Sort with balanced tree seems to be a clear winner on all accounts.

Is my conclusion correct? Is Tree Sort algorithm with balanced tree is always the best choice (when Tree Sort is applicable generally)?

In what cases Tree Sort algorithm with unbalanced tree can be better in some respect?

Answer 1

The advantages of unbalanced trees over balanced trees in practical situations are little to none. A large number of predefined algorithms/ data structures that many programming languages use implement a variety of the Tree Sort algorithm in order to keep time complexity of emplacement and retrieval of data to a minimum (keeping in mind that space complexity stays the same). Such varieties are AVL trees and Red-Black trees.

For instance, in STL (Standard Template Library in C++), structures such as map/ multimap, set/ multiset implement a BST as to keep the time factor to a minimum value.

An example of usage of an unordered tree (although not a binary tree) is a tree used to represent TRIE structures. You can find more about these from Wikipedia or Geeksforgeeks.

Hope this was helpful!

Answer 2

The big hurdles with self-balancing trees is that there can be a significant amount of overhead if implemented poorly. You don't have this issue in unbalanced trees because it's that simple, you insert, then they stay unbalanced.

With that being said, the difference comes down to the input.

If your input is sorted or almost sorted, as the wiki article says, it will result in a worst-case or bad-case tree which can result in the algorithm being worst-case $O(n^2)$ on an unbalanced tree. This is the scenario (almost sorted input) where you would probably want to use balanced trees.

However, if your input is sufficiently shuffled, then an unbalanced tree would still allow the algorithm to run in expected $O( n \log n)$. This is because we would be creating a Random Binary Search Tree. The expected search length to a node would be $O(\log n)$, thus allowing us to achieve expected $O(n \log n)$ for all insertions.

If you're stuck with a poorly implemented self-balancing BST, then perhaps a light-weight unbalanced tree paired with a good shuffle of the input could be more practical for you.

I haven't done it myself, but I would recommend comparing these two strategies via implementation and compare some statistics. It would probably be interesting.