搜尋

二元搜尋樹和 sort 搜尋的最壞情況(資料結構)

題目在sort裡面以比較基礎來排序n個元素的演算法在最壞情況下必須花上O(n log n)次比較。

這個結論對於初始一個含有n個元素的二元搜尋樹的複雜度有何關聯不太明白題目要做什麼n個元素的二元搜尋樹要搜尋某筆資料最壞情況是n所以題目結論是要我說二元比較快這樣嗎?有沒有人能幫我解答這題
一個 n 個元素的二元搜尋樹

用 inorder traversal (中序遍訪)

O(n) 就可得此 n 個元素的排序.但是

(如 sponge 的意見)為了初始此二元搜尋樹 (即

輸入 n 個元素時

建造出它們的二元搜尋樹)

則

視此 n 個元素的加入之次序

其建造出來所花的時間

由 O(nlogn) (最佳情況--左右平衡的二元樹) 到 O(n^2) (最差情況

譬如全都都偏左邊的二元樹).如此的話

整個排序時間就有可能是 O(n^2)

沒辦法保證是 O(nlogn).因此

若用二元搜尋樹來把 n 個元素排序

為了達到的排序問題的下界 O(nlogn) (即

最快的排序方法)

則

一開始的建立二元搜尋樹時

必須設法在陸續加入此 n 個元素時

保持每加入一個元素時

目前的二元搜尋樹都是左右平衡的.然後

對此 n 個元素的二元搜尋樹

做中序遍訪

就可得排序結果.至於

如何把 n 個元素建成左右平衡的二元搜尋樹

有一方法叫 AVL-tree

它會在加入或刪除元素時

用 O(logn) 保持左右平衡 (任一點的左

右子樹的高度差

二元搜尋樹刪除二元搜尋樹定義二元搜尋樹 c 二元搜尋樹程式最佳二元搜尋樹建立二元搜尋樹二元搜尋樹時間複雜度二元搜尋樹 java 二元搜尋樹高度二元搜尋樹搜尋二元搜尋樹資料結構元素二元樹 inorder traversal 搜尋排序演算法平衡 logn

玩樂天下

玩樂天下發表在痞客邦留言(0) 人氣()

E-mail轉寄

玩樂天下