进阶数据结构：AVL 树

AVL 相关概念：

AVL 树是由二叉搜索树加上一定的限制而形成的树。AVL 树的左右子树都是 AVL 树，且左右子树的高度差的绝对值不超过 1。AVL 树是一颗高度平衡搜索二叉树，通过控制高度差去控制平衡。

AVL 树得名于它的发明者 G. M. Adelson-Velsky 和 E. M. Landis，他们在 1962 年的论文《An algorithm for the organization of information》中发表了它。

AVL 树引入了平衡因子这个概念，每个节点都有平衡因子，任何节点的平衡因子等于右子树的高度减去左子树的高度。也就是说 AVL 树的每个节点的平衡因子等于 1/-1/0。引入平衡因子能让我们更方便去观察和控制树是否平衡。

AVL 因为它的平衡条件，使得我们树的高度可以控制在 logN，那么搜索的时间复杂度也就是 logN，相比于二叉搜索树有了质的提升。

AVL 树的结构

#include <utility>
using namespace std;

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; // 平衡因子

    AVLTreeNode(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;
};

Insert

我们要插入一个值在 AVL 树中的前半过程和二叉搜索树一样，都是先找到要插入的位置然后插入。插入后就有一点不一样了，在 AVL 树中最重要的要进行更新平衡因子，也就是 。