面试题库 › 算法 / 大模型 › AVL 树的查找时间复杂度

AVL 树的查找时间复杂度

难度 ★☆☆在 1 场真实面经中被问到 方向:算法 / 大模型考点:树与二叉树

哪些公司问过

腾讯1

常见岗位:推荐搜索广告

答案要点

  1. 查找时间复杂度 O(log n),最坏情况也是 O(log n)
  2. 任意节点左右子树高度差不超过 1,树高约不超过 1.44·log2 n
  3. 普通 BST 有序插入会退化为链表,查找 O(n)
  4. 插入删除后通过 LL、RR、LR、RL 旋转恢复平衡,更新也是 O(log n)
  5. 与红黑树相比:AVL 更矮查找略快,但更新旋转更多,适合读多写少

易错点

面试官常见追问

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

相关面试题