面试题库 › C++ / 后端 › map 的底层实现:为什么用红黑树

map 的底层实现:为什么用红黑树

难度 ★★☆在 47 场真实面经中被问到 方向:C++ / 后端考点:STL容器与算法

哪些公司问过

腾讯4深信服4字节跳动3网易3恒生电子3百度2大华1地平线1美团1

常见岗位:C/C++ 软件开发、Java 后端、推理部署与加速、C++ 后端、C++ / Qt 客户端

答案要点

  1. std::map 底层是红黑树:查找、插入、删除 O(log n),按键有序,支持范围查询
  2. 需要有序,所以不用哈希表;插入最多 2 次旋转、删除最多 3 次,写操作比 AVL 友好
  3. 红黑树有确定性的 O(log n) 最坏保证,跳表是概率性的
  4. B 树为磁盘优化,内存中用二叉树更简单
  5. unordered_map 是哈希表:平均 O(1),无序,最坏 O(n)

易错点

面试官常见追问

完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。

相关面试题