AVL 树的查找时间复杂度
哪些公司问过
答案要点
- 查找时间复杂度 O(log n),最坏情况也是 O(log n)
- 任意节点左右子树高度差不超过 1,树高约不超过 1.44·log2 n
- 普通 BST 有序插入会退化为链表,查找 O(n)
- 插入删除后通过 LL、RR、LR、RL 旋转恢复平衡,更新也是 O(log n)
- 与红黑树相比:AVL 更矮查找略快,但更新旋转更多,适合读多写少
易错点
- 把 AVL 的最坏情况说成 O(n),混淆了普通二叉搜索树
- 说 AVL 插入和删除都只需一次旋转
- 说不出树高为何是对数级
面试官常见追问
- AVL 插入后最多要几次旋转?
- 为什么 std::map 用红黑树而不是 AVL?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- 二叉树的遍历142 场
- 平衡树的种类与区别:红黑树、AVL、B/B+ 树97 场
- 红黑树的原理与特点67 场
- 二叉树的最近公共祖先 LCA22 场
- 二叉树的最大深度17 场
- 二叉树的最大路径和15 场
- 对称二叉树(判断镜像)13 场
- 二叉树的 Z 字形层序遍历13 场
- 二叉树的直径8 场
- 二叉搜索树转双向链表7 场