C++实战：从二叉排序树到AVL树的完整实现与优化

1. 二叉排序树平衡树的起点二叉排序树BST是理解AVL树的基础它就像图书馆里按照编号排列的书架。每本书都有固定位置——比它编号小的放在左边大的放在右边。我当年第一次实现BST时曾犯过把所有节点都插到右子树的错误结果树退化成链表查找效率从O(log n)降到了O(n)。BST的核心规则很简单左子树所有节点值 根节点值右子树所有节点值 根节点值左右子树也是BST用C定义节点结构时我习惯加个构造函数初始化指针struct BSTNode { int val; BSTNode *left, *right; BSTNode(int x) : val(x), left(nullptr), right(nullptr) {} };查找操作就像玩猜数字游戏从根节点开始比较小了往左大了往右。递归实现只要4行代码bool search(BSTNode* root, int target) { if (!root) return false; if (target root-val) return true; return search(target root-val ? root-left : root-right, target); }插入操作有个坑点要传指针的引用。我第一次写的时候漏了结果插入的节点根本没挂到树上void insert(BSTNode* root, int val) { if (!root) root new BSTNode(val); else insert(val root-val ? root-left : root-right, val); }BST的中序遍历会产生有序序列这个特性我在实际项目中经常用来实现排行榜功能。不过当数据有序插入时BST会严重倾斜这时候就需要AVL树来拯救了。2. AVL树的平衡之道AVL树就像严格自律的体操运动员始终保持左右平衡。它的定义中有两个关键点左右子树高度差不超过1每个子树也都是AVL树平衡因子是AVL树的核心概念计算起来很简单int getHeight(TreeNode* node) { return node ? max(getHeight(node-left), getHeight(node-right)) 1 : 0; } int balanceFactor(TreeNode* node) { return getHeight(node-left) - getHeight(node-right); }我在实现时发现频繁计算高度很耗性能于是改为在节点结构中存储高度struct AVLNode { int val, height; AVLNode *left, *right; AVLNode(int x) : val(x), height(1), left(nullptr), right(nullptr) {} };更新高度的操作要放在每次插入和旋转后void updateHeight(AVLNode* node) { node-height max(getHeight(node-left), getHeight(node-right)) 1; }四种旋转操作是AVL树的精华所在。记得第一次实现LL旋转时我搞混了指针指向结果把树转成了死循环。正确的LL旋转应该像这样AVLNode* leftRotate(AVLNode* x) { AVLNode* y x-right; x-right y-left; y-left x; updateHeight(x); updateHeight(y); return y; }3. 从BST到AVL的完整转换把BST升级成AVL树的关键在于插入后的平衡调整。这个过程就像搭积木每次插入后都要检查是否失衡。我习惯用递归实现从下往上调整AVLNode* insert(AVLNode* root, int val) { if (!root) return new AVLNode(val); if (val root-val) root-left insert(root-left, val); else if (val root-val) root-right insert(root-right, val); else return root; // 重复值 updateHeight(root); int bf balanceFactor(root); // LL情况 if (bf 1 val root-left-val) return rightRotate(root); // RR情况 if (bf -1 val root-right-val) return leftRotate(root); // LR情况 if (bf 1 val root-left-val) { root-left leftRotate(root-left); return rightRotate(root); } // RL情况 if (bf -1 val root-right-val) { root-right rightRotate(root-right); return leftRotate(root); } return root; }删除操作更复杂些需要先按BST规则删除节点再平衡。我建议先实现查找最小节点的辅助函数AVLNode* findMin(AVLNode* node) { while (node-left) node node-left; return node; }4. 性能优化实战技巧在实际项目中我发现AVL树有几点可以优化高度缓存像前面提到的存储高度比实时计算快得多非递归实现对于深度较大的树递归可能导致栈溢出内存池频繁的节点操作可以用内存池优化非递归插入的实现示例AVLNode* insertIterative(AVLNode* root, int val) { stackAVLNode** path; AVLNode** curr root; while (*curr) { path.push(curr); if (val (*curr)-val) curr (*curr)-left; else if (val (*curr)-val) curr (*curr)-right; else return root; // 重复值 } *curr new AVLNode(val); while (!path.empty()) { AVLNode** node path.top(); path.pop(); updateHeight(*node); *node rebalance(*node); } return root; }另一个优化点是实现批量插入。单次插入的AVL树效率是O(n log n)但如果我们预先排序数据可以用O(n)时间构建AVLNode* buildBalanced(vectorint nums, int start, int end) { if (start end) return nullptr; int mid start (end - start) / 2; AVLNode* root new AVLNode(nums[mid]); root-left buildBalanced(nums, start, mid - 1); root-right buildBalanced(nums, mid 1, end); updateHeight(root); return root; }最后给树加上迭代器可以实现STL风格的遍历这在项目集成时特别有用class AVLIterator { stackAVLNode* s; public: AVLIterator(AVLNode* root) { while (root) { s.push(root); root root-left; } } bool hasNext() { return !s.empty(); } int next() { AVLNode* node s.top(); s.pop(); int val node-val; node node-right; while (node) { s.push(node); node node-left; } return val; } };