面试题库 › 客户端 › 红黑树的性质与插入过程

红黑树的性质与插入过程

难度 ★★★在 3 场真实面经中被问到 方向:客户端考点:树与二叉树

哪些公司问过

广和通1度小满1朝夕光年1

常见岗位:iOS、嵌入式软件、游戏客户端

答案要点

  1. 五条性质:非红即黑、根黑、空叶子黑、红节点子节点为黑、各路径黑高相同
  2. 性质保证最长路径不超过最短路径两倍,操作复杂度 O(log n)
  3. 新节点涂红,不改变黑高,只可能出现连续红节点
  4. 叔叔红则变色并上移;叔叔黑则旋转加变色,最多两次旋转
  5. 应用:C++ map/set、Java TreeMap、Linux 内核 CFS 调度等

易错点

面试官常见追问

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

相关面试题