面试题库 › C++ / 后端 › 红黑树的原理与特点

红黑树的原理与特点

难度 ★★☆在 67 场真实面经中被问到 方向:C++ / 后端考点:树与二叉树

哪些公司问过

百度8腾讯7字节跳动6深信服5奇安信3美团2华为2拼多多2蚂蚁集团2恒生电子2海康威视2吉比特2

常见岗位:C/C++ 软件开发、Java 后端、C++ 后端、C++ / Qt 客户端、嵌入式软件

答案要点

  1. 五条性质:节点红或黑;根黑;叶子(NIL)黑;红节点的孩子都是黑;任一节点到其叶子的路径黑节点数相同
  2. 性质 4 和 5 保证最长路径不超过最短路径的 2 倍,查找、插入、删除 O(log n)
  3. 插入修复:新节点染红;父红时看叔叔:叔叔红则变色并向上,叔叔黑则旋转加变色(最多 2 次旋转)
  4. 删除比插入复杂,最多 3 次旋转
  5. 优点:增删旋转少、综合性能稳定(STL map/set、Java TreeMap);缺点:实现复杂、查找略慢于 AVL

易错点

面试官常见追问

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

相关面试题