C++算法
C++ AVL 树（平衡搜索树）概念讲解与模拟实现
AVL 树是一种自平衡二叉搜索树，通过旋转操作确保任意节点左右子树高度差不超过 1。文章详细阐述了 AVL 树的基本概念、平衡因子的定义与更新机制、插入过程中的不平衡检测以及四种旋转调整策略（左单旋、右单旋、左右双旋、右左双旋）。提供了基于 C++ 模板的完整代码实现，包括节点定义、插入逻辑、旋转函数及平衡性验证方法，并通过随机数据测试验证了实现的正确性。
AVL 树是一种自平衡二叉搜索树，通过旋转操作确保任意节点左右子树高度差不超过 1。文章详细阐述了 AVL 树的基本概念、平衡因子的定义与更新机制、插入过程中的不平衡检测以及四种旋转调整策略（左单旋、右单旋、左右双旋、右左双旋）。提供了基于 C++ 模板的完整代码实现，包括节点定义、插入逻辑、旋转函数及平衡性验证方法，并通过随机数据测试验证了实现的正确性。
理想状态下，当数据乱序并且二叉搜索树的形态趋近于满二叉树的时候，二叉搜索树查找的时间复杂度为 O(logN)，效率很高。但是，当数据有序或接近有序的时候，二叉搜索树会退化成单支树，此时进行数据查找的时间复杂度为 O(N)，相当于在顺序表中遍历数据进行查找，效率十分低。
一颗 AVL 树要么是空树，要么是具有以下性质的二叉搜索树：
AVL 树采用类模板的形式，使用 key_value 结构实现，同时使用 pair 键值对。定义 AVL 树的节点，成员变量包括 pair 键值对、左右指针、父亲节点以及平衡因子。这里的父亲节点用于后续旋转中找到父亲节点进行链接，即节点的结构是三叉链的结构。
#pragma once
#include <iostream>
#include <assert.h>
using namespace std;
template<typename K, typename V>
struct AVLTreeNode {
pair<K, V> _kv;
AVLTreeNode<K, V>* _left;
AVLTreeNode<K, V>* _right;
AVLTreeNode<K, V>* _parent;
int _bf;
AVLTreeNode(const pair<K, V>& kv) :_kv(kv), _left(nullptr), _right(nullptr), _parent(nullptr), _bf(0) {}
};
template<typename K, typename V>
class AVLTree {
typedef AVLTreeNode<K, V> Node;
public:
AVLTree() :_root(nullptr) {}
private:
Node* _root;
};
平衡因子本质是一个 int 类型的变量，它是用于判断是否需要进行旋转控制树的高度的。它的计算是采用当前节点的右子树的高度减去左子树的高度就为当前节点的平衡因子，在插入和删除过程中平衡因子需要频繁更新控制。
正常情况下平衡因子的取值为 -1, 0, 1。一旦平衡因子的绝对值超出这个区间 [-1, 1]，平衡因子为 2 或 -2，说明当前节点的左右子树的高度差的绝对值大于 1，此时不符合 AVL 树的性质了，不满足平衡，此时就需要进行旋转降低树的高度。
其中为了控制树的高度进行的旋转有 4 种：左单旋、右单旋、右左双旋、左右双旋四种情况，这四种情况都是通过平衡因子判断出来的。
常规插入的情况下的平衡因子更新规律：如果新插入的节点处于其父亲节点的右边，那么其父亲节点的平衡因子应该 ++；如果新插入的节点处于其父亲节点的左边，那么其父亲节点的平衡因子应该 --。
关于插入找插入节点的逻辑和二叉搜索树的非递归中的插入一样。由于是三叉链的结构，还需要将标记的 cur 的父亲节点 parent 链接到 cur 中的父亲节点的指针 _parent 上。
接下来完成一个至关重要的步骤，那就是更新控制当前插入节点的父亲的平衡因子，并且根据父亲平衡因子判断是否需要向上更新，以及是否继续向上停止更新，以及是否当前树处于不平衡的状态，是否需要进行旋转降低高度。
bool Insert(const pair<K, V>& kv) {
if (_root == nullptr) {
_root = new Node(kv);
return true;
}
else {
Node* parent = nullptr;
Node* cur = _root;
while (cur) {
if (kv.first > cur->_kv.first) {
parent = cur;
cur = cur->_right;
}
else if (kv.first < cur->_kv.first) {
parent = cur;
cur = cur->_left;
}
else {
return false;
}
}
cur = new Node(kv);
cur->_parent = parent; // 三叉链需要额外链接 cur 的父亲节点
if (cur->_kv.first > parent->_kv.first) {
parent->_right = cur;
}
else {
parent->_left = cur;
}
while (parent) { // 当 parent == nullptr 的时候，无法继续向上更新，退出即可
if (cur->_kv.first > parent->_kv.first) {
parent->_bf++;
}
else {
parent->_bf--;
}
if (parent->_bf == 0) { // 此时父亲节点的平衡因子为 0，退出即可
break;
}
else if (parent->_bf == 1 || parent->_bf == -1) { // 迭代 cur 和 parent，继续向上更新
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) {
RotateRL(parent);
}
else if (parent->_bf == -2 && cur->_bf == 1) {
RotateLR(parent);
}
else { // 如果 cur 的平衡因子不符合为 1 或 -1 的情况，说明在插入前树已经不是 AVL 树了
assert(false);
}
break;
}
else { // 如果 parent 的平衡因子不符合为 0, 1 或 -1, 2 或 -2 的情况
assert(false);
}
}
return true;
}
}
进行旋转需要注意的问题需要保证它是搜索树变成平衡树并且降低这颗子树的高度。旋转分为左单旋、右单旋、右左双旋、左右双旋，这四种旋转我们不希望暴露给用户，所以我们将这四种旋转使用 private 访问限定符设置为私有成员。
左单旋是 parent 节点的右边（右子树）高于左边（左子树），右边是一条直线，符合此时平衡因子 parent == 2 && cur == 1 的情况。此时 AVL 树不平衡，parent 的右边高，为了降低整棵子树的高度维持平衡，此时就应该进行左单旋。
void RotateL(Node* parent) {
Node* ppnode = parent->_parent;
Node* cur = parent->_right;
Node* curleft = cur->_left;
parent->_right = curleft;
if (curleft) {
curleft->_parent = parent;
}
cur->_left = parent;
parent->_parent = cur;
if (ppnode == nullptr) {
_root = cur;
cur->_parent = nullptr;
}
else {
cur->_parent = ppnode;
if (ppnode->_left == parent) {
ppnode->_left = cur;
}
else {
ppnode->_right = cur;
}
}
parent->_bf = cur->_bf = 0;
}
右单旋是 parent 节点的左边（左子树）高于右边（右子树），左边是一条直线，符合此时平衡因子 parent == -2 && cur == -1 的情况。此时 AVL 树不平衡，parent 的左边高度高，为了降低整棵子树的高度维持平衡，此时就应该进行右单旋。
void RotateR(Node* parent) {
Node* ppnode = parent->_parent;
Node* cur = parent->_left;
Node* curright = cur->_right;
parent->_left = curright;
if (curright) {
curright->_parent = parent;
}
cur->_right = parent;
parent->_parent = cur;
if (ppnode == nullptr) {
_root = cur;
cur->_parent = nullptr;
}
else {
if (ppnode->_left == parent) {
ppnode->_left = cur;
cur->_parent = ppnode;
}
else {
ppnode->_right = cur;
cur->_parent = ppnode;
}
}
parent->_bf = cur->_bf = 0;
}
右左双旋，顾名思义需要进行两次旋转，先以 cur 为旋转点进行右旋转，再以 parent 为旋转点进行左旋转。当平衡因子满足 parent == 2 && cur == -1，parent 和 cur 和 curleft 所在的节点构成曲线的时候，此时不能使用单纯的左单旋或右单旋，而是要使用两次旋转去完成降低高度控制平衡。
void RotateRL(Node* parent) {
Node* cur = parent->_right;
Node* curleft = cur->_left;
int bf = curleft->_bf;
RotateR(cur);
RotateL(parent);
if (bf == 0) { // 对应 h == 0 的情况
parent->_bf = 0;
cur->_bf = 0;
curleft->_bf = 0;
}
else if (bf == -1) {
parent->_bf = 0;
cur->_bf = 1;
curleft->_bf = 0;
}
else if (bf == 1) {
parent->_bf = -1;
cur->_bf = 0;
curleft->_bf = 0;
}
else { // 如果 bf 出现其它情况，那么插入前该树已经不是 AVL 树
assert(false);
}
}
左右双旋是进行两次旋转，先以 cur 为旋转点进行左单旋，再以 parent 为旋转点进行右单旋。进行左右双旋的平衡因子需要满足：parent == -2 && cur == 1，并且分三种情况，这三种不同的情况对应的平衡因子的更新情况都各不相同。
void RotateLR(Node* parent) {
Node* cur = parent->_left;
Node* curright = cur->_right;
int bf = curright->_bf;
RotateL(cur);
RotateR(parent);
if (bf == 0) {
parent->_bf = 0;
cur->_bf = 0;
curright->_bf = 0;
}
else if (bf == -1) {
parent->_bf = 1;
cur->_bf = 0;
curright->_bf = 0;
}
else if (bf == 1) {
parent->_bf = 0;
cur->_bf = -1;
curright->_bf = 0;
}
else {
assert(false);
}
}
我们知道 AVLTree 的最重要的特点就是左右子树的高度差的绝对值不超过 1。这里我们递归 AVL 树验证每一层的节点使用高度计算函数 Height 计算出的右子树的高度减去左子树的高度，即计算出并验证每一层的左右子树的高度差的绝对值是否都不超过 1。
同时还可以顺便验证计算出来当前节点的左右子树的高度差是否等于当前节点存储的平衡因子 _bf。如果不相等则打印出对应节点的 key 值及异常的平衡因子。
int Height() {
return Height(_root);
}
int Height(Node* root) {
if (root == nullptr) {
return 0;
}
int heightL = Height(root->_left);
int heightR = Height(root->_right);
return heightL > heightR ? heightL + 1 : heightR + 1;
}
bool Isbalance() {
return Isbalance(_root);
}
bool Isbalance(Node* root) {
if (root == nullptr) {
return true;
}
Node* left = root->_left;
Node* right = root->_right;
int heightL = Height(left);
int heightR = Height(right);
int bf = heightR - heightL;
if (bf != root->_bf) {
cout << "平衡因子异常" << root->_kv.first << ":" << root->_bf << endl;
return false;
}
return abs(bf) <= 1 && Isbalance(left) && Isbalance(right);
}
使用第一组数据验证一下：
#include <iostream>
#include "AVLTree.h"
using namespace std;
int main() {
int arr[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
AVLTree<int, int> alv;
for (auto e : arr) {
alv.Insert(make_pair(e, e));
cout << e << ':' << alv.Isbalance() << endl;
}
return 0;
}
运行结果正确。
使用更严格更随机更大量的数据进行验证，设置好随机数种子，然后使用 rand 函数随机生成一千万的随机数数据构成 AVLTree 进行验证正确性。
#include <iostream>
#include "AVLTree.h"
#include <time.h>
#include <vector>
using namespace std;
int main() {
srand((unsigned int)time(NULL));
const int N = 10000000;
vector<int> v;
v.reserve(N); // 提前扩容，防止频繁扩容带来的消耗
for (int i = 0; i < N; i) {
v.push_back(rand());
}
AVLTree<int, int> avl;
for (auto e : v) {
avl.Insert(make_pair(e, e));
}
cout << avl.Isbalance() << endl;
cout << avl.Height() << endl;
return 0;
}
运行结果正确。
#pragma once
#include <iostream>
#include <assert.h>
using namespace std;
template<typename K, typename V>
struct AVLTreeNode {
pair<K, V> _kv;
AVLTreeNode<K, V>* _left;
AVLTreeNode<K, V>* _right;
AVLTreeNode<K, V>* _parent;
int _bf;
AVLTreeNode(const pair<K, V>& kv) :_kv(kv), _left(nullptr), _right(nullptr), _parent(nullptr), _bf(0) {}
};
template<typename K, typename V>
class AVLTree {
typedef AVLTreeNode<K, V> Node;
public:
AVLTree() :_root(nullptr) {}
bool Insert(const pair<K, V>& kv) {
if (_root == nullptr) {
_root = new Node(kv);
return true;
}
else {
Node* parent = nullptr;
Node* cur = _root;
while (cur) {
if (kv.first > cur->_kv.first) {
parent = cur;
cur = cur->_right;
}
else if (kv.first < cur->_kv.first) {
parent = cur;
cur = cur->_left;
}
else {
return false;
}
}
cur = new Node(kv);
cur->_parent = parent;
if (cur->_kv.first > parent->_kv.first) {
parent->_right = cur;
}
else {
parent->_left = cur;
}
while (parent) {
if (cur->_kv.first > parent->_kv.first) {
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) {
RotateRL(parent);
}
else if (parent->_bf == -2 && cur->_bf == 1) {
RotateLR(parent);
}
else {
assert(false);
}
break;
}
else {
assert(false);
}
}
return true;
}
}
int Height() {
return Height(_root);
}
int Height(Node* root) {
if (root == nullptr) {
return 0;
}
int heightL = Height(root->_left);
int heightR = Height(root->_right);
return heightL > heightR ? heightL + 1 : heightR + 1;
}
bool Isbalance() {
return Isbalance(_root);
}
bool Isbalance(Node* root) {
if (root == nullptr) {
return true;
}
Node* left = root->_left;
Node* right = root->_right;
int heightL = Height(left);
int heightR = Height(right);
int bf = heightR - heightL;
if (bf != root->_bf) {
cout << "平衡因子异常" << root->_kv.first << ":" << root->_bf << endl;
return false;
}
return abs(bf) <= 1 && Isbalance(left) && Isbalance(right);
}
private:
void RotateL(Node* parent) {
Node* ppnode = parent->_parent;
Node* cur = parent->_right;
Node* curleft = cur->_left;
parent->_right = curleft;
if (curleft) {
curleft->_parent = parent;
}
cur->_left = parent;
parent->_parent = cur;
if (ppnode == nullptr) {
_root = cur;
cur->_parent = nullptr;
}
else {
cur->_parent = ppnode;
if (ppnode->_left == parent) {
ppnode->_left = cur;
}
else {
ppnode->_right = cur;
}
}
parent->_bf = cur->_bf = 0;
}
void RotateR(Node* parent) {
Node* ppnode = parent->_parent;
Node* cur = parent->_left;
Node* curright = cur->_right;
parent->_left = curright;
if (curright) {
curright->_parent = parent;
}
cur->_right = parent;
parent->_parent = cur;
if (ppnode == nullptr) {
_root = cur;
cur->_parent = nullptr;
}
else {
if (ppnode->_left == parent) {
ppnode->_left = cur;
cur->_parent = ppnode;
}
else {
ppnode->_right = cur;
cur->_parent = ppnode;
}
}
parent->_bf = cur->_bf = 0;
}
void RotateRL(Node* parent) {
Node* cur = parent->_right;
Node* curleft = cur->_left;
int bf = curleft->_bf;
RotateR(cur);
RotateL(parent);
if (bf == 0) {
parent->_bf = 0;
cur->_bf = 0;
curleft->_bf = 0;
}
else if (bf == -1) {
parent->_bf = 0;
cur->_bf = 1;
curleft->_bf = 0;
}
else if (bf == 1) {
parent->_bf = -1;
cur->_bf = 0;
curleft->_bf = 0;
}
else {
assert(false);
}
}
void RotateLR(Node* parent) {
Node* cur = parent->_left;
Node* curright = cur->_right;
int bf = curright->_bf;
RotateL(cur);
RotateR(parent);
if (bf == 0) {
parent->_bf = 0;
cur->_bf = 0;
curright->_bf = 0;
}
else if (bf == -1) {
parent->_bf = 1;
cur->_bf = 0;
curright->_bf = 0;
}
else if (bf == 1) {
parent->_bf = 0;
cur->_bf = -1;
curright->_bf = 0;
}
else {
assert(false);
}
}
private:
Node* _root;
};
#include <iostream>
#include "AVLTree.h"
using namespace std;
#include <time.h>
#include <vector>
int main() {
srand((unsigned int)time(NULL));
const int N = 10000000;
vector<int> v;
v.reserve(N);
for (int i = 0; i < N; i++) {
v.push_back(rand());
}
AVLTree<int, int> avl;
for (auto e : v) {
avl.Insert(make_pair(e, e));
}
cout << avl.Isbalance() << endl;
cout << avl.Height() << endl;
return 0;
}
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 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