使用AVL樹有什麼缺點？

Question

在我看來，像AVL樹總比BST更有效。那麼爲什麼人們仍然使用BST？ AVL實施中是否會產生費用？

Answer 1

AVL樹有其優點和缺點超過其他樹木，如紅黑樹或2-3樹或只是普通的BST。

AVL樹：

優勢：

1. 簡單。相當容易編碼和理解
2. 額外存儲：非常小，每個節點2位（存儲+ 1,0，-1）。還有一個技巧，你可以通過使用你的孩子的 單個位來爲每個節點使用1位。
3. 查找常量（查看您最喜歡的 分析書：Knuth等）爲1.5 （因此爲1.5 log）。紅黑樹的常數爲2（查找時爲2 * log（n））。

缺點：

1. 缺失昂貴十歲上下。刪除一個節點仍然是對數，但可能必須一直「旋轉」到樹的根部。換句話說，一個更大的常數。紅黑樹只需要做1次旋轉。
2. 不簡單的代碼。他們可能是樹家的「簡單」，但仍然有很多或角落的情況。

如果您希望對數據進行排序，則BST將轉換爲鏈接列表。但是如果你期望你的數據是相當隨機的，那麼「平均而言」，你所有的BST操作（查找，刪除，插入）都是大約對數的。編碼BST非常容易：AVL樹雖然編碼起來相當簡單，但有很多角落案例，測試可能會非常棘手。總之，簡單的二叉搜索樹很容易編碼並且正確，如果你的數據相當隨機，應該表現得非常好（平均而言，所有操作都是對數）。 AVL Tree很難編碼，但是以一些額外空間和更復雜代碼的價格來保證對數性能。