从二叉树出发梳理常见的树结构
哪些公司问过
答案要点
- 二叉搜索树左小右大、中序有序,有序插入会退化为链表,查找变O(n)
- AVL严格平衡(高度差不超过1),查询快旋转多;红黑树近似平衡,修改代价更稳定
- B树多路降低树高、减少磁盘IO;B+树数据只在叶子且叶子链表相连,适合范围查询
- 专用树:堆(优先队列)、Trie(前缀匹配)、哈夫曼树(编码)、线段树(区间查询)
易错点
- 说红黑树是严格平衡,其实只保证最长路径不超过最短路径的两倍
- 把叶子链表说成B树的特性,它是B+树的
- 认为二叉搜索树查找总是O(log n),忽略退化情况
面试官常见追问
- B树和B+树有什么区别?MySQL为什么用B+树?
- 红黑树和AVL怎么选?
- 堆为什么用数组存?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- 二叉树的遍历142 场
- 平衡树的种类与区别:红黑树、AVL、B/B+ 树97 场
- 红黑树的原理与特点67 场
- 二叉树的最近公共祖先 LCA22 场
- 二叉树的最大深度17 场
- 二叉树的最大路径和15 场
- 对称二叉树(判断镜像)13 场
- 二叉树的 Z 字形层序遍历13 场
- 二叉树的直径8 场
- 二叉搜索树转双向链表7 场