爲什麼很重要,一個二叉樹平衡爲什麼平衡二叉樹很重要?
7
A
回答
5
二叉樹的餘額由稱爲偏度的屬性控制。如果一棵樹更傾斜,那麼訪問二叉樹元素的時間複雜度就會增加。說一棵樹
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
8
想象一下,一個樹,看起來像這樣:
A
\
B
\
C
\
D
\
E
這是一個有效的二叉樹,但現在大多數操作是O(N),而不是Ø (lg n)。
4
爲確保log(n)搜索時間,您需要在每個分支處將下級節點的總數除以2。例如,如果您有線性樹,永遠不會從根分支到葉節點,那麼搜索時間將與鏈接列表中的線性一致。
1
一個非常不平衡的樹,例如一棵樹,其中所有節點都鏈接到左邊,這意味着您在查找最後一個節點之前仍然搜索每個節點,這根本不是樹的一點,也沒有任何好處通過鏈表。平衡樹使得搜索時間O(log(n))更好,而不是O(n)。
相關問題
- 1. 平衡二叉樹
- 2. 平衡二叉搜索樹
- 3. 不平衡二叉樹
- 4. 無法平衡二叉樹
- 5. 左平衡二叉樹
- 6. 二叉樹屬性 - 平衡
- 7. 平衡二叉搜索樹子樹
- 8. 平衡四叉樹
- 9. 這個平衡二叉樹的名字是什麼?
- 10. 使用foldr構建平衡二叉樹
- 11. 二叉樹中的平衡和數
- 12. 打印不平衡的二叉樹
- 13. 這個二叉樹可以平衡嗎?
- 14. 平衡二叉樹的索引函數
- 15. 如何平衡我的二叉樹
- 16. C++二叉樹類需要什麼
- 17. 樹或平衡二叉搜索樹來存儲字典?
- 18. 二叉搜索樹,確定要使用前置或後續使樹平衡
- 19. 爲什麼跳過列表內存局部性很差,但平衡樹很好?
- 20. 具有一個空子樹的二叉樹可以是平衡二叉樹嗎?如果是這樣,何時?
- 21. 展平二叉查找樹
- 22. 輸入來創建平衡二叉搜索樹
- 23. 從平衡二叉搜索樹中刪除
- 24. .NET Generic.Dictionary的實現是否使用平衡二叉樹?
- 25. 建立一個平衡二叉搜索樹
- 26. 使用Java創建平衡二叉樹時出錯
- 27. 不平衡二叉樹無法正常工作。 Node.js的
- 28. 使用sortedset的平衡二叉搜索樹
- 29. 將大樣本放在二叉搜索樹上(不平衡)
- 30. 平衡二叉搜索樹的分期複雜度