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 树中最重要的要进行更新平衡因子,也就是 。




















