文章目录

引言一、AVL树的概念二、AVL树的模拟实现2.1 结点2.2 成员变量2.3 插入2.4 旋转2.4.1 左单旋2.4.2 右单旋2.4.3 左右旋2.4.4 右左旋

三、AVL树的验证四、AVL树的性能4.1 优势4.2 缺陷4.3 适用场景

引言

之前讲解了二叉搜索树，最优情况下它具有非常好的搜索性能，但是在极端场景下，它可能退化为单支树，可以形象地称为歪脖子树~

这样的话，它搜索的时间复杂度会从O(log₂N)退化为O(N²)，完全丧失了其优良的搜索性能。那么AVL树就可以登场了，它就是为解决这类问题而生的！

一、AVL树的概念

两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了AVL树，AVL树满足两条性质：

它的左右子树都是AVL树任意结点的左右子树高度差的绝对值不超过1

这样通过控制子树高度差，让AVL树几乎完美接近于平衡，便不会出现单支树的情况，保证了优良的搜索性能，因此AVL树又称为高度平衡二叉搜索树。

二、AVL树的模拟实现

2.1 结点

<code>template<class K, class V>

struct AVLTreeNode

{

AVLTreeNode<K, V>* _left;

AVLTreeNode<K, V>* _right;

AVLTreeNode<K, V>* _parent;

pair<K, V> _kv;

int _bf;//balance factor

AVLTreeNode(const pair<K, V>& kv)

: _left(nullptr)

, _right(nullptr)

, _parent(nullptr)

, _kv(kv)

, _bf(0)

{ }

};

细节：

使用三叉链，增加了指向parent的指针使用KV模型，数据存储键值对pair结点存储平衡因子，用来记录左右子树高度差

注：平衡因子计算高度差，是 右子树高度 - 左子树高度

2.2 成员变量

template<class K, class V>

class AVLTree

{

protected:

typedef AVLTreeNode<K, V> Node;

public:

protected:

Node* _root = nullptr;

};

2.3 插入

因为AVL树也是二叉搜索树，所以默认成员函数和遍历与之前写的没什么不同，这里重点讲解AVL树的插入。

bool Insert(const pair<K, V>& kv)

{

if (_root == nullptr)

{

_root = new Node(kv);

return true;

}

Node* parent = nullptr;

Node* cur = _root;

while (cur)

{

if (cur->_kv.first < kv.first)

{

parent = cur;

cur = cur->_right;

}

else if (cur->_kv.first > kv.first)

{

parent = cur;

cur = cur->_left;

}

else

{

return false;

}

}

cur = new Node(kv);

if (parent->_kv.first < kv.first)

{

parent->_right = cur;

}

else

{

parent->_left = cur;

}

cur->_parent = parent;

while (parent)//讨论平衡因子

{

if (cur == parent->_right)

{

++parent->_bf;

}

else

{

--parent->_bf;

}

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

{

parent = parent->_parent;

cur = cur->_parent;

}

else if (parent->_bf == 0)

{

break;

}

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

}

else

{

assert(false);

}

break;

}

else

{

assert(false);

}

}

return true;

}

思路：

以二叉搜索树的方式正常插入讨论平衡因子，以及调整结构

这里的重点在于如何讨论和调整平衡因子(bf)。

首先，插入cur结点，调整parent结点的bf，左减右加讨论parent的bf

bf为0bf为1或-1bf为2或-2

bf为0时：

分析：此时没有增加高度，而是补上缺口，整棵树是平衡的，直接break即可

bf为1或-1时：

分析：此时增加了局部子树的高度，不确定有没有影响整体的高度差，所以要继续向上调整

<code>parent = parent->_parent;

cur = cur->_parent;

bf为2或-2时：

此时bf已经超出平衡限制区间，需要进行结构调整，我们称之为旋转。

2.4 旋转

旋转分为两大类：单旋和双旋。而单旋分为左单旋和右单旋，双旋分为左右旋和右左旋。

2.4.1 左单旋

场景：右部外侧插入

过程：

parent接过subR的左子树subRLsubR左边再链接parent

<code>void RotateL(Node* parent)//左单旋

{

Node* grandparent = parent->_parent;

Node* subR = parent->_right;

Node* subRL = subR->_left;

parent->_right = subRL;

if (subRL)

{

subRL->_parent = parent;

}

subR->_left = parent;

parent->_parent = subR;

if (grandparent)

{

if (grandparent->_right == parent)

{

grandparent->_right = subR;

}

else

{

grandparent->_left = subR;

}

}

else

{

_root = subR;

}

subR->_parent = grandparent;

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

}

细节：

大体是三步链接，注意双向链接注意判空（subRL，grandparent）如果判空，注意_root的传递最后调整平衡因子_bf

2.4.2 右单旋

场景：左部外侧插入

过程：

parent接过subL的右子树subLRsubL右边再链接parent

<code>void RotateR(Node* parent)//右单旋

{

Node* grandparent = parent->_parent;

Node* subL = parent->_left;

Node* subLR = subL->_right;

parent->_left = subLR;

if (subLR)

{

subLR->_parent = parent;

}

subL->_right = parent;

parent->_parent = subL;

if (grandparent)

{

if (grandparent->_right == parent)

{

grandparent->_right = subL;

}

else

{

grandparent->_left = subL;

}

}

else

{

_root = subL;

}

subL->_parent = grandparent;

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

}

细节：同左单旋

2.4.3 左右旋

场景：左部内侧插入

过程：

先对subL进行左单旋再对parent进行右单旋

<code>void RotateLR(Node* parent)//左右旋

{

Node* subL = parent->_left;

Node* subLR = subL->_right;

int bf = subLR->_bf;

RotateL(subL);

RotateR(parent);

if (bf == 1)

{

subL->_bf = -1;

subLR->_bf = 0;

parent->_bf = 0;

}

else if (bf == -1)

{

subL->_bf = 0;

subLR->_bf = 0;

parent->_bf = 1;

}

else if (bf == 0)

{

subL->_bf = 0;

subLR->_bf = 0;

parent->_bf = 0;

}

else

{

assert(false);

}

}

细节：

这里旋转直接复用前面单旋的代码主要的重点，在于平衡因子bf的讨论

bf为1，在subLR的右侧插入bf为-1，在subLR的左侧插入bf为0，插入subLR（之前为空）

2.4.4 右左旋

场景：右部内侧插入

过程：

先对subR进行右单旋再对parent进行左单旋

<code>void RotateRL(Node* parent)//右左旋

{

Node* subR = parent->_right;

Node* subRL = subR->_left;

int bf = subRL->_bf;

RotateR(subR);

RotateL(parent);

if (bf == 1)

{

parent->_bf = -1;

subRL->_bf = 0;

subR->_bf = 0;

}

else if (bf == -1)

{

parent->_bf = 0;

subRL->_bf = 0;

subR->_bf = 1;

}

else if (bf == 0)

{

parent->_bf = 0;

subRL->_bf = 0;

subR->_bf = 0;

}

else

{

assert(false);

}

}

细节：同左右旋

综上所述，旋转的目的：保证平衡，同时降低树的高度。

三、AVL树的验证

我们主要验证左右子树高度是否平衡，即高度差是否小于等于1

bool IsBalance()

{

return _IsBalance(_root);

}

int Height(Node* root)

{

if (root == nullptr)

{

return 0;

}

int leftH = Height(root->_left);

int rightH = Height(root->_right);

return leftH > rightH ? leftH + 1 : rightH + 1;

}

bool _IsBalance(Node* root)

{

if (root == nullptr)

{

return true;

}

int leftH = Height(root->_left);

int rightH = Height(root->_right);

if (rightH - leftH != root->_bf)

{

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

return false;

}

return abs(rightH - leftH) <= 1

&& _IsBalance(root->_left)

&& _IsBalance(root->_right);

}

细节：

为了方便计算高度，写一个Height函数在子函数递归中，计算高度差是否小于等于1与此同时，还要检查平衡因子是否正常

四、AVL树的性能

4.1 优势

AVL树是一棵绝对平衡的二叉搜索树，其要求每个节点的左右子树高度差的绝对值都不超过1，这样可以保证查询时高效的时间复杂度，即

l

o

g

2

(

N

)

log_2 (N)

log2​(N)。

4.2 缺陷

但是如果要对AVL树做一些结构修改的操作，性能非常低下，比如：插入时要维护其绝对平衡，旋转的次数比较多，更差的是在删除时，有可能一直要让旋转持续到根的位置。

4.3 适用场景

因此，如果需要一种查询高效且有序的数据结构，而且数据的个数为静态的(即不会改变)，可以考虑AVL树，但一个结构经常修改，就不太适合。