【c++】AVL树的部分实现
hello~ 很高兴见到大家! 这次带来的是C++中关于AVL树这部分的一些知识点,如果对你有所帮助的话,可否留下你宝贵的三连呢? 个 人 主 页: 默|笙
一、AVL树介绍
1. 了解AVL树
- AVL树是最先发明的平衡二叉搜索树，AVL是一棵空树，或者是具备以下条件的搜索树：左右子树都是AVL树，且高度差的绝对值不大于1。它通过控制高度来达到平衡，它得名于它的发明者G.MAdelson-Velsky 和 E.M.Landis两个前苏联的科学家。
- AVL树通过引入一个平衡因子的概念，平衡因子 = 右子树高度 - 左子树高度，每个节点都有一个平衡因子，且每个节点的平衡因子一定是-1/0/1。AVL树并不是一定需要平衡因子，但是通过平衡因子的值能够更加直观的观察和判断树是否平衡。
- AVL高度差要求不超过1，而不是0，是因为有时在插入的的时候无法做到高度差为0，比如4个节点的二叉树。AVL树只有最后两层的节点可以不是满的，这一点很像完全二叉树，不过完全二叉树是最后一层节点可以不满。所以它的增删查改效率可以控制在O（logN），相比于普通二叉树有了很大的提升。
在这里插入图片描述
2. AVL树结构
template<class K, class V>
struct AVLTreeNode
{
AVLTreeNode(const pair<K, V>& kv)
:_kv(kv)
,_left(nullptr)
,_right(nullptr)
,_parent(nullptr)
,_bf(0)
{ }
pair<K, V> _kv;
AVLTreeNode<K, V>* _left;
AVLTreeNode<K, V>* _right;
AVLTreeNode<K, V>* _parent;//指向父亲节点
int _bf;//平衡因子
};
template<class K, class V>
class AVLTree
{
typedef AVLTreeNode<K, V> Node;
```
private:
Node* _root = nullptr;//给缺省值，用编译器自动生成的默认构造函数
};- 它的结构基于一般的key/value二叉搜索树，节点里的成员变量多了一个指针_parent，它指向当前节点的父亲节点。也就是一个节点拥有三个指针。还多了一个成员变量 _bf，它用来记录当前节点的平衡因子。
二、AVL树的插入
- 插入一个值会按照二叉搜索树的规则来进行插入。<二叉搜索树博客>
- 新增节点之后，一定会更新部分当前节点到跟节点一系列祖先节点的平衡因子，因为影响了高度。最坏的情况是一直更新到根节点，有些情况更新到中间节点就会停止。
- 更新平衡因子的过程中如果没有出现异常，插入之后仍然保持平衡，那么更新将会停止。
- 如果平衡因子出现了异常，代表着树已经不平衡，那么就需要对树进行旋转操作。旋转操作的本质是降低子树的高度，保持平衡。
在这里插入图片描述
- 比如新增一个节点5，它的出现可能会使从节点5到根节点8一路上一系列的祖先节点的平衡因子更新。最终它只影响到节点3就停止，因为节点3平衡因子绝对值已经大于了1，平衡因子异常，这棵树已经不平衡，更新停止，需要对以节点3为根节点的这棵子树进行旋转操作，降低它右子树的高度进而达到平衡。
1. 平衡因子更新
1.1 更新原则
- 平衡因子 = 右子树高度 - 左子树高度。
- 只有子树高度变化才会影响当前子树的根节点的平衡因子。
- 新增节点的平衡因子为0，它的父节点的平衡因子一定会改变。父节点平衡因子的变化决定了要不要继续向上更新。
- 如果新增节点在其父节点的右子树，那么父节点平衡因子++，反之–。
cpp平衡因子 = 右子树高度 - 左子树高度
右子树高度+1，平衡因子会+1
左子树高度+1，平衡因子会-11.2 更新终止和继续条件
更新终止
- 当parent更新完之后的平衡因子为0的时候（由-1/1变来），更新之后parent左右子树高度相等时，不用继续向上更新。因为以parent为根节点的这棵子树的高度没有改变，不会影响到parent的直系祖先的平衡因子。
在这里插入图片描述
- 就比如插入7这一个节点，那么其父亲节点节点6的平衡因子将从-1变为0，可以看到，以6为根节点的这棵子树的高度是没有变化的，即节点3的右子树的高度没有改变，3的平衡因子自然不会改变，也就不需要更新。在更新完节点6之后就可以停止更新。在更新直系祖先平衡因子的途中也是这样，如果parent更新之后的平衡因子为0，就不用继续向上更新了。
- 当parent节点平衡因子为2/-2的时候（由1/-1变来），平衡因子异常时，需要进行对以parent为根节点的这棵子树或整棵树旋转来调整高度，不用再向上更新，因为旋转之后会变得平衡，平衡因子的变化旋转部分会详细讲解。
更新继续
- 当parent节点平衡因子为1/-1的时候（由0变来），需要向上更新，直到遇到前两种更新停止的情况为止。这种情况是原来parent的左右子树是平衡的，现在插入了一个节点，导致以parent为根节点的子树高度改变，将会影响到parent的直系祖先节点的平衡因子。
在这里插入图片描述
- 这里节点4的平衡因子变为1，需要向上更新，节点6的平衡因子变为-1，继续向上更新直到节点3的平衡因子变为2才停止。
插入节点更新平衡因子代码实现：
bool Insert(const pair<K, V>& kv)
{
//考虑空树的情况
if (_root == nullptr)
{
_root = new Node(kv);
}
else
{
Node* cur = _root;
Node* parent = nullptr;
while (cur)
{
if (cur->_kv.first > kv.first)
{
parent = cur;
cur = cur->_left;
}
else if (cur->_kv.first < kv.first)
{
parent = cur;
cur = cur->_right;
}
else
{
return false;
}
}
cur = new Node(kv);
if (parent->_kv.first > cur->_kv.first)
{
parent->_left = cur;
}
else
{
parent->_right = cur;
}
cur->_bf = 0;
cur->_parent = parent;//完成对节点的插入
//更新平衡因子
while (parent)
{
if (parent->_left == cur)
{
//是左子树就--
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)
{
//进行旋转
break;
}
}
}
}三、旋转
旋转分为四种针对四种不同的情况，分别是：
- 右旋转针对parent左子树高度比右子树高1，且parent左孩子的左子树的高度也比parent左孩子的右子树高1的情况。
- 左旋转针对parent右子树高度比左子树高1，且parent右孩子的右子树的高度也比parent右孩子的左子树高1的情况。
- 左右双旋针对parent左子树高度比右子树高1，且parent左孩子的右子树高度比parent左孩子的左子树高1的情况。
- 右左双旋针对parent右子树高度比左子树高1，且parent的右孩子的左子树高度比parent右孩子的右子树高1的情况。
- 注意区分情况1和情况3，情况2和情况4，可以通过下面的图来更好的理解。
1. 右旋转和左旋转
1.1 右旋转
右旋转针对parent左子树高度比右子树高1，且parent左孩子的左子树的高度也比parent左孩子的右子树高1的情况。
在这里插入图片描述
- 我们可以将右旋转的模型抽象为图中所示，块h代表着许多种情况下的二叉平衡搜索子树，但它们的高度都是相同的。现在给定一个情境：在黄色区块增加一个节点，一定会导致黄色区块的高度+1，黄色区块具体是什么样子不做分析，情况有无数种。
- 我们来分析平衡因子的变化情况，在更新之前，节点15的平衡因子是-1，因为左子树高度是h+1，右子树高度是h，平衡因子 = 右子树高度 - 左子树高度 = -1。更新之后，由于10节点的左子树高度变成h + 1，它的平衡因子更新为-1，需要继续向上更新，节点15的左子树的高度变成h + 2，平衡因子更新为 -2，更新停止，需要对以15为根节点的这棵树做右旋转处理。
- 黄色区块的数 < 10 < 绿色区块的数 < 15 < 蓝色区块的数。以所以可以把绿色区块给到节点15的左子树，让10节点变成根节点，节点15变成节点10的右孩子。右旋转的本质就是将节点10变成根节点，以10为新的分界点，黄色区块一定在节点10左边，绿色区块，节点15，蓝色区块一定在节点10右边。从图上看，就像是向右旋转了一下。
- 接着我们能够发现，节点10的左右子树高度都是h + 1，平衡节点为0，节点15的左右子树高度都是h，平衡节点为0，它们变得完全平衡，不再需要往上面的直系祖先更新平衡因子了。
- 由于需要改动的主要是根节点，根节点的左孩子和根节点的左孩子的右子树，我们将它们记录下来，以parent为参考点，parent的左孩子记为subL，parent的左孩子的右子树记为subLR。
- 那么什么时候会需要进行右旋转？可以根据平衡因子来进行判断，当parent节点平衡因子为-2且subL节点为-1（parent->left）的时候就需要进行右旋转。
接下来给出一段代码：
void RotateR(Node* parent)
{
//记录节点
Node* subL = parent->_left;
Node* subLR = subL->_right;
parent->_left = subLR;
subL->_right = parent;
parent->_bf = subL->_bf = 0;
}在这里插入图片描述
- 这段代码有多个问题，它只改变了指针_left和指针_right的指向，而没有管指针_parent的指向，AVL树每个节点是拥有三个指针的。我们需要把parent的_parent指针指向subL，subLR的_parent指针指向parent，subL的_parent的指针置空？
- 但是要在考虑改变parent的基础之上，考虑特殊情况，h = 0的情况，即subLR = nullptr的时候。这种情况下不能对subLR指针解引用去改变它_parent指针的指向，需要做特殊处理。
- 且节点parent不一定就是整棵树的根节点，它很有可能只是这棵子树的根节点，我们需要分情况处理，有两个要点第一是如何判断，第二是如何做：若它是整棵树的根节点的话，parent 的_parent指针一定为空（因为我们将根节点初始化为nullptr），且我们需要改变这棵树的_root，_root = subL，然后将subL的_parent 指针置空；否则parent只是某棵子树的根节点，我们需要记录parent的父亲节点（在改变parent的_parent指针指向之前），记为parentParent，然后判断这棵子树是parentParent的左子树还是右子树，接着去改变parentParent的_left指针或_right指针，将它们指向subL，最后改变subL的_parent指针，将它指向parentParent。
右旋转代码：
void RotateR(Node* parent)
{
//记录节点
Node* subL = parent->_left;
Node* subLR = subL->_right;
Node* parentParent = parent->_parent;
//改变指针
parent->_left = subLR;
subL->_right = parent;
if (parentParent == nullptr)
{
_root = subL;
subL->_parent = nullptr;
}
else
{
if (parentParent->_left == parent)
{
parentParent->_left = subL;
}
else
{
parentParent->_right = subL;
}
subL->_parent = parentParent;
}
//避免subLR = nullptr出现空指针解引用的情况
if (subLR)
{
subLR->_parent = parent;
}
parent->_parent = subL;
//改变平衡因子
parent->_bf = subL->_bf = 0;
}1.2 左旋转
左旋转针对parent右子树高度比左子树高1，且parent右孩子的右子树的高度也比parent右孩子的左子树高1的情况。
在这里插入图片描述
- 左旋转跟右旋转的规律高度相似，这里就不再详细解释。它就像是往左旋转了一下。**它是在parent平衡因子为2且parent->right平衡因子为1的情况下进行左旋转。
左旋转代码：
void RotateL(Node* parent)
{
//记录节点
Node* subR = parent->_right;
Node* subRL = subR->_left;
Node* parentParent = parent->_parent;
//改变指针指向
subR->_left = parent;
parent->_right = subRL;
if (parentParent == nullptr)
{
_root = subR;
subR->_parent = nullptr;
}
else
{
if (parentParent->_left == parent)
{
parentParent->_left = subR;
}
else
{
parentParent->_right = subR;
}
subR->_parent = parentParent;
}
if (subRL)
{
subRL->_parent = parent;
}
parent->_parent = subR;
//改变平衡因子
parent->_bf = subR->_bf = 0;
}2. 左右双旋和右左双旋
2.1 左右双旋
左右双旋针对parent左子树高度比右子树高1，且parent左孩子的右子树高度比parent左孩子的左子树高1的情况。
在这里插入图片描述
- 左右双旋顾名思义就是先进行一次左旋转，再进行一次右旋转使其平衡。第一次左旋转针对的是parent的左子树，第二次就针对的是以parent为根节点的整棵树，最后能让整棵树达到平衡。
- 假设图2到图3平衡因子会更新成图中所示，如图3所示的节点12的平衡因子暂时变为-2，且节点10的平衡因子暂时变为0，那也只会在左右双旋针对的情况里面出现。它不被包含在右旋转针对的情况里面。
- 左旋转之后节点15，节点12，节点10的平衡因子都会更新为0。
- 左右双旋的本质其实是将subLR的左子树给subL，右子树给parent，然后让节点12变成新的根节点。
- 除了图中所示情况之外，还有可能新节点插入在节点12的右子树里，致使节点12的平衡因子变成1，最后的结果就是节点10的平衡因子为-1，而节点15的平衡因子为0。可以凭借节点12更新后的平衡因子来判断是哪种情况。
- 然后需要考虑特殊情况，那就是h = 0 的情况，插入节点12，节点12的平衡因子为0。这种情况下，节点15，节点10，节点12的平衡因子最后都会是0，可以将最后的图的所有颜色区块去掉，方便看。
- 在最后改变平衡因子的时候，需要提前存储一下subLR的平衡因子，因为在左旋转和右旋转之后平衡因子都会变成0。
- 左右双旋其实就是对左旋转和右旋转的复用，然后根据节点12的平衡因子的值更新一下平衡因子。需要改变平衡因子的是：parent，subL，subLR，可以记录一下。
左右双旋代码：
void RotateLR(Node* parent)
{
//记录一下节点
Node* subL = parent->_left;
Node* subLR = subL->_right;
int bf = subLR->_bf;
//左右双旋
RotateL(parent->_left);
RotateR(parent);
//改变平衡因子
if (bf == 0)
{
parent->_bf = 0;
subL->_bf = 0;
subLR->_bf = 0;
}
else if (bf == -1)
{
parent->_bf = 1;
subL->_bf = 0;
subLR->_bf = 0;
}
else if (bf == 1)
{
parent->_bf = 0;
subL->_bf = -1;
subLR->_bf = 0;
}
else
{
assert(false);
}
}2.1 右左双旋
右左双旋针对parent右子树高度比左子树高1，且parent的右孩子的左子树高度比parent右孩子的右子树高1的情况。
在这里插入图片描述
- 它的逻辑也跟左右双旋差不多，这里不再做详细解释。
- 右左双旋其本质就是把subRL的左子树给parent，右子树给subR。
- 记录一下节点，subR，subRL。当subRL平衡因子为-1的时候，subR平衡因子更新为1，parent平衡因子更新为0；当subRL平衡因子为1的时候，subR平衡因子更新为0，parent平衡因子更新为-1；当subRL平衡因子为0的时候，subR和parent平衡因子都更新为0。
void RotateRL(Node* parent)
{
//记录一下节点
Node* subR = parent->_right;
Node* subRL = subR->_left;
int bf = subRL->_bf;
//右旋转和左旋转各一次
RotateR(parent->_right);
RotateL(parent);
//更新平衡因子
if (bf == 0)
{
parent->_bf = parent->_bf = subRL->_bf = 0;
}
else if (bf == 1)
{
subR->_bf = 0;
parent->_bf = -1;
subRL->_bf = 0;
}
else if (bf == -1)
{
subR->_bf = 1;
parent->_bf = 0;
subRL->_bf = 0;
}
else
{
assert(false);
}
}
};四、检测是否为平衡二叉树
- 检测次数是否为一棵平衡二叉树不能通过检查它的平衡因子去实现，因为这跟监守自盗没有什么区别，有可能它是一棵平衡二叉树但是平衡因子异常，也有可能它不是一棵平衡二叉树但是平衡因子是正常的。
- 我们需要获得每一个节点它的右左子树高度之差，若没有绝对值大于1的，那么该树是平衡二叉树，否则不是，还可以用此值来核实该节点的平衡因子是否正确。
- 首先，是需要获得一棵树的高度，这个函数可以由递归算法实现，然后再进行递归，算出每一个节点它的右左子树高度之差，如果绝对值大于1，则返回false，否则true。
//算树的高度
int _Height(Node* root)
{
if (root == nullptr)
{
return 0;
}
int LeftHeight = _Height(root->_left);
int RightHeight = _Height(root->_right);
return LeftHeight > RightHeight ? LeftHeight + 1: RightHeight + 1;
}
bool _IsBalanceTree(Node* root)
{
//空树也是平衡树
if (root == nullptr)
{
return true;
}
int LeftHeight = _Height(root->_left);
int RightHight = _Height(root->_right);
int bf = RightHight - LeftHeight;
if (bf != root->_bf)
{
cout << root->_kv.first << endl;
}
if (abs(bf) > 1)
{
return false;
}
return _IsBalanceTree(root->_left) && _IsBalanceTree(root->_right);
}五、源代码
#pragma once
#include<assert.h>
#include<iostream>
using namespace std;
template<class K, class V>
struct AVLTreeNode
{
AVLTreeNode(const pair<K, V>& kv)
:_kv(kv)
,_left(nullptr)
,_right(nullptr)
,_parent(nullptr)
,_bf(0)
{ }
pair<K, V> _kv;
AVLTreeNode<K, V>* _left;
AVLTreeNode<K, V>* _right;
AVLTreeNode<K, V>* _parent;
int _bf;
};
template<class K, class V>
class AVLTree
{
typedef AVLTreeNode<K, V> Node;
public:
bool Insert(const pair<K, V>& kv)
{
//考虑空树的情况
if (_root == nullptr)
{
_root = new Node(kv);
}
else
{
Node* cur = _root;
Node* parent = nullptr;
while (cur)
{
if (cur->_kv.first > kv.first)
{
parent = cur;
cur = cur->_left;
}
else if (cur->_kv.first < kv.first)
{
parent = cur;
cur = cur->_right;
}
else
{
return false;
}
}
cur = new Node(kv);
if (parent->_kv.first > cur->_kv.first)
{
parent->_left = cur;
}
else
{
parent->_right = cur;
}
cur->_bf = 0;
cur->_parent = parent;//完成对节点的插入
//更新平衡因子
while (parent)
{
if (parent->_left == cur)
{
//是左子树就--
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 && parent->_left->_bf == -1)
{
//进行右旋转
RotateR(parent);
}
else if (parent->_bf == 2 && parent->_right->_bf == 1)
{
//进行左旋转
RotateL(parent);
}
else if (parent->_bf == -2 && parent->_left->_bf == 1)
{
//进行左右双旋
RotateLR(parent);
}
else if (parent->_bf == 2 && parent->_right->_bf == -1)
{
//进行右左双旋
RotateRL(parent);
}
else
{
//平衡因子出错
assert(false);
}
break;
}
else
{
//平衡因子出错
assert(false);
}
}
}
}
//中序遍历
void InOrder()
{
_Inorder(_root);
cout << endl;
}
//AVL树平衡检测
bool IsBalanceTree()
{
if (_IsBalanceTree(_root))
{
cout << "是平衡二叉树" << endl;
}
else
{
cout << "不是平衡二叉树" << endl;
}
return _IsBalanceTree(_root);
}
private:
//算树的高度
int _Height(Node* root)
{
if (root == nullptr)
{
return 0;
}
int LeftHeight = _Height(root->_left);
int RightHeight = _Height(root->_right);
return LeftHeight > RightHeight ? LeftHeight + 1: RightHeight + 1;
}
bool _IsBalanceTree(Node* root)
{
//空树也是平衡树
if (root == nullptr)
{
return true;
}
int LeftHeight = _Height(_root->_left);
int RightHight = _Height(_root->_right);
int bf = RightHight - LeftHeight;
if (bf != _root->_bf)
{
cout << root->_kv.first << endl;
}
if (abs(bf) > 1)
{
return false;
}
return _IsBalanceTree(root->_left) && _IsBalanceTree(root->_right);
}
void RotateR(Node* parent)
{
//记录节点
Node* subL = parent->_left;
Node* subLR = subL->_right;
Node* parentParent = parent->_parent;
//改变指针
parent->_left = subLR;
subL->_right = parent;
if (parentParent == nullptr)
{
_root = subL;
subL->_parent = nullptr;
}
else
{
if (parentParent->_left == parent)
{
parentParent->_left = subL;
}
else
{
parentParent->_right = subL;
}
subL->_parent = parentParent;
}
//避免subLR = nullptr出现空指针解引用的情况
if (subLR)
{
subLR->_parent = parent;
}
parent->_parent = subL;
//改变平衡因子
parent->_bf = subL->_bf = 0;
}
void RotateL(Node* parent)
{
//记录节点
Node* subR = parent->_right;
Node* subRL = subR->_left;
Node* parentParent = parent->_parent;
//改变指针指向
subR->_left = parent;
parent->_right = subRL;
if (parentParent == nullptr)
{
_root = subR;
subR->_parent = nullptr;
}
else
{
if (parentParent->_left == parent)
{
parentParent->_left = subR;
}
else
{
parentParent->_right = subR;
}
subR->_parent = parentParent;
}
if (subRL)
{
subRL->_parent = parent;
}
parent->_parent = subR;
//改变平衡因子
parent->_bf = subR->_bf = 0;
}
void RotateLR(Node* parent)
{
//记录一下节点
Node* subL = parent->_left;
Node* subLR = subL->_right;
//左右双旋
RotateL(parent->_left);
RotateR(parent);
//改变平衡因子
if (subLR->_bf == 0)
{
parent->_bf = 0;
subL->_bf = 0;
subLR->_bf = 0;
}
else if (subLR->_bf == -1)
{
parent->_bf = 1;
subL->_bf = 0;
subLR->_bf = 0;
}
else if (subLR->_bf == 1)
{
parent->_bf = 0;
subL->_bf = -1;
subLR->_bf = 0;
}
else
{
assert(false);
}
}
void RotateRL(Node* parent)
{
//记录一下节点
Node* subR = parent->_right;
Node* subRL = subR->_left;
//右旋转和左旋转各一次
RotateR(parent->_right);
RotateL(parent);
//更新平衡因子
if (subRL->_bf == 0)
{
parent->_bf = parent->_bf = 0;
}
else if (subRL->_bf == 1)
{
subR->_bf = 0;
parent->_bf = -1;
}
else if (subRL->_bf == -1)
{
subRL->_bf = 1;
parent->_bf = 0;
}
else
{
assert(false);
}
}
//中序遍历
void _Inorder(const Node* root)
{
if (root == nullptr)
{
return;
}
_Inorder(root->_left);
cout << root->_kv.first << " ";
_Inorder(root->_right);
}
Node* _root = nullptr;
};今天的分享就到此结束啦,如果对读者朋友们有所帮助的话,可否留下宝贵的三连呢~~ 让我们共同努力, 一起走下去!
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2026-01-13，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号