数据结构中堆排序的步骤，查找、插入、删除都很快的数据结构（散列表vs红黑树vs跳表）

2023-09-24 阅读 16 评论 0

摘要：散列表散列表的插入、删除、查找操作的时间复杂度可以做到常量级的 O(1)，非常高效。平衡二叉查找树（红黑树）二叉查找树在比较平衡的情况下（红黑树是一种平衡二叉树），插入、删除、查找操作时间复杂度是 O(logn)。跳表跳表ÿ

散列表

散列表的插入、删除、查找操作的时间复杂度可以做到常量级的 O(1)，非常高效。
哈希表

平衡二叉查找树（红黑树）

二叉查找树在比较平衡的情况下（红黑树是一种平衡二叉树），插入、删除、查找操作时间复杂度是 O(logn)。

跳表

跳表，插入、删除、查找操作时间复杂度是 O(logn)。

散列表 vs 二叉查找树

相对散列表，二叉查找树好像并没有什么优势，那我们为什么还要用二叉查找树呢？

第一，散列表中的数据是无序存储的，如果要输出有序的数据，需要先进行排序。而对于二叉查找树来说，我们只需要中序遍历，就可以在 O(n) 的时间复杂度内，输出有序的数据序列。

数据结构中堆排序的步骤，第二，散列表扩容耗时很多，而且当遇到散列冲突时，性能不稳定，尽管二叉查找树的性能不稳定，但是在工程中，我们最常用的平衡二叉查找树的性能非常稳定，时间复杂度稳定在 O(logn)。
比如：红黑树的插入、删除、查找各种操作性能都比较稳定。对于工程应用来说，要面对各种异常情况，为了支撑这种工业级的应用，我们更倾向于这种性能稳定的平衡二叉查找树

第三，笼统地来说，尽管散列表的查找等操作的时间复杂度是常量级的，但因为哈希冲突的存在，这个常量不一定比 logn 小，所以实际的查找速度可能不一定比 O(logn) 快。加上哈希函数的耗时，也不一定就比平衡二叉查找树的效率高。

第四，散列表的构造比二叉查找树要复杂，需要考虑的东西很多。比如散列函数的设计、冲突解决办法、扩容、缩容等。平衡二叉查找树只需要考虑平衡性这一个问题，而且这个问题的解决方案比较成熟、固定。