24|二叉树基础(下):有了如此高效的散列表，为什么还需要二叉树?

[hfuuss]

二叉查找树最大的特点就是，支持动态数据集合的快速 插入、删除、查找操作。

[hfuuss]

除了插入、删除、查找操作之外，二叉查找树中还可以支持快速地查找最大节点和最小节点、前驱节点和后继节点。

[hfuuss]

特性，就是中序遍历二叉查找树，可以输出有序的数据序列，时间复杂度是O(n)，非常高效。因此，二 叉查找树也叫作二叉排序树。

[hfuuss]

解答开篇

我们在散列表那节中讲过，散列表的插入、删除、查找操作的时间复杂度可以做到常量级的O(1)，非常高效。而二叉查找树在比较平衡的情况下，插入、删除、 查找操作时间复杂度才是O(logn)，相对散列表，好像并没有什么优势，那我们为什么还要用二叉查找树呢? 我认为有下面几个原因: 第一，散列表中的数据是无序存储的，如果要输出有序的数据，需要先进行排序。而对于二叉查找树来说，我们只需要中序遍历，就可以在O(n)的时间复杂度 内，输出有序的数据序列。 第二，散列表扩容耗时很多，而且当遇到散列冲突时，性能不稳定，尽管二叉查找树的性能不稳定，但是在工程中，我们最常用的平衡二叉查找树的性能非常稳 定，时间复杂度稳定在O(logn)。 第三，笼统地来说，尽管散列表的查找等操作的时间复杂度是常量级的，但因为哈希冲突的存在，这个常量不一定比logn小，所以实际的查找速度可能不一定 比O(logn)快。加上哈希函数的耗时，也不一定就比平衡二叉查找树的效率高。 第四，散列表的构造比二叉查找树要复杂，需要考虑的东西很多。比如散列函数的设计、冲突解决办法、扩容、缩容等。平衡二叉查找树只需要考虑平衡性这一 个问题，而且这个问题的解决方案比较成熟、固定。 最后，为了避免过多的散列冲突，散列表装载因子不能太大，特别是基于开放寻址法解决冲突的散列表，不然会浪费一定的存储空间。 综合这几点，平衡二叉查找树在某些方面还是优于散列表的，所以，这两者的存在并不冲突。我们在实际的开发过程中，需要结合具体的需求来选择使用哪一 个。