介绍 AVL 树（平衡二叉搜索树）的原理与 C++ 实现。AVL 树通过限制节点平衡因子（左右子树高度差绝对值不超过 1）保证 O(logN) 查找效率。文章详细说明了插入节点后平衡因子的更新逻辑，以及四种旋转操作（左单旋、右单旋、左右双旋、右左双旋）的触发条件和具体步骤。提供了包含构造、析构、拷贝、查找及插入功能的完整类代码示例。
普通二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序，二叉搜索树将退化为单支树，查找元素相当于在顺序表中搜索元素，效率低下。
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 调用析构函数，把指向的从 *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 (_root == parent)
_root = subR;
else {
if (pp->_left == parent)
pp->_left = subR;
else
pp->_right = subR;
}
subR->_parent = pp;
// 更新平衡因子
parent->_bf = subR->_bf = 0;
}
所有的需要右单旋的情况，都可以画成下图的抽象图。 具体情况描述：
此时就使用右单旋：把（下图中的）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 (_root == parent)
_root = subL;
else {
if (pp->_left == parent)
pp->_left = subL;
else
pp->_right = subL;
}
subL->_parent = pp;
// 更新平衡因子
parent->_bf = subL->_bf = 0;
}
所有的需要左右双旋的情况，都可以画成下图的抽象图。 具体情况描述：
此时使用一次单旋，是解决不了的，旋了之后还是有平衡因子为 2/-2 的节点。但是如果我们对 PL 进行左单旋之后，就可以发现可以对 parent 使用右旋来使树，在不违反搜索树规则（所有左子树上的值<根<右子树）的基础上，尽可能地接近平衡。
即：
RotateL(parent->_left);
RotateR(parent);
所有的需要右左双旋的情况，都可以画成下图的抽象图。 具体情况描述：
此时使用一次单旋，是解决不了的，旋了之后还是有平衡因子为 2/-2 的节点。但是如果我们对 PR 进行右单旋之后，就可以发现可以对 parent 使用左单旋来使树，在不违反搜索树规则（所有左子树上的值<根<右子树）的基础上，尽可能地接近平衡。
即：
RotateR(parent->_right);
RotateL(parent);
因为插入的情况都只有一种，所以平衡因子的更新很简单，看上面画的示意图就行。即 parent 和 PR(PL) 的平衡因子最后都变成 0，其他节点的平衡因子没有变化。
因为左右双旋和右左双旋的新节点既可以插在子树 b 上，又可以插在子树 c 上，而插在这两颗子树上的平衡因子更新是不同的。
综上：左右双旋代码逻辑如下（需根据新节点位置微调 bf）：
void RotateLR(Node*& parent) {
Node* subL = parent->_left;
Node* subLR = subL->_right;
int bf = subLR->_bf;
RotateL(parent->_left);
RotateR(parent);
if (bf == 1) {
parent->_bf = 0;
subL->_bf = -1;
} else if (bf == -1) {
parent->_bf = 1;
subL->_bf = 0;
} else {
parent->_bf = 0;
subL->_bf = 0;
}
subLR->_bf = 0;
}
右左双旋同理。
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) {
if (cur->_left == nullptr) {
cur->_left = new Node(data);
cur->_left->_parent = cur;
break;
} else {
cur = cur->_left;
}
} else if (data > cur->_key) {
if (cur->_right == nullptr) {
cur->_right = new Node(data);
cur->_right->_parent = cur;
break;
} else {
cur = cur->_right;
}
} else {
return false; // 已存在
}
}
// 更新平衡因子
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 || parent->_bf == -2) {
// 失衡，需要旋转
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) {
// 左右情况，左右双旋
RotateLR(parent);
} else if (parent->_bf == -2 && cur->_bf == 1) {
// 右左情况，右左双旋
RotateRL(parent);
}
break; // 旋转后高度恢复，停止更新
}
}
return true;
}
bool Empty() const { return _root == nullptr; }
size_t Size() const { return _size; }
void InOrder() {
_InOrder(_root);
cout << endl;
}
void _InOrder(Node* root) {
if (root == nullptr) return;
_InOrder(root->_left);
cout << root->_key << " ";
_InOrder(root->_right);
}
完整代码请参照 AVLTree.hpp 文件结构。
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 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