开发语言 数据结构 算法 【C++】AVL树

AVL树

一、AVL树概念二、AVL树实现1. AVL树节点的定义2. AVL树的定义3. AVL树的插入4. AVL树的验证

一、AVL树概念

二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树，查找元素相当于在顺序表中搜索元素，效率低下。因此，两位俄罗斯的数学家 G.M.Adelson-Velskii 和 E.M.Landis 在 1962 年发明了一种解决上述问题的方法：当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度。

一棵 AVL树 或者是 空树，或者是具有以下性质的二叉搜索树：

它的左右子树都是AVL树左右子树高度之差(简称平衡因子，等于右子树高度 - 左子树高度)的绝对值不超过1(-1/0/1)

如下是一颗 AVL 树，蓝色数字代表平衡因子：

二、AVL树实现

1. AVL树节点的定义

想要实现一个AVL树 ，首先我们得有树的节点，而树的节点中我们需要存：该节点的父节点、该节点的右孩子、该节点的左孩子、平衡因子以及数据类型；为了方便后面红黑树的学习我们在这里给的数据类型是 pair，大家也可以定义成其他类型；代码如下：

template

struct AVLTreeNode

{

AVLTreeNode* _left; // 左孩子

AVLTreeNode* _right; // 右孩子

AVLTreeNode* _parent; // 父节点

pair _kv; // 数据类型

int _bf; // 平衡因子

AVLTreeNode(const pair& kv)

:_left(nullptr)

,_right(nullptr)

,_parent(nullptr)

,_kv(kv)

,_bf(0)

{}

};

2. AVL树的定义

AVL树的定义如下：

template

class AVLTree

{

typedef AVLTreeNode Node;

private:

Node* _root = nullptr;

};

3. AVL树的插入

AVL树就是在二叉搜索树的基础上引入了平衡因子，因此AVL树也可以看成是二叉搜索树。那么AVL树的插入过程可以分为两步：

按照二叉搜索树的方式插入新节点调整节点的平衡因子并进行旋转

所以我们先按照原来二叉搜索树的插入逻辑插入节点，插入节点后再进行其它操作，代码如下：

bool Insert(const pair& kv)

{

if (_root == nullptr)

{

_root = new Node(kv);

return true;

}

Node* parent = nullptr, * cur = _root;

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 > kv.first)

{

parent->_left = cur;

cur->_parent = parent;

}

else

{

parent->_right = cur;

cur->_parent = parent;

}

}

新节点插入后，AVL树的平衡性可能会遭到破坏，此时就需要更新平衡因子，并检测是否破坏了AVL树的平衡性。新增可能会影响祖先节点，此时需要判断子树的高度是否发生变化，如果子树高度不变，就不会继续往上影响祖先；如果子树高度发生变化，就会继续往上影响祖先。

因为平衡因子 = 右子树高度 - 左子树高度，所以新增节点在左子树，父节点的 _bf–；新增节点在右子树，父节点的 _bf++；

更新平衡因子

更新平衡因子后有以下三种情况：

父节点更新后 _bf == 0，说明父节点所在的子树高度不变，不用继续往上更新了，插入结束；如下图所示：

如上图，在插入新节点前，父节点(8所在的节点) _bf == 1 or -1，是一边高一边低，新插入的节点填上低的那边。

父节点更新后，_bf == 1 or -1，父节点所在的子树高度发生变化，必须继续往上更新；如下图所示：

如上图，在插入节点前，父节点(8所在的节点)的 _bf == 0，两边一样高，插入导致高度发生了变化。

父节点更新后，_bf == 2 or -2，父节点所在的子树破坏了AVL树的平衡，需要调整处理；如下图所示：

所以更新平衡因子的代码如下，续上面的代码：

// 循环的结束条件有：1、parent 为空；2、平衡因子为0；3、旋转完成

while (parent)

{

// 更新平衡因子

if (cur == parent->_left)

{

parent->_bf--;

}

else

{

parent->_bf++;

}

// 插入后左右子树变平衡

if (parent->_bf == 0)

{

break;

}

// 插入后左右子树高度差为1，继续往上更新

else if (parent->_bf == 1 || parent->_bf == -1)

{

cur = parent;

parent = parent->_parent;

}

// 插入后左右子树高度差超过1，需要调整旋转

else if (parent->_bf == 2 || parent->_bf == -2)

{

// 旋转

}

// 当走到这里说明这棵树有问题，直接报错

else

{

assert(false);

}

}

旋转

如果在一棵原本是平衡的AVL树中插入一个新节点，可能造成不平衡，此时必须调整树的结构，使之平衡化。根据节点插入位置的不同，AVL树的旋转分为四种：

新节点插入较高右子树的右侧- - -右右- - - 右边高：左单旋

没插入之前如下图，30 的右子树高度为 h+1，左子树高度为 h，所以平衡因子为1.

当新插入节点在较高右子树的右侧，即在 c 子树的位置插入；以上这个图叫做抽象图，因为情况太多了画不完，所以用抽象图表示更为直观；要在 c 子树插入引起旋转，那么 c 一定为高度为 h 的满AVL树或者空树，a 和 b 就不一定。

我们在 c 子树插入节点，导致以 30 为根的二叉树不平衡，要让它平衡，只能想办法让右子树的高度减少一层，左子树的高度增加一层；即将 60 往上提，30 旋转下来；因为 60 比 30 大，所以 60 所在的子树都比 30 大，所以我们可以将 60 的左子树接到 30 的右边，然后让 60 去做新的根，60 的左边更新为新的 30 的子树；如下图所示：

在旋转过程中，有以下几种情况需要考虑： （1）60 节点的左孩子可能存在，也可能不存在 （2）30 可能是根节点，也可能是子树；如果是根节点，旋转完成后，要更新根节点；如果是子树，可能是某个节点的左子树，也可能是右子树。 （3）旋转完成后，30 和 60 的 _bf 都变成了 0.

所以左单旋的代码如下：

// 左单旋

void RotateL(Node* parent)

{

Node* subR = parent->_right, * subRL = subR->_left;

parent->_right = subRL;

if (subRL)

subRL->_parent = parent;

subR->_left = parent;

Node* parentParent = parent->_parent;

parent->_parent = subR;

// 如果 parent 是根节点，就直接更新 subR 为根节点，并将 subR 的_parent指向空

if (_root == parent)

{

_root = subR;

subR->_parent = nullptr;

}

// 否则，先判断 parent 是 parentParent 的右还是左，再将parentParent的左或者右连接subR

else

{

if (parentParent->_left == parent)

{

parentParent->_left = subR;

}

else

{

parentParent->_right = subR;

}

subR->_parent = parentParent;

}

// 最后更新 _bf

subR->_bf = parent->_bf = 0;

}

新节点插入较高左子树的左侧- - -左左- - -左边高：右单旋

没插入之前如下图，60 的右子树高度为 h，左子树高度为 h+1，所以平衡因子为 -1.

与左单旋的分析类似，右单旋中，是在 a 的子树中插入新节点，因为 30 是 60 的左子树，所以 30 这颗子树都比 60 要小，所以可以将 30 的右子树变成 60 的左子树，然后让 30 成为新的根，再让 60 这颗新的子树成为 30 的右子树。如下图所示：

我们可以观察到，无论是左单旋还是右单旋，从新插入节点到根节点的线条是一条直线；我们可以以此作为与下面双旋的区分；如下图：

在旋转过程中，有以下几种情况需要考虑： （1）30 节点的右孩子可能存在，也可能不存在。 （2）60 可能是根节点，也可能是子树；如果是根节点，旋转完成后，要更新根节点；如果是子树，可能是某个节点的左子树，也可能是右子树。 （3）旋转完成后，30 和 60 的 _bf 都变成了 0.

所以右单旋的代码如下：

// 右单旋

void RotateR(Node* parent)

{

Node* subL = parent->_left, * subLR = subL->_right;

parent->_left = subLR;

if (subLR)

subLR->_parent = parent;

subL->_right = parent;

Node* parentParent = parent->_parent;

parent->_parent = subL;

if (_root == parent)

{

_root = subL;

subL->_parent = nullptr;

}

else

{

if (parentParent->_left == parent)

{

parentParent->_left = subL;

}

else

{

parentParent->_right = subL;

}

subL->_parent = parentParent;

}

subL->_bf = parent->_bf = 0;

}

新节点插入较高左子树的右侧- - -左右：先左单旋再右单旋(左右双旋)

如下图所示，我们无论在 subLR 节点的左右子树(是满AVL树的前提下)插入的时候，会改变 subLR 的高度，进而会往上更新，一直更新到根 parent，此时单旋就满足不了这种情况了：

通过观察可以得到，我们从 subLR 的左右子树插入新节点，那么新节点到 parent 根节点的线条是一条折线，通过这种方法可以区分不同的旋转；如下图所示：

于是我们有以下方法解决：将双旋变成单旋后再旋转，即：先对以 subL 节点的子树进行左单旋，然后再对 parent 节点为子树进行右单旋，旋转完成后再考虑平衡因子的更新。如下图所示：

因为我们只能从 b 或 c 子树插入新节点，那么我们怎么区分它在哪里插入的呢？通过观察我们可以发现，在 b 或者 c 子树插入新节点，一定会影响 subLR；所以分为以下三种情况：

当在 subLR 的左子树插入， subLR 的 _bf 就变成了 -1；此时旋转完成后，parent 的 _bf 变为 1，subL 和 subLR 的 _bf 都变成了 0. 当在 subLR 的右子树插入，subLR 的 _bf 就变成了 1；此时旋转完成后，subL 的 _bf 变为 1，parent 和 subLR 的 _bf 都变成了 0. 当 subLR 本身就是新增节点， subLR 的 _bf 就是 0；此时旋转完成后 parent 、subLR 和 subL 的 _bf 都是 0.

所以我们可以根据 subLR 的 _bf 来对这三种情况进行区分。代码如下：

// 左右双旋

void RotateLR(Node* parent)

{

Node* subL = parent->_left, * subLR = subL->_right;

int bf = subLR->_bf;

RotateL(parent->_left);

RotateR(parent);

if (bf == 0)

{

parent->_bf = subLR->_bf = subL->_bf = 0;

}

else if (bf == -1)

{

parent->_bf = 1;

subLR->_bf = subL->_bf = 0;

}

else if (bf == 1)

{

subL->_bf = -1;

parent->_bf = subLR->_bf = 0;

}

else

{

assert(false);

}

}

新节点插入较高右子树的左侧—右左：先右单旋再左单旋(右左双旋)

如下图所示，我们无论在 subRL 节点的左右子树(是满AVL树的前提下)插入的时候，会改变 subRL 的高度，进而会往上更新，一直更新到根 parent，此时单旋就满足不了这种情况了：

右左双旋中新插入节点到 parent 的线条折线为：

分析过程与左右双旋类似：

当在 subRL 的左子树插入， subRL 的 _bf 就变成了 -1；此时旋转完成后，subR 的 _bf 变为 1，parent 和 subRL 的 _bf 都变成了 0. 当在 subRL 的右子树插入，subRL 的 _bf 就变成了 1；此时旋转完成后，parent 的 _bf 变为 -1，subR 和 subRL 的 _bf 都变成了 0. 当 subRL 本身就是新增节点， subRL 的 _bf 就是 0；此时旋转完成后 parent 、subRL 和 subR 的 _bf 都是 0.

如下图所示：

代码如下：

// 右左双旋

void RotateRL(Node* parent)

{

Node* subR = parent->_right, * subRL = subR->_left;

int bf = subRL->_bf;

RotateR(parent->_right);

RotateL(parent);

// 新增节点就是 subRL

if (bf == 0)

{

parent->_bf = subR->_bf = subRL->_bf = 0;

}

// subRL 的右子树新增节点

else if (bf == 1)

{

parent->_bf = -1;

subR->_bf = subRL->_bf = 0;

}

// subRL 的左子树新增节点

else if (bf == -1)

{

subR->_bf = 1;

parent->_bf = subRL->_bf = 0;

}

else

{

assert(false);

}

}

其中完整的插入代码如下：

bool Insert(const pair& kv)

{

if (_root == nullptr)

{

_root = new Node(kv);

return true;

}

Node* parent = nullptr, * cur = _root;

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 > kv.first)

{

parent->_left = cur;

cur->_parent = parent;

}

else

{

parent->_right = cur;

cur->_parent = parent;

}

// 循环的结束条件有：1、parent 为空；2、平衡因子为0；3、旋转完成

while (parent)

{

// 更新平衡因子

if (cur == parent->_left)

{

parent->_bf--;

}

else

{

parent->_bf++;

}

// 插入后左右子树变平衡

if (parent->_bf == 0)

{

break;

}

// 插入后左右子树高度差为1，继续往上更新

else if (parent->_bf == 1 || parent->_bf == -1)

{

cur = parent;

parent = parent->_parent;

}

// 插入后左右子树高度差超过1，需要调整旋转

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);

}

break;

}

// 当走到这里说明这棵树有问题

else

{

assert(false);

}

}

return true;

}

4. AVL树的验证

AVL树是在二叉搜索树的基础上加入了平衡性的限制，因此要验证AVL树，可以分两步：

验证其为二叉搜索树 如果中序遍历可得到一个有序的序列，就说明为二叉搜索树验证其为平衡树 每个节点子树高度差的绝对值不超过1(注意节点中如果没有平衡因子)，就说明为平衡树

按中序打印结果，验证是否是搜索二叉树：

void InOrder()

{

_InOrder(_root);

}

void _InOrder(Node* root)

{

if (root == nullptr)

return;

_InOrder(root->_left);

cout << root->_kv.first << " ";

_InOrder(root->_right);

}

验证是否是平衡树：

bool IsBalance()

{

return _IsBalance(_root);

}

bool _IsBalance(Node* root)

{

if (root == nullptr)

return true;

int leftHeight = _Height(root->_left);

int rightHeight = _Height(root->_right);

if (rightHeight - leftHeight != root->_bf)

{

cout << root->_kv.first << "平衡因子异常" << endl;

return false;

}

return abs(leftHeight - rightHeight) <= 1

&& _IsBalance(root->_left)

&& _IsBalance(root->_right);

}

int Height()

{

return _Height(_root);

}

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;

}

下面我们开始生成一些随机数插入 AVL树 中，观察是否有问题；代码如下：

int main()

{

const int N = 200;

vector v;

v.reserve(N);

srand(time(0));

for (size_t i = 0; i < N; i++)

v.push_back(rand());

AVLTree t;

for (auto e : v)

t.Insert(make_pair(e, e));

t.InOrder();

if (t.IsBalance())

cout << "AVL树正常" << endl;

else

cout << "AVL树异常" << endl;

return 0;

}

我们随机生成 200 个数插入到 AVL树 中，观察是否正常：

如上图，我们就验证了我们写的AVL树是没有问题的。

参考阅读