面试真题

结论：map底层红黑树，有序、查找O(log n)；unordered_map底层哈希表，无序、平均O(1)。红黑树弱平衡，AVL强平衡。要点：map元素按key比较排序，支持范围查询，空间开销每个节点含颜色等；unordered_map需哈希函数，可能有冲突，最坏O(n)；红黑树插入删除最多2次旋转，AVL要求左右子树高差≤1，插入删除可能多次旋转，查找稍快但维护成本高；适用：需有序遍历用map，需高性能查找用unordered_map。