1回答

liuyubobobo

2021-07-11

已采纳

普通的二分搜索树，因为可能退化，所以最差的时间复杂度是 O(n) 的。但是，如果是平衡的二分搜索树的话，比如这个课程后续介绍的 AVL 树或者红黑树的话，是的，所有的时间复杂度都是 O(logn) 级别的。

但是，如果只是用于优先队列的场景的话，使用堆实现会比使用 AVL 树或者红黑树实现，具体的性能快一些，这是因为堆不牵扯旋转等维护平衡的操作，且堆本身是绝对平衡的。虽然他们的理论时间复杂度的级别是一样的，但是具体的性能有差异。

其实这种情况在算法的世界非常多。不要说复杂度一样了，就算复杂度更优，也有可能实际性能更差。比如非比较排序虽然理论复杂度是 O(n) 的，但是在一些情况（甚至是绝大多数情况），实际性能不如 O(nlogn) 的排序；再比如哈希表，虽然各个操作理论复杂度是 O(1) 的，但是在数据分布特别稀疏，不均匀，或者数据规模不够大的情况下，可能不如各个复杂度为 O(logn) 的基于红黑树的集合或者映射。

但是，是的，使用红黑树或者 AVL 树等平衡的二分搜树，完全可以作为优先队列使用。

继续加油！：）

0

1

散落满天的回忆

谢谢老师解答

2021-07-11

共1条回复