常见树结构的种类、特点与应用场景
哪些公司问过
答案要点
- 二叉树每个节点最多两个孩子,遍历有前序、中序、后序、层序
- 二叉搜索树左小右大;AVL 严格平衡,红黑树近似平衡且调整更少
- 红黑树用于 Java TreeMap、HashMap 树化、C++ map
- 堆用于优先队列和 TopK;B+ 树用于数据库索引;Trie 用于前缀匹配
- 图分有向、无向、带权,用邻接矩阵或邻接表表示
易错点
- 把堆说成二叉搜索树,混淆两者的有序性质
- 认为红黑树是严格平衡的
- 说 HashMap 链表长度到 8 一定树化,忽略数组长度至少 64 的条件
- 把 B 树和 B+ 树的数据存放位置说反
面试官常见追问
- 红黑树的原理是什么?
- HashMap 为什么在链表过长时转红黑树?
- 数据库索引为什么用 B+ 树而不用红黑树?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- 二叉树的遍历142 场
- 平衡树的种类与区别:红黑树、AVL、B/B+ 树97 场
- 红黑树的原理与特点67 场
- 二叉树的最近公共祖先 LCA22 场
- 二叉树的最大深度17 场
- 二叉树的最大路径和15 场
- 对称二叉树(判断镜像)13 场
- 二叉树的 Z 字形层序遍历13 场
- 二叉树的直径8 场
- 二叉搜索树转双向链表7 场