Member Avatar for jk09

i want to apply a technique of sorting the numbers using binary search tree .
Average case of building a tree is O(lg n)
and then if i apply Inorder traversal , i could get sorted output.
So, can this technique be used over others like mergesort , quicksort etc. where the avg case is O(n lg n)???

  • 2 Contributors
  • 1 Reply
  • 99 Views
  • 6 Hours Discussion Span
  • Latest Post Latest Post by Narue
Member Avatar for Narue

Average case of building a tree is O(lg n)

You mean O(N logN). Inserting one item into a tree is logarithmic (excluding degenerate cases), but you want to add N items.

So, can this technique be used over others like mergesort , quicksort etc. where the avg case is O(n lg n)???

A tree sort is also O(N logN) provided the tree is either randomized or balanced. But consider all of the extra space and time you're spending to maintain the tree. It's not a bad idea, but not really competitive against the usual suspects for fast general sorting. I'd only use it for cases where I'm already generating a tree, that way the cost isn't quite as prohibitive.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.