AVL 树是一种自平衡二叉搜索树，通过维护节点的平衡因子（左右子树高度差绝对值不超过 1）确保查找效率稳定在 O(logN)。详细讲解了 AVL 树的基本性质、插入操作中的旋转调整策略（左单旋、右单旋、左右双旋、右左双旋）以及平衡因子的更新逻辑。内容涵盖构造函数、拷贝构造、析构函数、查找及插入等核心功能的 C++ 模拟实现，并提供了完整的代码示例。
普通二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序，二叉搜索树将退化为单支树，查找元素相当于在顺序表中搜索元素，效率低下。
AVL 树就可以解决上述问题，让搜索树的查找效率在任何情况下都能稳定是 O(logN)。
AVL 树解决上述问题的方法是：保证每个结点的左右子树高度之差的绝对值不超过 1。这样就能保证树中的节点分布接近满二叉树，高度非常接近 logN（N 为树中节点的个数），进而让一次查找的效率为 O(logN)。
为什么是保证每个结点的左右子树高度之差的绝对值不超过 1，而不是保证左右子树高度一样呢？其实很简单：因为在一些情况下绝对不可能做到左右子树高度一样。
综上，一棵 AVL 树或者是空树，或者是具有以下性质的二叉搜索树：
创建两个文件，一个头文件 AVLTree.hpp，一个源文件 test.cpp。
【因为模板的声明和定义不能分处于不同的文件中，所以把成员函数的声明和定义放在了同一个文件 AVLTree.hpp 中】
AVLTree.hpp：存放包含的头文件，命名空间的定义，成员函数和命名空间中的函数的定义test.cpp：存放 main 函数，以及测试代码实现 AVL 树最主要的就是保证树中节点的左右子树高度差不超过 1。而维护这一条件的方法并不是唯一的，我使用的是平衡因子来维护。
平衡因子是每个节点都有的，它的值就是这个节点的左右子树高度之差（一般是右子树高度 - 左子树高度）。
构造函数没什么好说的，默认构造就行了。
AVLTree():_root(nullptr){ }
拷贝构造：因为节点都是从堆区 new 出来的，所以要深拷贝。
使用递归实现深拷贝：因为拷贝构造不能有多余的参数，但是递归函数又必须使用参数记录信息。
然后在拷贝构造里面调用一下这个函数就行了。
AVLTree(const AVLTree& obj){ _root = Copy(obj._root, nullptr); }
交换两颗二叉搜索树的本质就是交换两颗数的资源（数据），而它们的资源都是从堆区申请来的，然后用指针指向这些资源。
并不是把资源存储在了二叉搜索树对象中。
所以资源交换很简单，直接交换_root 指针的指向即可。
void Swap(AVLTree& obj){ std::swap(_root, obj._root); }
赋值运算符重载
AVLTree& operator=(AVLTree obj){ this->Swap(obj); return *this; }
为什么上面的两句代码就可以完成深拷贝呢？这是因为使用了传值传参，会在传参之前调用拷贝构造，再把拷贝构造出的临时对象作为参数传递进去。赋值运算符的左操作数，this 再与传入的临时对象 obj 交换，就直接完成了拷贝。在函数结束之后，存储在栈区的 obj 再函数结束之后，obj 生命周期结束，obj 调用析构函数，把指向的从this 那里交换来的不需要的空间销毁。
使用递归遍历，把所有从堆区申请的节点都释放掉：因为析构函数不能有多余的参数，但是递归函数又必须使用参数记录信息，所以再封装一个成员函数，专门用来递归释放。
然后在拷贝构造里面调用一下这个函数就行了。
~AVLTree(){ Destroy(_root); _root = nullptr; }
具体流程：从根节点开始，将目标值（传入的 key）与当前节点的 key 进行比较。如果目标值小于当前节点值，则在左子树中继续查找；如果目标值大于当前节点值，则在右子树中继续查找。这个过程一直进行，直到找到与目标值或者到达空节点为止。
把上述过程转成代码：
Node* Find(const T& data){ Node* cur = _root; while(cur){ if(data < cur->_key) cur = cur->_left; else if(data > cur->_key) cur = cur->_right; else return cur; } return nullptr; }
AVL 树就是在二叉搜索树的基础上引入了平衡因子，因此 AVL 树也可以看成是二叉搜索树。
那么 AVL 树的插入过程可以分为两步：
因为新节点一定是插在叶子节点或者只有一个孩子节点的节点上，所以插入节点后一定会影响新节点的父亲节点的平衡因子，可能会影响祖先节点。
插入节点后具体分以下 3 种情况：
其实也简单：就是把原来的 parent 当做新的 cur，把 parent 的父节点作为新的 parent。再判断新的 cur 是父亲节点的左还是右，据此再更新新的 parent 的平衡因子。
即：
cur = parent; parent = parent->_parent;
// 因为以之前的 parent 为根的子树，高度增加了 1
// 右因为平衡因子=右子树高度 - 左子树高度
if(cur == parent->_left){ parent->_bf--; }
else{ parent->_bf++; }
然后，再重复判断一下新的 parent 的平衡因子的 3 种情况，进行处理：
旋转分以下 4 种：
所有的需要左单旋的情况，都可以画成下图的抽象图。
具体情况描述：
此时就使用左单旋：把（下图中的）PRL 链接在 parent 的右子树上，再把 parent 连接在 PR 的左子树上，把 PR 作为这颗子树新的根。
这样就可以做到：在不违反搜索树规则（所有左子树上的值<根<右子树）的基础上，尽可能地让树平衡。
将上述过程转换成代码：
void RotateL(Node*& parent){ Node* subR = parent->_right; Node* subRL = subR->_left; parent->_right = subRL; if(subRL) subRL->_parent = parent; subR->_left = parent; Node* pp = parent->_parent; parent->_parent = subR; if(parent->_parent == nullptr) _root = subR; else{ if(pp->_left == parent) pp->_left = subR; else pp->_right = subR; } subR->_parent = pp; }
所有的需要右单旋的情况，都可以画成下图的抽象图。
具体情况描述：
此时就使用右单旋：把（下图中的）PLR 链接在 parent 的左子树上，再把 parent 连接在 PL 的右子树上，把 PL 作为这颗子树新的根。
将上述过程转换成代码：
void RotateR(Node*& parent){ Node* subL = parent->_left; Node* subLR = subL->_right; parent->_left = subLR; if(subLR) subLR->_parent = parent; subL->_right = parent; Node* pp = parent->_parent; parent->_parent = subL; if(parent->_parent == nullptr) _root = subL; else{ if(pp->_left == parent) pp->_left = subL; else pp->_right = subL; } subL->_parent = pp; }
所有的需要左右双旋的情况，都可以画成下图的抽象图。
具体情况描述：
此时使用一次单旋，是解决不了的，旋了之后还是有平衡因子为 2/-2 的节点。但是如果我们对 PL 进行左单旋之后，就可以发现可以对 parent 使用右旋来使树，在不违反搜索树规则的基础上，尽可能地接近平衡。
即：
RotateL(parent->_left);
RotateR(parent);
所有的需要右左双旋的情况，都可以画成下图的抽象图。
具体情况描述：
此时使用一次单旋，是解决不了的，旋了之后还是有平衡因子为 2/-2 的节点。但是如果我们对 PR 进行右单旋之后，就可以发现可以对 parent 使用左单旋来使树，在不违反搜索树规则的基础上，尽可能地接近平衡。
即：
RotateR(parent->_right);
RotateL(parent);
因为插入的情况都只有一种，所以平衡因子的更新很简单，看上面画的示意图就行。即 parent 和 PR(PL) 的平衡因子最后都变成 0，其他节点的平衡因子没有变化。
因为左右双旋和右左双旋的新节点既可以插在子树 b 上，又可以插在子树 c 上，而插在这两颗子树上的平衡因子更新是不同的。
例如：
而且当 h=0 时，还有一种情况：下图是左右双旋的 h=0 的旋转图，最后：parent 的平衡因子=0，PL 的平衡因子=0，PLR 的平衡因子=0。
综上，左右双旋代码逻辑如下：
void UpdateBF(Node* parent, Node* child){ if(child == parent->_left){ parent->_bf--; } else { parent->_bf++; } }
右左双旋同理。
bool Insert(const T& data){ if(_root == nullptr){ _root = new Node(data); return true; } Node* cur = _root; Node* parent = nullptr; while(cur){ if(data < cur->_key){ parent = cur; cur = cur->_left; } else if(data > cur->_key){ parent = cur; cur = cur->_right; } else return false; // 不允许重复 } cur = new Node(data); cur->_parent = parent; if(data < parent->_key) parent->_left = cur; else parent->_right = cur; // 更新平衡因子 while(parent){ if(cur == parent->_left) parent->_bf--; else parent->_bf++; if(parent->_bf == 0) break; else if(parent->_bf == 1 || parent->_bf == -1){ cur = parent; parent = parent->_parent; } else{ // 需要旋转 if(parent->_bf == 2 && cur->_bf == 1) RotateL(parent); else if(parent->_bf == -2 && cur->_bf == -1) RotateR(parent); else if(parent->_bf == 2 && cur->_bf == -1){ RotateR(parent->_right); RotateL(parent); } else if(parent->_bf == -2 && cur->_bf == 1){ RotateL(parent->_left); RotateR(parent); } UpdateBF(parent, cur); break; } } return true; }
bool Empty() const{ return _root == nullptr; }
size_t Size() const{ return _size; } // 假设有一个_size 成员变量统计节点数，或者通过遍历计算
void InOrder(){ _InOrder(_root); cout << endl; }
void _InOrder(Node* root){ if(root == nullptr) return; _InOrder(root->_left); cout << root->_key << " "; _InOrder(root->_right); }
#include <iostream>
#include <cmath>
using namespace std;
template<class T>
struct AVLTreeNode{
T _key;
int _bf;
AVLTreeNode<T>* _left;
AVLTreeNode<T>* _right;
AVLTreeNode<T>* _parent;
AVLTreeNode(const T& x):_key(x),_bf(0),_left(nullptr),_right(nullptr),_parent(nullptr){}
};
template<class T>
class AVLTree{
typedef AVLTreeNode<T> Node;
public:
AVLTree():_root(nullptr){}
~AVLTree(){ Destroy(_root); }
AVLTree(const AVLTree& tree){ _root = Copy(tree._root, nullptr); }
AVLTree& operator=(AVLTree tree){ Swap(tree); return *this; }
void Swap(AVLTree& tree){ std::swap(_root, tree._root); }
bool Insert(const T& data){ /* 见上文 */ }
Node* Find(const T& data){ /* 见上文 */ }
bool Empty() const{ return _root == nullptr; }
size_t Size() const{ return _Size(_root); }
void InOrder(){ _InOrder(_root); cout << endl; }
private:
Node* _root;
void Destroy(Node* root){ if(root == nullptr) return; Destroy(root->_left); Destroy(root->_right); delete root; }
Node* Copy(Node* root, Node* parent){ if(root == nullptr) return nullptr; Node* newRoot = new Node(root->_key); newRoot->_parent = parent; newRoot->_left = Copy(root->_left, newRoot); newRoot->_right = Copy(root->_right, newRoot); return newRoot; }
void RotateL(Node*& parent){ /* 见上文 */ }
void RotateR(Node*& parent){ /* 见上文 */ }
void UpdateBF(Node* parent, Node* child){ /* 见上文 */ }
size_t _Size(Node* root){ if(root == nullptr) return 0; return _Size(root->_left) + _Size(root->_right) + 1; }
void _InOrder(Node* root){ if(root == nullptr) return; _InOrder(root->_left); cout << root->_key << " "; _InOrder(root->_right); }
};
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online