AVL 树核心详解：从概念到 C++ 手撕实现

AVL 树核心详解

你是否曾在写算法时，用二叉搜索树（BST）存数据却遭遇'超时'暴击？明明理论复杂度是 O(logn)，偏偏插入一串有序数据后，树直接退化成链表，查询效率暴跌到 O(n)？这背后的元凶，正是 BST 无法自我平衡的结构性缺陷。而 AVL 树，就是为破解这个痛点而生的平衡大师。

它不仅是首个严格平衡的二叉搜索树，每一个设计细节都藏着精妙的逻辑：为什么平衡因子要选高度差≤1 而非高度相等？旋转操作看似复杂，实则是局部修复全局平衡的贪心策略。这篇内容我们将挖透 AVL 树的底层逻辑，从诞生的根源到旋转与平衡因子的本质，最终让你明白——AVL 树不仅是一种数据结构，更是一套用最小代价解决失衡问题的方法论。

AVL 树的概念

AVL 树是二叉平衡搜索树的一种（红黑树也是）。跟普通二叉搜索树的区别在于，极端场景下 BST 会退化成类似链表的结构，而 AVL 树则不会。

一棵 AVL 树或者是空树，或者是具有以下性质的二叉搜索树：

它的左右子树都是 AVL 树。
左右子树高度之差（简称平衡因子）的绝对值不超过 1（即 -1、0 或 1）。

每个节点都有它的平衡因子。AVL 树增删查改的时间复杂度都是 O(logn)，其中 n 是元素个数。

AVL 树的模拟实现

虽然 AVL 树和红黑树在手撕代码中考察频率不如基础结构高，但理解其整体模拟实现的思想以及旋转的手撕过程非常关键。这里我们重点看 C++ 的实现细节。

节点结构与插入逻辑

首先定义节点，需要存储键值对、左右孩子指针、父指针以及平衡因子 _bf。

template<class K, class V>
struct AVLTreeNode {
    pair<K, V> _kv;
    AVLTreeNode<K, V>* _left;
    AVLTreeNode<K, V>* _right;
    AVLTreeNode<K, V>* _parent;
    int _bf; // 平衡因子 balance factor

    AVLTreeNode(const pair<K, V>& kv)
        :_kv(kv), _left(nullptr), _right(nullptr), _parent(nullptr), _bf(0) {}
};

插入时的核心难点在于更新平衡因子和必要的旋转。插入完成后，我们需要自底向上更新祖先节点的平衡因子。

template<class K, class V>
class AVLTree {
    typedef AVLTreeNode<K, V> Node;
public:
    bool Insert(const pair<K, V>& kv) {
         (_root == ) {
            _root =  (kv);
             ;
        }

        Node* parent = ;
        Node* cur = _root;
         (cur) {
             (cur->_kv.first < kv.first) {
                parent = cur;
                cur = cur->_right;
            }   (cur->_kv.first > kv.first) {
                parent = cur;
                cur = cur->_left;
            }  {
                 ; 
            }
        }

        cur =  (kv);
         (parent->_kv.first < kv.first) {
            parent->_right = cur;
        }  {
            parent->_left = cur;
        }
        cur->_parent = parent;

        
         (parent) {
             (cur == parent->_left) {
                parent->_bf--;
            }  {
                parent->_bf++;
            }

             (parent->_bf == ) {
                
                ;
            }   (parent->_bf ==  || parent->_bf == ) {
                
                cur = parent;
                parent = parent->_parent;
            }   (parent->_bf ==  || parent->_bf == ) {
                
                 (parent->_bf ==  && cur->_bf == ) {
                    (parent); 
                }   (parent->_bf ==  && cur->_bf == ) {
                    (parent); 
                }   (parent->_bf ==  && cur->_bf == ) {
                    (parent); 
                }   (parent->_bf ==  && cur->_bf == ) {
                    (parent); 
                }
                ;
            }  {
                (); 
            }
        }
         ;
    }

AVL 树核心详解：从概念到 C++ 手撕实现