當不平衡二叉搜索樹中的搜索操作可能比平衡二叉搜索樹中的搜索操作更有效時，我無法理解和想到這樣的場景。如果二叉搜索樹高度傾斜，那么它可能采用鏈表的形式，此時運行時間復雜度將為 O(n)。有沒有可能真正發生的情況？我的教授堅持說有一些，但我根本想不出。
uj5u.com熱心網友回復：
在某些情況下，不平衡的樹可能會更好。以下面兩棵樹為例：
二叉搜索樹背后的想法是，如果您同樣可能搜索節點集中的任何值，那么保持樹平衡可以最大限度地減少您必須進行的平均比較次數。
例如，如果我搜索每個值（1、2、3、4、5、6），那么我想搜索左側的平衡樹。在平衡樹上執行該搜索序列將導致 (3 2 3 1 2 3) = 14 次比較。在不平衡樹上執行相同的搜索序列將導致 (1 2 3 4 5 6) = 21 次比較。
但是，如果我知道我需要搜索的值不會均勻分布，而是偏低怎么辦？如果我想搜索值（1、2、1、2、1、3）怎么辦？那么哪棵樹會提供更好的性能呢？
在平衡樹上執行這些搜索將導致 (3 2 3 2 3 3) = 16 次比較。不錯，但是在不平衡樹上進行相同的搜索序列只需要 (1 2 1 2 1 3) = 10 次比較。
這是一個人為的示例，但它表明了解您的資料并了解人們可能最常搜索的值可以幫助您為該資料選擇正確的排列以提供更好的性能。
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/471191.html
上一篇：對負指數產生錯誤結果的n實作的冪