数据结构：AVL 树的原理与实现

1. AVL 树

1.1 AVL 的概念

AVL 树可以是一个空树。 它的左右子树都是 AVL 树，且左右子树的高度差的绝对值不超过 1。AVL 树是一种高度平衡的搜索二叉树，通过控制高度差去控制平衡。 AVL 树整体结点数量和分布和完全二叉树类似，高度可以控制在 logN，那么增删查改的效率也可以控制在 O(logN)，相比二叉搜索树有了本质的提升。

1.2 平衡因子

结点的平衡因子=右子树的高度减去左子树的高度，也就是说任何结点的平衡因子等于 0/1/-1，AVL 树并不是必须要平衡因子，但是有了平衡因子可以更方便我们去进行观察和控制树是否平衡，就像一个风向标一样。 为什么 AVL 树是高度平衡搜索二叉树，要求高度差不超过 1，而不是高度差是 0 呢？ 因为例如二和四个结点无法达到 0.

2. AVL 树的实现

2.1 AVL 树的结构

template <class K, class V>
struct AVLTreeNode {
    // 需要 parent 指针，后续更新平衡因子可以看到
    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:
    // ...
private:
    Node* _root = nullptr;
};

2.2 AVL 树的插入

bool Insert(const pair<K, V>& kv) {
    if (_root == nullptr) {
        _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 == ) {
            
            ;
        }  {
            ();
        }
    }
     ;
}