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＃