算法 笔记 学习 数据结构：AVL树讲解（C++）

AVL树

1.AVL树的概念2.平衡因子3.节点的定义4.插入操作5.旋转操作（重点）5.1左单旋5.2右单旋5.3左右双旋5.4右左双旋

6.一些简单的测试接口7.完整代码

1.AVL树的概念

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

它的左右子树都是AVL树左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1)如果一棵二叉搜索树是高度平衡的，它就是AVL树。如果它有n个结点，其高度可保持在

O

(

l

o

g

2

n

)

O(log_2 n)

O(log2​n)，搜索时间复杂度O(

l

o

g

2

n

log_2 n

log2​n)。

2.平衡因子

AVL树的实现有很多种，本文引入平衡因子来维持高度稳定。 本文平衡因子的定义：右子树高度 - 左子树的高度。 依据每个节点的平衡因子，我们可以判断树的情况：

平衡因子在(-1, 0, 1)，当前节点所在子树是稳定的。平衡因子为2或-2，当前节点所在子树是不稳定的。

插入节点后平衡因子的更新：

插入节点在右子树，平衡因子加一。插入节点在左子树，平衡因子减一。

插入节点后平衡因子的不同情况（重点）：

当前节点所在子树平衡因子为0，子树高度不变，不需要更新（原来一边高一边低，新插入在低一方，变成完全平衡）。当前节点所在子树平衡因子为1或-1，子树高度变化，需要向上更新。（原来完全平衡，现在一边高，子树整体高度加1，会影响到祖先的平衡，故需要向上更新看祖先所在子树是否平衡）当前节点所在子树平衡因子为2或-2，子树高度变化且不平衡，无需向上更新，对当前子树进行旋转操作。（当前子树已不平衡，向上更新没有意义，旋转操作是AVL树的核心，可以降低当前子树的高度且不影响上面的树结构）

3.节点的定义

节点除了需要增加一个平衡因子，还需要增加一个父亲指针，方便我们进行平衡因子的向上更新和旋转操作。

template

struct ALVTreeNode

{

ALVTreeNode* _left;

ALVTreeNode* _right;

ALVTreeNode* _parent;

pair _kv; //存储键值对

int _bf; //平衡因子

ALVTreeNode(const pair& kv)

:_left(nullptr)

,_right(nullptr)

,_parent(nullptr)

,_bf(0)

,_kv(kv)

{}

};

4.插入操作

PS：因为多加了一个父亲指针，所以插入时要注意更新父亲指针，平衡因子更新按前面的分析来还是比较简单的，旋转操作后面单独讲。

bool Insert(const pair& kv)

{

if (_root == nullptr) //一开始为空树，直接插入即可

{

_root = new Node(kv);

return true;

}

//找插入位置加插入

Node* cur = _root; //记录插入位置

Node* parent = nullptr; //待插入位置的父亲

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

if (kv.first > parent->_kv.first) //插入在父亲的右边

{

parent->_right = cur;

}

else //插入在父亲的左边

{

parent->_left = cur;

}

cur->_parent = parent; //注意更新父亲指针

//调整平衡因子

while (parent) //是有可能调整到根部的

{

if (cur == parent->_right) //如果新插入的在右子树

{

parent->_bf++;

}

else if (cur == parent->_left) //如果新插入的在左子树

{

parent->_bf--;

}

if (parent->_bf == 0) //插入后高度不变

{

break;

}

else if (parent->_bf == 1 || parent->_bf == -1) //插入后高度变化，但当前子树依然平衡，需要向上更新

{

parent = parent->_parent;

cur = cur->_parent;

}

else if (parent->_bf == 2 || parent->_bf == -2) //插入后高度变化，并且当前子树已经不平衡,旋转

{

//旋转操作（先省略）

break;

}

else //存在大于2小于-2的情况，树原来就不平衡，应该报错

{

assert(false);

}

}

return true;

}

5.旋转操作（重点）

5.1左单旋

主体思想：

平衡因子的调整：

代码加细节处理：

void RotateL(Node* parent) //左单旋,rotate->旋转

{

Node* SubR = parent->_right;

Node* SubRL = SubR->_left; //这个有可能为空

Node* ppnode = parent->_parent; //原来父亲的父亲

parent->_right = SubRL;

if(SubRL) SubRL->_parent = parent;

SubR->_left = parent;

parent->_parent = SubR;

if (ppnode == nullptr) //旋转的是整颗树

{

_root = SubR;

SubR->_parent = nullptr;

}

else //旋转的是部分

{

if (ppnode->_left == parent) //是左子树

{

ppnode->_left = SubR;

}

else //是右子树

{

ppnode->_right = SubR;

}

SubR->_parent = ppnode;

}

//最后更新平衡因子

parent->_bf = SubR->_bf = 0;

}

5.2右单旋

PS：右单旋和左单旋类似，细节处理也差不多，这里只讲主体思路。 主体思路：

平衡因子的调整：

代码：

void RotateR(Node* parent) //右单旋细节处理和左单旋差不多

{

Node* SubL = parent->_left;

Node* SubLR = SubL->_right; //这个有可能为空

Node* ppnode = parent->_parent;

parent->_left = SubLR;

if(SubLR) SubLR->_parent = parent;

SubL->_right = parent;

parent->_parent = SubL;

if (ppnode == nullptr) //旋转的是整颗树

{

_root = SubL;

SubL->_parent = nullptr;

}

else //旋转部分

{

if (ppnode->_left == parent) //是左子树

{

ppnode->_left = SubL;

}

else //右子树

{

ppnode->_right = SubL;

}

SubL->_parent = ppnode;

}

//最后更新平衡因子

parent->_bf = SubL->_bf = 0;

}

5.3左右双旋

PS：双旋其实就是两次单旋(复用即可)，有前面的基础很好理解，重点在于旋转后平衡因子的更新。

旋转思路：

平衡因子的调整： 想知道平衡因子调整是那种情况，我们需要在旋转前记录SubRL的平衡因子bf：

bf为0是第一种情况。bf为1是第二种情况。bf为-1是第三种情况。

代码：

void RotateLR(Node* parent) //左右双旋

{

Node* SubL = parent->_left;

Node* SubLR = SubL->_right;

int bf = SubLR->_bf;

RotateL(SubL);

RotateR(parent);

if (bf == 1) //插入的是右边

{

SubLR->_bf = 0;

SubL->_bf = -1;

parent->_bf = 0;

}

else if (bf == -1) //插入的是左边

{

SubLR->_bf = 0;

SubL->_bf = 0;

parent->_bf = 1;

}

else if (bf == 0) //刚好原来parent的左边就两个节点

{

SubLR->_bf = SubL->_bf = parent->_bf = 0;

}

else //原来就不是平衡树，出现问题

{

assert(false);

}

}

5.4右左双旋

PS：右左双旋和左右双旋思路是差不多的，重点还是在旋转后平衡因子的更新。

旋转思路：

平衡因子的调整： 和前面一样，旋转前确认SubRL的平衡因子bf即可。

代码：

void RotateRL(Node* parent) //右左双旋

{

Node* SubR = parent->_right;

Node* SubRL = SubR->_left;

int bf = SubRL->_bf;

RotateR(SubR);

RotateL(parent);

if (bf == 1) //插入的是右边

{

SubRL->_bf = 0;

SubR->_bf = 0;

parent->_bf = -1;

}

else if (bf == -1) //插入的是左边

{

SubRL->_bf = 0;

parent->_bf = 0;

SubR->_bf = 1;

}

else if (bf == 0) //原来parent的右边就两个节点

{

SubRL->_bf = SubR->_bf = parent->_bf = 0;

}

else //原来就有问题

{

assert(false);

}

}

6.一些简单的测试接口

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;

}

bool IsBalance()

{

return IsBalance(_root);

}

//看当前树是不是平衡树

//（1）看每个子树是否满足左右子树高度差不超过一

//（2）看平衡因子和所求的左右子树高度差是否一致

bool IsBalance(Node* root)

{

if (root == nullptr)

return true;

int leftHight = _Height(root->_left);

int rightHight = _Height(root->_right);

if (rightHight - leftHight != root->_bf)

{

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

return false;

}

return abs(rightHight - leftHight) < 2

&& IsBalance(root->_left)

&& IsBalance(root->_right);

}

7.完整代码

#pragma once

#include

#include

#include

using namespace std;

template

struct ALVTreeNode

{

ALVTreeNode* _left;

ALVTreeNode* _right;

ALVTreeNode* _parent;

pair _kv; //存储键值对

int _bf;

ALVTreeNode(const pair& kv)

:_left(nullptr)

,_right(nullptr)

,_parent(nullptr)

,_bf(0)

,_kv(kv)

{}

};

template

class AVLTree

{

public:

typedef ALVTreeNode Node;

bool Insert(const pair& kv)

{

if (_root == nullptr) //一开始为空树，直接插入即可

{

_root = new Node(kv);

return true;

}

Node* cur = _root; //记录插入位置

Node* parent = nullptr; //待插入位置的父亲

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

if (kv.first > parent->_kv.first) //插入在父亲的右边

{

parent->_right = cur;

}

else //插入在父亲的左边

{

parent->_left = cur;

}

cur->_parent = parent;

//调整平衡因子

while (parent) //是有可能调整到根部的

{

if (cur == parent->_right) //如果新插入的是右子树

{

parent->_bf++;

}

else if (cur == parent->_left) //如果新插入的是左子树

{

parent->_bf--;

}

if (parent->_bf == 0) //插入后高度不变

{

break;

}

else if (parent->_bf == 1 || parent->_bf == -1) //插入后高度变化，但当前子树依然平衡，需要向上更新

{

parent = parent->_parent;

cur = cur->_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) //左子树的右边高，左右双旋

{

RotateLR(parent);

}

else if (parent->_bf == 2 && cur->_bf == -1) //右子树的左边高，右左双旋

{

RotateRL(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 leftHeight = _Height(root->_left);

int rightHeight = _Height(root->_right);

return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;

}

bool IsBalance()

{

return IsBalance(_root);

}

//看当前树是不是平衡树

//（1）看每个子树是否满足左右子树高度差不超过一

//（2）看平衡因子和所求的左右子树高度差是否一致

bool IsBalance(Node* root)

{

if (root == nullptr)

return true;

int leftHight = _Height(root->_left);

int rightHight = _Height(root->_right);

if (rightHight - leftHight != root->_bf)

{

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

return false;

}

return abs(rightHight - leftHight) < 2

&& IsBalance(root->_left)

&& IsBalance(root->_right);

}

private:

void RotateL(Node* parent) //左单旋,rotate->旋转

{

Node* SubR = parent->_right;

Node* SubRL = SubR->_left; //这个有可能为空

Node* ppnode = parent->_parent; //原来父亲的父亲

parent->_right = SubRL;

if(SubRL) SubRL->_parent = parent;

SubR->_left = parent;

parent->_parent = SubR;

if (ppnode == nullptr) //旋转的是整颗树

{

_root = SubR;

SubR->_parent = nullptr;

}

else //旋转的是部分

{

if (ppnode->_left == parent) //是左子树

{

ppnode->_left = SubR;

}

else //是右子树

{

ppnode->_right = SubR;

}

SubR->_parent = ppnode;

}

//最后更新平衡因子

parent->_bf = SubR->_bf = 0;

}

void RotateR(Node* parent) //右单旋细节处理和左单旋差不多

{

Node* SubL = parent->_left;

Node* SubLR = SubL->_right; //这个有可能为空

Node* ppnode = parent->_parent;

parent->_left = SubLR;

if(SubLR) SubLR->_parent = parent;

SubL->_right = parent;

parent->_parent = SubL;

if (ppnode == nullptr) //旋转的是整颗树

{

_root = SubL;

SubL->_parent = nullptr;

}

else //旋转部分

{

if (ppnode->_left == parent) //是左子树

{

ppnode->_left = SubL;

}

else //右子树

{

ppnode->_right = SubL;

}

SubL->_parent = ppnode;

}

//最后更新平衡因子

parent->_bf = SubL->_bf = 0;

}

void RotateLR(Node* parent) //左右双旋

{

Node* SubL = parent->_left;

Node* SubLR = SubL->_right;

int bf = SubLR->_bf;

RotateL(SubL);

RotateR(parent);

if (bf == 1) //插入的是右边

{

SubLR->_bf = 0;

SubL->_bf = -1;

parent->_bf = 0;

}

else if (bf == -1) //插入的是左边

{

SubLR->_bf = 0;

SubL->_bf = 0;

parent->_bf = 1;

}

else if (bf == 0) //刚好原来parent的左边就两个节点

{

SubLR->_bf = SubL->_bf = parent->_bf = 0;

}

else //原来就不是平衡树，出现问题

{

assert(false);

}

}

void RotateRL(Node* parent) //右左双旋

{

Node* SubR = parent->_right;

Node* SubRL = SubR->_left;

int bf = SubRL->_bf;

RotateR(SubR);

RotateL(parent);

if (bf == 1) //插入的是右边

{

SubRL->_bf = 0;

SubR->_bf = 0;

parent->_bf = -1;

}

else if (bf == -1) //插入的是左边

{

SubRL->_bf = 0;

parent->_bf = 0;

SubR->_bf = 1;

}

else if (bf == 0) //原来parent的右边就两个节点

{

SubRL->_bf = SubR->_bf = parent->_bf = 0;

}

else //原来就有问题

{

assert(false);

}

}

Node* _root = nullptr;

};

精彩链接