二叉搜索树的定义、性质与操作复杂度
哪些公司问过
答案要点
- 左子树所有节点小于根、右子树所有节点大于根,左右子树递归满足
- 中序遍历结果为升序序列
- 查找次数等于目标深度,平衡时平均 O(log n),退化成链时最坏 O(n)
- 删除分叶子、单孩子、双孩子三种情况,双孩子用后继或前驱替换
- AVL、红黑树等平衡树通过旋转保证 O(log n),支持范围查询
易错点
- 只说平均 O(log n),忽略退化成链表的最坏情况 O(n)
- 判断二叉搜索树时只比较父子节点,忽略整棵子树的约束
- 删除有两个孩子的节点时直接删除,破坏树结构
- 把二叉搜索树和堆的性质混淆
面试官常见追问
- 红黑树、B 树、B+ 树的区别是什么?
- AVL 树和红黑树怎么选?
- 如何判断一棵树是不是二叉搜索树?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- 二叉树的遍历142 场
- 平衡树的种类与区别:红黑树、AVL、B/B+ 树97 场
- 红黑树的原理与特点67 场
- 二叉树的最近公共祖先 LCA22 场
- 二叉树的最大深度17 场
- 二叉树的最大路径和15 场
- 对称二叉树(判断镜像)13 场
- 二叉树的 Z 字形层序遍历13 场
- 二叉树的直径8 场
- 二叉搜索树转双向链表7 场