1
對不起，如果這是一個愚蠢的問題。我聽說AVL樹有O（log（n））用於搜索，但我不明白它總是如何保證log（n）搜索。AVL樹如何保證O（log（n））全天搜索
A
回答
1
這是因爲AVL樹是一個自平衡樹，所有節點的子樹之間始終有最多1級的差異。 BST的高度影響搜索時間。想象一下，如果你有一個具有n個節點線性形狀的BST。它的高度不是log（n）。在這種情況下，搜索時間複雜度是O（n）。（不平衡樹的最壞情況）。換句話說，它意味着我們也可以通過將樹的高度控制爲log（n）來生成一個保證log（n）搜索時間的樹。
相關問題
- 1. O（log n）中的二叉搜索樹？
- 2. 圖形搜索O（log（N）（N + M）
- 3. AVL搜索樹
- 4. 時間複雜度 - O（n^2）到O（n log n）搜索
- 5. Java - AVL樹搜索
- 6. 是log（n！）= O（（log（n））^ 2）？
- 7. 如何計算O（Log（N））？
- 8. 你如何看出O（log n）和O（n log n）之間的差異？
- 9. 大O符號 - O（n日誌（N））對O（的log（n^2））
- 10. 爲什麼O（N日誌N）構建二進制搜索樹？
- 11. 證明log（n！）是Ω（n log（n））
- 12. floor（√2n）的O（log log n）算法？
- 13. 如何在時間O（log（n））中搜索一個列表的算法？
- 14. 合併n個AVL樹
- 15. C++ AVL二叉搜索樹問題
- 16. 如何證明$ D _ {\ frac {1} {2} - \ epsilon}^{uniform}（f）= n + O（log \ epsilon）$？
- 17. 時間複雜度O（N日誌（log n）的）+ N O（L）
- 18. 與log（n）相比，log（n^2）的大O是什麼？
- 19. 搜索在N叉樹
- 20. 複雜度O（log（n））是否等於O（sqrt（n））？
- 21. 爲什麼avl樹比紅黑樹搜索更快？
- 22. 二元搜索樹通過旋轉平衡（在AVL樹上）
- 23. 完整的二叉搜索樹和AVL樹的區別？
- 24. 建立AVL樹的二進制搜索樹
- 25. 從小於O（log（n））運行時間的排序數組中搜索
- 26. 證明最大（O（f（n）），O（g（n）））= O（max（f（n），g（n））
- 27. O（n）中的2鍵搜索算法
- 28. 在C中的O（N）中搜索T
- 29. O（log（n））中的優先級驗證器實現
- 30. 如何搜索列表框中的相冊並將其連接到AVL樹或二進制搜索樹？ C＃