爲什麼平衡二叉樹很重要？

Question

爲什麼很重要，一個二叉樹平衡

Answer 1

二叉樹的餘額由稱爲偏度的屬性控制。如果一棵樹更傾斜，那麼訪問二叉樹元素的時間複雜度就會增加。說一棵樹

   1 
      /\ 
       2 3 
       \ \ 
       7 4 
        \ 
         5 
         \ 
         6 

上面還二叉樹，但正偏態。它有7個元素，因此理想的二叉樹需要O（log 7）= 3查找。但是在最壞的情況下，你需要再深入一級= 4查找。所以這裏的偏度是一個常數1.但考慮樹是否有數千個節點。在這種情況下，偏斜將更加可觀。所以保持二叉樹平衡很重要。

但是，再次偏斜是辯論的話題，因爲隨機二叉樹的概率分析表明平均深度爲random binary tree with n elements is 4.3 log n。所以這實際上是平衡與偏斜的問題。

還有一件有趣的事情，計算機科學家甚至發現了偏斜的優勢，並提出了一種傾斜的數據結構，稱爲skew heap

Answer 2

想象一下，一個樹，看起來像這樣：

A 
    \ 
    B 
    \ 
     C 
     \ 
     D 
     \ 
      E 

這是一個有效的二叉樹，但現在大多數操作是O（N），而不是Ø （lg n）。

Answer 3

爲確保log（n）搜索時間，您需要在每個分支處將下級節點的總數除以2。例如，如果您有線性樹，永遠不會從根分支到葉節點，那麼搜索時間將與鏈接列表中的線性一致。

Answer 4

一個非常不平衡的樹，例如一棵樹，其中所有節點都鏈接到左邊，這意味着您在查找最後一個節點之前仍然搜索每個節點，這根本不是樹的一點，也沒有任何好處通過鏈表。平衡樹使得搜索時間O（log（n））更好，而不是O（n）。