红黑树和 AVL 树各有什么特点？
What are the characteristics of red-black and AVL trees?
两者都是自平衡二叉搜索树：AVL 更严格平衡，查找更快但插入删除旋转多；红黑树放宽平衡（黑高平衡），插入删除开销更低，因此更常用于系统级数据结构如 C++ map。
Both are self-balancing BSTs: AVL is stricter (faster lookups, more rotations), while red-black relaxes balance for cheaper insertions/deletions, so it is common in system structures like C++ maps.
难度 专业 · 适合 初中(12-15)
CC BY 4.0 · 已核验 · Verified 2026-08-23 · 2 条独立证据
来源 · Source
Cormen, Leiserson, Rivest, Stein,《Introduction to Algorithms》第3版,MIT Press,2009
T. H. Cormen et al., Introduction to Algorithms, 3rd ed., MIT Press, 2009
独立核验依据 · Independent verification: 核验依据 2 ISBN 978-0-262-04630-5
#树 #平衡
哈希表是如何实现 O(1) 平均查找的？
How does a hash table achieve O(1) average lookup?
哈希函数把键映射到桶下标，理想情况下不同键均匀分布到不同桶，直接定位；冲突时常用链地址法或开放寻址法处理，负载因子过高会触发扩容再哈希。
A hash function maps keys to bucket indices so the right bucket is found directly; collisions are handled by chaining or open addressing, and high load triggers resizing and rehashing.
难度 专业 · 适合 初中(12-15)
CC BY 4.0 · 已核验 · Verified 2026-08-23 · 2 条独立证据
来源 · Source
Cormen, Leiserson, Rivest, Stein,《Introduction to Algorithms》第3版,MIT Press,2009
T. H. Cormen et al., Introduction to Algorithms, 3rd ed., MIT Press, 2009
独立核验依据 · Independent verification: 核验依据 2 ISBN 978-0-262-04630-5
#数据结构 #哈希
布隆过滤器是什么，有什么取舍？
What is a Bloom filter and what are its trade-offs?
布隆过滤器用多个哈希函数和位数组判断元素是否可能在集合中：它绝不会漏报，但有一定误判率，且不支持删除，优点是空间开销极小。
A Bloom filter uses several hash functions over a bit array to test membership: it never yields false negatives but has a tunable false-positive rate and cannot delete, trading accuracy for tiny space.
难度 专业 · 适合 大众
CC BY 4.0 · 来源待核验 · Source pending review
来源 · Source
出处备注：此条未指向带版次的可引用著作（通识性内容、机构文件或未展开的英文书名），本库不提供独立书目出处；如需精确引用，需由编辑补全具体篇目与版次。
论文 Bloom 1970
Bloom 1970 paper
#概率 #数据结构
斐波那契堆为什么特别适合用来实现 Dijkstra 算法？
Why is a Fibonacci heap especially suited to Dijkstra's algorithm?
Dijkstra 需要大量“降低某个键的优先级”和“取最小”。斐波那契堆把插入和减键都做到摊还 O(1)，只在抽取最小值时才做昂贵的合并，使得整体最短路运行的摊还复杂度降到 O(E + V log V)，优于二叉堆。
Dijkstra needs many 'decrease-key' and 'extract-min' ops. A Fibonacci heap does insert and decrease-key in amortized O(1) and only pays heavily at extract-min, bringing the shortest-path cost to O(E + V log V)—better than a binary heap.
难度 专业 · 适合 高中(15-18)
CC BY 4.0 · 已核验 · Verified 2026-08-23 · 2 条独立证据
来源 · Source
Cormen, Leiserson, Rivest, Stein,《Introduction to Algorithms》第3版,MIT Press,2009
T. H. Cormen et al., Introduction to Algorithms, 3rd ed., MIT Press, 2009
独立核验依据 · Independent verification: 核验依据 2 ISBN 978-0-262-04630-5
#斐波那契堆 #Dijkstra
跳表（skip list）是怎么用“概率”换来平衡的？
How does a skip list use probability to achieve balance?
跳表是带多层索引的有序链表：每个节点以固定概率（如 1/2）再向上晋升一层，形成稀疏到稠密的多级指针。查找时从顶层大幅跳跃、逐层下降，期望代价 O(log n)，且不需要像平衡树那样做复杂的旋转。
A skip list is an ordered linked list with multi-level indexes: each node is promoted one level up with a fixed probability (e.g. 1/2), forming sparse-to-dense pointers. Search jumps from the top and descends, costing expected O(log n) without the rotations of balanced trees.
难度 进阶 · 适合 小学高段(9-12)
CC BY 4.0 · 已核验 · Verified 2026-08-23 · 2 条独立证据
来源 · Source
Cormen, Leiserson, Rivest, Stein,《Introduction to Algorithms》第3版,MIT Press,2009
T. H. Cormen et al., Introduction to Algorithms, 3rd ed., MIT Press, 2009
独立核验依据 · Independent verification: 核验依据 2 ISBN 978-0-262-04630-5
#跳表 #概率
堆和优先队列有什么关系？
What is the relationship between a heap and a priority queue?
优先队列是一种抽象数据类型，堆（通常是二叉堆）是其高效实现：插入和取最值都能在 O(log n) 完成，常用于任务调度和 Dijkstra。
A priority queue is an ADT, and a heap (usually binary) is its efficient implementation: insert and extract-min run in O(log n), used in scheduling and Dijkstra.
难度 进阶 · 适合 高中(15-18)
CC BY 4.0 · 已核验 · Verified 2026-08-23 · 2 条独立证据
来源 · Source
Cormen, Leiserson, Rivest, Stein,《Introduction to Algorithms》第3版,MIT Press,2009
T. H. Cormen et al., Introduction to Algorithms, 3rd ed., MIT Press, 2009
独立核验依据 · Independent verification: 核验依据 2 ISBN 978-0-262-04630-5
#数据结构 #堆