哈希表
查找某个元素是否
存在过
单次 CRUD 效率：
O(1)
~
O(n)
为了避免冲突，可能会剧烈增加的空间复杂度：
vol >> O(n)
栈
适用于
回溯
适用于需要依赖
上一个
历史信息的查询
队列
单调队列
维护一个最大、次大的窗口
优先队列（大小顶堆）
适用于求“
第k大
”问题：
O(k*logn)
适用于求
最大的k个元素
问题：
O(k*logn)
对于局部排序问题通常比快排更快
单次 CRUD 效率：
O(logn)
快排的时间复杂度：
O(nlogn)
~
O(n^2)
搜索树
适用于快速索引、范围索引
单次查询
平凡二叉搜索树 → AVL 树 → 红黑树
范围查询
B+树、BW树
红黑树