GESP 八级 · GESP 202503 C++ 八级 第 22 题

在 $N$ 个节点的平衡二叉树中查找指定元素的最差时间复杂度为 $O(N)$。

分析时间复杂度时关注循环层数和每层迭代次数，递归算法则分析递归树。注意最坏/最好/平均情况的区别。

分析复杂度时注意外层循环和内层循环的关联。例如内外两层都到n的循环不一定是O(n²)，要看内层是否每次都在缩小。

【考点】平衡二叉树性质｜查找操作时间复杂度｜最坏情况分析

1. 🎯 考纲定位

考查 GESP 八级「数据结构」核心模块的平衡二叉树（AVL）性质与查找复杂度分析。命题人专盯那些能背结论却不懂平衡因子约束的考生——以为「最坏情况=退化成链表」，结果在 AVL 上栽跟头。