当前位置：网站首页>平衡搜索二叉树——AVL树
平衡搜索二叉树——AVL树
2022-06-11 18:14:00 【HHYX.】
AVL树特点
正常的搜索二叉树中，一般而言查找一个数的时间复杂度几乎可以等价于log2N，但是正常的搜索二叉树可能会遇到一些极端情况，例如按照1，2，3，4插入数组，此时的搜索二叉树便会变为如下的情况：
这种数据有序或者接近有序的插入数据此时的搜索二叉树会退化为一个单分支，此时查找效率就变成了O(n)，并不能体现搜索二叉树的优势。此时，有两位数学家提出了一种方法来解决这种问题：当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度。这种让搜索二叉树的高度平衡，此时他有n个节点，他的高度可以保持着log2n，因此可以达到log2n的时间复杂度，极大的提高了效率。
AVL树的实现
AVL树节点的定义
AVL树有多种控制高度的方式，这里介绍的是采用平衡因子的方式，即在每个节点保存一个平衡因子，它用来存放该节点的左右子树的高度差。后续通过判断平衡因子大小就可以判断该节点是否平衡。代码定义如下：
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)
, _bf(0)
, _kv(kv)
{
}
};
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;
cur->_parent = parent;
}
else
{
parent->_left = cur;
cur->_parent = parent;
}
return true;
}
到这里为止，和普通搜索二叉树的插入方式基本一致，只需要多处理这里的三叉链的父节点的链接即可。下面需要注意的就是如果此时的二叉树高度不平衡则需要进行高度调整。
高度调整需要先调整二叉树的平衡因子，代码如下：
调整原则为如果当前节点为父节点的左节点则进行平衡因子减一操作，如果为右节点则进行加1操作，以此向上更新，如果此时父节点的平衡因子变为0，就不需要再向上调整了，因为该部分已经平衡了。如果父节点平衡因子变为2或者-2则此时二叉树已经不平衡了，需要对其进行高度调整。
while (parent)
{
if (cur == parent->_left)
{
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 && cur->_bf == -1)
{
RotateR(parent);
}
//左单旋
else if (parent->_bf == 2 && cur->_bf == 1)
{
RotateL(parent);
}
//左右双旋
else if (parent->_bf == -2 && cur->_bf == 1)
{
RotateLR(parent);
}
else if (parent->_bf == 2 && cur->_bf == -1)
{
RotateRL(parent);
}
break;
}
else
{
//说明插入更新平衡因子之前，树中的平衡因子就有问题了
assert(false);
}
}
一般而言，搜索二叉树的高度不平衡可以分为如下四种情况：
右单旋
这种情况下左子树高度高于右子树，高度差大于1，也就是插入新节点后，当前节点的平衡因子为-1，当前节点的父节点的平衡因子为-2时的情况，此时二叉树已经出现不平衡了，需要进行右单旋进行调整，使其降低高度。
右单旋的过程是将当前节点的父节点变为当前节点的右子树节点，同时将原来的右子树变为父节点的左子树。
代码实现如下：
void RotateR(Node* parent)//右单旋
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
parent->_left = subLR;
if (subLR)
{
subLR->_parent = parent;
}
subL->_right = parent;
Node* parentParent = parent->_parent;
parent->_parent = subL;
if (parent == _root)
{
_root = subL;
_root->_parent = nullptr;
}
else
{
if (parentParent->_left == parent)
{
parentParent->_left = subL;
}
else
{
parentParent->_right = subL;
}
subL->_parent = parentParent;
}
subL->_bf = parent->_bf = 0;
}
左单旋
左单旋和右单旋的情况相反，二叉树的右子树高于左子树的情况。插入新节点后，当前的节点的平衡因子变为1，父节点的平衡因子变为2.因此需要对其进行高度平衡调节
对于这种情况使用左单旋对其进行高度调整。所谓左单旋是将当前节点的父节点变为当前节点的左节点，并且将原来的左子树与父节点的右子树链接起来。示意图与代码实现如下：
void RotateL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
parent->_right = subRL;
if (subRL)
{
subRL->_parent = parent;
}
subR->_left = parent;
Node* parentParent = parent->_parent;
parent->_parent = subR;
if (parent == _root)
{
_root = subR;
_root->_parent = nullptr;
}
else
{
if (parentParent->_left == parent)
{
parentParent->_left = subR;
}
else
{
parentParent->_right = subR;
}
subR->_parent = parentParent;
}
subR->_bf = parent->_bf = 0;
}
左右双旋
以上两种情况都是二叉树往一个方向上生长，除此以外还有一种二叉树长歪了的情况，即如下图：原本父节点平衡因子为-1，当前节点为父节点的左节点平衡因子为0时的一颗二叉树，此时如果在当前节点的右子树插入一个节点，此时当前节点的平衡因子变为1，父节点平衡因子变为-2，出现问题需要进行调整
这种情况相较于上面的情况稍微复杂一点，不能通过单一的旋转来实现，这里可以通过多次旋转来实现平衡：先对当前节点使用左单旋，然后再对当前节点的父节点使用右单旋，示意图如下：可以看到第一次左单旋之后，此时的情况以及变成了左子树单边高的情况，因此只要使用右单旋即可实现平衡，代码只需要进行复用即可，需要注意的是需要对平衡因子进行调整。(图中有误最后平衡因子情况需要进行讨论)
void RotateLR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
int bf = subLR->_bf;
RotateL(parent->_left);
RotateR(parent);
if (bf == 1)
{
parent->_bf = 0;
subL->_bf = -1;
subLR->_bf = 0;
}
else if (bf == -1)
{
parent->_bf = 1;
subL->_bf = 0;
subLR->_bf = 0;
}
else if (bf == 0)
{
parent->_bf = 0;
subL->_bf = 0;
subLR->_bf = 0;
}
else
{
assert(false);
}
}
右左双旋
最后一种情况和上一种类似，也是属于二叉树长歪了的情况。父节点的平衡因子为1，当前节点为父节点的右子树其平衡因子为0，在当前节点的左子树中插入一个节点，此时当前节点变为-1，父节点变为2，示意图如下：
为了调整高度平衡，此时也需要进行两次旋转，和上一种情况操作相反，先对当前节点进行右旋转，使其变为右倾斜的情况，在对其进行左单旋，就可以实现平衡调节，示意图代码如下：(图中有误最后平衡因子情况需要进行讨论)
void RotateRL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
int bf = subRL->_bf;
RotateR(parent->_right);
RotateL(parent);
if (bf == 1)
{
parent->_bf = -1;
subR->_bf = 0;
subRL->_bf = 0;
}
else if (bf == -1)
{
parent->_bf = 0;
subR->_bf = 1;
subRL->_bf = 0;
}
else if (bf == 0)
{
parent->_bf = 0;
subR->_bf = 0;
subRL->_bf = 0;
}
else
{
assert(false);
}
}
总结
假如以Parent为根的子树不平衡，即Parent的平衡因子为2或者-2，分以下情况考虑
- Parent的平衡因子为2，说明Parent的右子树高，设Parent的右子树的根为SubR
当SubR的平衡因子为1时，执行左单旋
当SubR的平衡因子为-1时，执行右左双旋 - Parent的平衡因子为-2，说明Parent的左子树高，设Parent的左子树的根为SubL
当SubL的平衡因子为-1是，执行右单旋
当SubL的平衡因子为1时，执行左右双旋
旋转完成后，原Parent为根的子树个高度降低，已经平衡，不需要再向上更新
整体插入代码如下：
void RotateR(Node* parent)//右单旋
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
parent->_left = subLR;
if (subLR)
{
subLR->_parent = parent;
}
subL->_right = parent;
Node* parentParent = parent->_parent;
parent->_parent = subL;
if (parent == _root)
{
_root = subL;
_root->_parent = nullptr;
}
else
{
if (parentParent->_left == parent)
{
parentParent->_left = subL;
}
else
{
parentParent->_right = subL;
}
subL->_parent = parentParent;
}
subL->_bf = parent->_bf = 0;
}
void RotateL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
parent->_right = subRL;
if (subRL)
{
subRL->_parent = parent;
}
subR->_left = parent;
Node* parentParent = parent->_parent;
parent->_parent = subR;
if (parent == _root)
{
_root = subR;
_root->_parent = nullptr;
}
else
{
if (parentParent->_left == parent)
{
parentParent->_left = subR;
}
else
{
parentParent->_right = subR;
}
subR->_parent = parentParent;
}
subR->_bf = parent->_bf = 0;
}
void RotateLR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
int bf = subLR->_bf;
RotateL(parent->_left);
RotateR(parent);
if (bf == 1)
{
parent->_bf = 0;
subL->_bf = -1;
subLR->_bf = 0;
}
else if (bf == -1)
{
parent->_bf = 1;
subL->_bf = 0;
subLR->_bf = 0;
}
else if (bf == 0)
{
parent->_bf = 0;
subL->_bf = 0;
subLR->_bf = 0;
}
else
{
assert(false);
}
}
void RotateRL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
int bf = subRL->_bf;
RotateR(parent->_right);
RotateL(parent);
if (bf == 1)
{
parent->_bf = -1;
subR->_bf = 0;
subRL->_bf = 0;
}
else if (bf == -1)
{
parent->_bf = 0;
subR->_bf = 1;
subRL->_bf = 0;
}
else if (bf == 0)
{
parent->_bf = 0;
subR->_bf = 0;
subRL->_bf = 0;
}
else
{
assert(false);
}
}
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;
cur->_parent = parent;
}
else
{
parent->_left = cur;
cur->_parent = parent;
}
//控制平衡
//1、更新平衡因子-新增节点到根节点的祖先路径
//2、出现异常的平衡因子，那么需要旋转平衡处理
//1、cur==parent->left ,parent->bf++;
//2、cur==parent->right ,parent->bf--;
//3、更新以后,parent->bf==0更新结束，说明更新前parent->bf是1或者-1，现在变为0，填上矮的那边，parent所在的子树高度不变
//4、更新以后,parent->bf==1/-1,继续往上更新,说明更新前parent->bf是0，现在变为1或者-1，有一边子树变高了，parent所在子树高度变了
//5、更新以后,parent->bf==2/-2,parent所在子树已经不平衡，需要旋转处理
//可能会一路更新，一直更新到根节点的场景
while (parent)
{
if (cur == parent->_left)
{
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 && cur->_bf == -1)
{
RotateR(parent);
}
//左单旋
else if (parent->_bf == 2 && cur->_bf == 1)
{
RotateL(parent);
}
//左右双旋
else if (parent->_bf == -2 && cur->_bf == 1)
{
RotateLR(parent);
}
else if (parent->_bf == 2 && cur->_bf == -1)
{
RotateRL(parent);
}
break;
}
else
{
//说明插入更新平衡因子之前，树中的平衡因子就有问题了
assert(false);
}
}
return true;
}
AVL树的遍历
AVL树的遍历和搜索二叉树遍历类似，使用二叉树的中序遍历即可得到一个有序的序列。
代码如下：
void InOrder()
{
return _InOrder(_root);
}
void _InOrder(Node* root)
{
if (root == nullptr)
{
return;
}
_InOrder(root->_left);
cout << root->_kv.first << ":" << root->_kv.second << endl;
_InOrder(root->_right);
}
void TestAVLTree()
{
AVLTree<int, int> root;
root.Insert(make_pair(2, 2));
root.Insert(make_pair(4, 4));
root.Insert(make_pair(5, 5));
root.Insert(make_pair(1, 1));
root.Insert(make_pair(3, 3));
root.Insert(make_pair(6, 6));
root.InOrder();
}
AVL树判断平衡
AVL树作为一棵高度平衡的二叉树，加入了平衡性的限制，因此需要对AVL树平衡性进行验证，验证一棵树是否为AVL树可以分为两步：首先中序遍历二叉树，观察其是否有序，其次可以对每个节点进行深度遍历，每个节点的左右子树高度差绝对值不能大于1。中序遍历上面的代码已经实现过，这里来实现用比较各个节点的子树高度来判断平衡的代码：
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 << "现在是:" << root->_bf << endl;
cout << root->_kv.first << "应该是:" << rightHeight - leftHeight << endl;
return false;
}
return abs(rightHeight - leftHeight) < 2 && _IsBalance(root->_left) && _IsBalance(root->_right);
}
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;
}
测试代码如下：
void TestAVLTree()
{
AVLTree<int, int> root;
root.Insert(make_pair(2, 2));
root.Insert(make_pair(4, 4));
root.Insert(make_pair(5, 5));
root.Insert(make_pair(1, 1));
root.Insert(make_pair(3, 3));
root.Insert(make_pair(6, 6));
root.InOrder();
cout << root.IsBalance() << endl;
}
边栏推荐
- LDAP 目录服务器的现代化应用
- DataNode的启动流程
- Radio button text background changes at the same time
- Class question: how to ensure that line table storage can be inserted at any time?
- 網絡安全威脅情報體系
- Function and principle of key in V-for
- 【新手上路常见问答】关于项目管理
- Spring 2021 daily question [week5 not finished]
- RadioGroup动态添加RadioButton
- SISO decoder for a general (n, n-1) SPC code (supplementary Chapter 3)
猜你喜欢
SISO Decoder for SPC (补充章节1)
SISO decoder for a general (n,n-1) SPC code（補充章節3）
Reading summary of nacos2.x source code
Use egg Js+mongodb simple implementation of curdapi
Introduction to social engineering practice
SISO Decoder for a General (n, N - 1) SPC Code (Supplementary section 3)
NFT platform development NFT mall source code NFT mall development chain game development
New work of "the father of LSTM": a new method towards self correcting neural network
Retrofit source code analysis
v-for循环遍历
随机推荐
Network Security Threat Intelligence System
SQL语句当查询条件为空时默认查询全部数据，不为空是则按照条件进行查询
HashSet集合存储学生对象并遍历
ctf入门
v-for循环遍历
Reading summary of nacos2.x source code
Sorted circular linked list
使用Visdom对损失函数进行监控
使用mysql判断日期是星期几
Summary of common mysql/redis interview questions
SISO Decoder for a General (n, N - 1) SPC Code (Supplementary section 3)
[C语言]用结构体把输入的指定分数范围内的学生输出
JS实现全屏展示的具体方法
[C语言]对一个数组的元素排序后平移元素
Use egg Js+mongodb simple implementation of curdapi
高性能架构设计
[c language] output the average score and the student data below or equal to the average score with the structure
Radiogroup dynamically add RadioButton
ACL 2022: is it no longer difficult to evaluate word polysemy? A new benchmark "dibimt"
10 ways to reset any user password