為什麼不用二叉查找樹進行排序？

01-06

二叉查找樹中序遍歷是單調的，但是在使用樹結構實現排序演算法時，很多都是用堆來實現的，為什麼不用二叉查找樹呢？如果是因為二叉查找樹最壞情況會變成一顆斜樹的話，使用平衡二叉樹或者紅黑樹不就平衡了？

一是常數大

二是二叉查找樹要用額外空間

用AVL或者紅黑樹解決排序明顯屬於殺雞用牛刀啊...

BST(AVL,紅黑樹）主要目的是同時保證動態插入，刪除，查詢複雜度為O(log n)

如果只是對一個給定數組排序的話用BST來做

1. 常數太大。題主你可以試著比較一下qsort跟生成一個avl或者紅黑樹需要的操作次數。

2. 寫起來太麻煩。題主你試著比較一下qsort跟AVL的代碼量。

3. 再補充一點就是BST來做的話需要額外空間

打高射炮犯得著用蚊子嗎？

BST之所以存在是因為人們想讓他干更多的事：隨時可以以O(logn)查找、刪除單個元素，同時保證得到的樹還是有序的。而排序就不能做到這一點。

於此對應的代價就是BST編碼複雜度更高，同時運行時還有更高的常數複雜度。所以當你用不上BST提供的那些厲害的功能的時候，還去用BST就是浪費你和你的CPU的時間

殺雞用牛刀，只需要排序不需要查找和維護的話那當然是單純的排序演算法又快又簡單。

快排一般就20行

SGI STL紅黑樹實現一共1367行，樓主自己感受下。

https://www.sgi.com/tech/stl/stl_tree.h

為什麼不用快排？

。。