C++ 实现 AVL 平衡二叉搜索树详解

1、解密 AVL 树：平衡与效率的双重奏

前面我们已经学习了二叉搜索树。

最优情况下，二叉搜索树为完全二叉树 (或者接近完全二叉树)，其高度为：O(log2 N)

最差情况下，二叉搜索树退化为单支树 (或者类似单支)，其高度为：O(N/2)

这样如果是单链情况，那么大大降低了效率

所以出现了改进的搜索树->AVL 树（平衡二叉搜索树）

在 1962 年，俄罗斯数学家 G.M. Adelson-Velskii 和 E.M. Landis 提出了一种革命性的解决方案：他们发明了 AVL 树。通过在二叉搜索树插入新节点后，确保每个节点的左右子树高度差的绝对值不超过 1（即进行必要的树结构调整），这种方法能够有效控制树的高度，从而大幅度降低平均搜索长度。这个创新不仅解决了二叉搜索树在高频插入和删除操作中的性能瓶颈，也为平衡二叉树的发展奠定了基础，成为了数据结构领域的一个经典突破。

map 与 set 的底层实现也是 AVL 树或红黑树！

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

• 它的左右子树都是 AVL 树
• 左右子树高度之差 (简称平衡因子) 的绝对值不超过 1(-1 / 0 / 1 )

如果一棵二叉搜索树是高度平衡的，它就是 AVL 树。如果它有 n 个结点，其高度可保持在 O(log N)

搜索复杂度 O(log N)

通过每次插入删除的调整**(旋转)保证二叉树始终保持一个近乎完美的完全二叉树，规避了极端情况下二叉搜索树退化为单枝树的情况**

2、搭建 AVL 树：从零到自平衡的实现之路

2.1 树基打底：设计与框架构建

首先 AVL 树是在二叉搜索树的基础上进行改进，AVL 树节点中加入了：

• 平衡因子_bf：左右子树的高度差 right 子树高度 - left 子树高度 ，即左子树插入节点时_bf--，右子树插入节点时_bf++
• 父指针_parent：指向父节点的指针，为了可以回溯更新父节点的平衡因子

template<class K,class V> struct AVLTreeNode {
    //键值对 pair<K, V> _kv;
    //三叉链
    AVLTreeNode* _left;
    AVLTreeNode* _right;
    // 需要父亲指针 更新平衡因子
    AVLTreeNode* _parent;
    
     _bf;
    ( pair<K,V>& kv) :_kv(kv) ,_left() ,_right() ,_parent() ,_bf() {}
};

< ,  >   {
    
     Node = AVLTreeNode<K, V>;
:
    Node* _root = ;
};