【C++】AVL 树

目录

1. AVL的概念​编辑

2. AVL 树的实现

2.1 AVL 树的结构

2.2 AVL 树的插入

2.3 旋转

2.4 AVL 树的查找

2.5 AVL 树的平衡检查

2.6 AVL树的删除

1. AVL的概念

AVL 树由前苏联数学家 G.M. Adelson-Velsky（阿德尔森 – 韦尔斯基） 和 E.M. Landis（兰迪斯） 在 1962 年提出并发表论文，它也是世界上第一个自平衡二叉搜索树。

AVL 和普通二叉搜索树（BST）最大区别

AVL 本质上依然是一棵二叉搜索树，保留 BST 的有序性质；额外增加一条平衡约束：树中任意节点，左右子树高度差绝对值不超过 1（平衡因子 ∈ {-1,0,1}）。一旦插入、删除造成失衡，会通过旋转自动调整结构、恢复平衡；普通 BST 没有这个自动平衡机制，树形态完全由插入顺序决定。

AVL 树进步的地方

AVL 树的缺点

2. AVL 树的实现

2.1 AVL 树的结构

using namespace std;
template<class T>
struct AVLTreeNode
{
AVLTreeNode(const T& data = T())
: _pLeft(nullptr)
, _pRight(nullptr)
, _pParent(nullptr)
, _data(data)
, _bf(0)
{
}

AVLTreeNode<T>* _pLeft;
AVLTreeNode<T>* _pRight;
AVLTreeNode<T>* _pParent;
T _data;
int _bf; // 节点的平衡因子
};

// 左加 右减
// AVL: 二叉搜索树 + 平衡因子的限制
template<class T>
class AVLTree
{
typedef AVLTreeNode<T> Node;
public:
// 初始默认构造
AVLTree()
: _pRoot(nullptr)
{

}

private:
Node* _pRoot;
};

2.2 AVL 树的插入

2.2.1 AVL 插入的大概过程

        向 AVL 树插入节点时，首先按照普通二叉搜索树规则找到空位插入新节点。插入完成后，从新节点向上回溯，依次更新沿途每个祖先节点的高度，计算平衡因子。

        若所有节点平衡因子绝对值都不大于 1，树保持平衡，插入结束。

        如果某个节点平衡因子超出范围，说明发生失衡，需要判断失衡类型：LL、RR、LR、RL，对应执行单旋转或者双旋转调整结构，让该子树恢复平衡。旋转完成后，继续向上检查上层节点是否失衡，直到根节点。AVL 依靠旋转保证任意节点左右子树高度差不超过 1，维持树高为对数级别，保证查找效率稳定。

2.2.2 平衡因子的更新

        平衡因子 = 左子树高度 − 右子树高度。 插入新节点后，从新节点的父节点开始往根方向回溯：先更新当前节点的高度，再重新计算它的平衡因子。

• 平衡因子绝对值≤1：该节点平衡，继续向上检查祖先；
• 平衡因子绝对值＞1：节点失衡，进行旋转调整；旋转完成后，更新旋转涉及节点的高度与平衡因子，再继续向上判断上层节点。 删除节点时变化更大，删除可能让祖先高度持续变化，需要一路向上更新高度、重算平衡因子，多次触发调整。

size_t _Height(Node* pRoot)
{
if (pRoot == nullptr)
{
return 0;
}
// max 找出两数最大数值
size_t left = _Height(pRoot->_pLeft);
size_t right = _Height(pRoot->_pRight);
return max(left,right) + 1;
}
// Bf 调整
void Bf(Node* root)
{
if (root == nullptr)
return;
int left = root->_pLeft ? _Height(root->_pLeft) : 0;
int right = root->_pRight ? _Height(root->_pRight) : 0;
root->_bf = left – right;
}

2.2.2 插入节点的更新平衡音系的代码实现

// 在AVL树中插入值为data的节点
bool Insert(const T& data)
{
if (_pRoot == nullptr)
{
_pRoot = new Node(data);
return true;
}
else
{
Node* dest = _pRoot, *cur = nullptr;
while (dest)
{
if (data < dest->_data)
{
cur = dest;
dest = dest->_pLeft;
}
else if (dest->_data < data)
{
cur = dest;
dest = dest->_pRight;
}
else
{
return false;
}
}
dest = new Node(data);
if (data < cur->_data)
{
cur->_pLeft = dest;
}
else if (cur->_data < data)
{
cur->_pRight = dest;
}
dest->_pParent = cur;
// 向上调整平衡数
Bf(cur);
while (cur != nullptr && abs(cur->_bf) < 2)
{
cur = cur->_pParent;
Bf(cur);
}
// 如果没有问题直接退出有平衡失衡的情况就进行旋转
if (cur == nullptr)
return true;
else if (cur->_bf == 2)
{
if (cur->_pLeft->_bf == 1)
{
RotateR(cur);
}
else if(cur->_pLeft->_bf == -1)
{
RotateLR(cur);
}
}
else if (cur->_bf == -2)
{
if (cur->_pRight->_bf == 1)
{
RotateRL(cur);
}
else if (cur->_pRight->_bf == -1)
{
RotateL(cur);
}
}
else
{
assert(false);
}
return true;
}

}

2.3 旋转

2.3.1 旋转的原则

旋转核心原则：不破坏二叉搜索树有序性，同时修正失衡，调整子树高度、更新平衡因子。

2.3.2 右单旋

// 考虑问题:
// 1,是否有 Chlid 的 左右节点是否为空(但其实右旋时就R 可能就是为空出现的可能比较小,出现的话就已经被判断需要双旋了)
// 2,考虑是否有 GrandParent 有需要进行两线对接，没有就需要进行提上来的 Child 的 Parent 为空
// 右单旋
void RotateR(Node* pParent)
{ // G G
// P C
// C -> L P
// L R R
//
// pParent -> P
//
// 最有可能发生_pRoot 位置就是 P 和 G ，其中 G 改变只是其中个别位置，对_pRoot 没有影响下
// 其中要关注就是 _pRoot 的 P 位置 和 C 位置

Node* Child = pParent->_pLeft;//C
Node* Parent = pParent;//P
Node* GrandParent = pParent->_pParent;//G

// 4 段代码维护
// P->C = P->R
Parent->_pLeft = Child->_pRight;
// R->P = R->P
if (Child->_pRight != nullptr)
{
Child->_pRight->_pParent = Parent;
}
// C->R = C->P
Child->_pRight = Parent;
// P->G = P->C
Parent->_pParent = Child;
// G->P = G->C
if (GrandParent != nullptr)
{
GrandParent->_pLeft == Parent ? GrandParent->_pLeft = Child : GrandParent->_pRight = Child;
// C->P = C->G
Child->_pParent = GrandParent;
}
else
{
// C->P = C->nullptr
Child->_pParent = nullptr;
_pRoot = Child;
}
// 调整平衡
Bf(Parent);
Bf(Child);
}

2.3.3 左单旋

// 左单旋
void RotateL(Node* pParent)
{ // G G
// P C
// C -> P R
// L R L
// pParent -> P
// 最有可能发生_pRoot 位置就是 P 和 G ，其中 G 改变只是其中个别位置，对_pRoot 没有影响下
// 其中要关注就是 _pRoot 的 P 位置 和 C 位置
// 4 段代码维护
// P->C = P->L

Node* Child = pParent->_pRight;//C
Node* Parent = pParent;//P
Node* GrandParent = pParent->_pParent;//G
// 4 段代码维护
// P->C = P->L
Parent->_pRight = Child->_pLeft;
// L->C = L->P
if (Child->_pLeft != nullptr)
{
Child->_pLeft->_pParent = Parent;
}
// C->L = C->P
Child->_pLeft = Parent;
// P->G = P->C
Parent->_pParent = Child;
if (GrandParent != nullptr)
{
// G->P = G->C
GrandParent->_pLeft == Parent ? GrandParent->_pLeft = Child : GrandParent->_pRight = Child;
// C->P = C->G
Child->_pParent = GrandParent;
}
else
{
// C->P = C->nullptr
Child->_pParent = nullptr;
_pRoot = Child;
}
// 调整平衡
Bf(Parent);
Bf(Child);
}

2.3.4 左右双旋

在部分情况种单旋已经没有办法满足了所有需要双旋来满足，第一次旋转是为了结构变成，符合左右单旋的结构。其次双旋可以复用前面的代码，以便于理解也可以不用写太多代码。

// 左右双旋
void RotateLR(Node* pParent)
{
/*
a a c
b -> c-> b a
c b
b->pParent
优先 c 进行 左旋
因为 c 进行 右旋
*/
RotateL(pParent->_pLeft);
RotateR(pParent);
}

2.3.5 右左双旋

// 右左双旋
void RotateRL(Node* pParent)
{// pParent -> a
/*
a a c
b -> c-> b a
c b
b->pParent
优先 c 进行 右旋
因为 c 进行 左旋
*/
RotateR(pParent->_pRight);
RotateL(pParent);
}

2.4 AVL 树的查找

AVL 树的查找过程和普通二叉搜索树查找逻辑一致。从根节点出发，拿目标值和当前节点比较：目标更小就去往左子树查找，目标更大就去往右子树查找，相等则查找成功。如果走到空节点，代表查找失败。 区别在于 AVL 树受平衡约束限制，树高稳定为 logn，查找最坏时间复杂度是 O (log n)，不会像普通 BST 那样退化成 O (n)。查找过程不会修改树结构、不改动高度和平衡因子，也不会触发旋转。

2.5 AVL 树的平衡检查

// AVL树的验证
bool IsAVLTree()
{
return _IsAVLTree(_pRoot);
}
private:
// 根据AVL树的概念验证pRoot是否为有效的AVL树
bool _IsAVLTree(Node* pRoot)
{
if (pRoot == nullptr)
{
return true;
}
bool put = _IsAVLTree(pRoot->_pLeft);
if (put == false || abs(pRoot->_bf) >= 2)
{
cout << "节点平衡异常" << endl;

return false;
}
put = _IsAVLTree(pRoot->_pRight);
return put;
}

2.6 AVL树的删除

删除的原理其实与插入的原理一致，由二叉搜索树的删除原理，在加上对应位置旋转操作即可。

AVLTree · 浪子·悠仁/C++ 知识库 – 码云 – 开源中国