【数据结构】AVL树
一：什么是AVL树？
二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树，查找元素相当于在顺序表中搜索元素，效率低下。因此，两位俄罗斯的数学家G.M. A delson- V elskii和E.M. L andis在1962年 发明了一种解决上述问题的方法：当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之 差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度。
AVL树 = 二叉搜索树 + （ 所有的结点（左子树高度-右子树高度）的绝对值<=1 ）
1.1什么是平衡因子
- 左子树高度 - 右子树高度 = 平衡因子
- AVL树中平衡因子只能取（-1,0,1），如果平衡因子为2，或者-2，则需要旋转调整树，使平衡因子回归（-1,0,1）。
AVL树高度保持在 O( log 2 N \log_2N log2N) ，搜索时间复杂度 O( log 2 N \log_2N log2N) 。
二：AVL树的数据结构
在调整失衡的AVL树时，我们需要频繁的访问父节点，所以在AVL树中我们需要使用三叉链，因此AVL树的节点除了包含左右子节点的指针，还需要一个指向父节点的指针
- AVL树的结点
template<class K,class V>
struct AVLTreeNode
{
AVLTreeNode(const pair<K,V>& kv):_kv(kv),
_left(nullptr),_right(nullptr),_bf(0),_parent(nullptr){}
AVLTreeNode<K, V>* _left; //左孩子
AVLTreeNode<K, V>* _right;//右孩子
AVLTreeNode<K, V>* _parent;//父亲
int _bf;// 平衡因子
pair<K, V> _kv;//KV模型值
};
- AVL树
template<class K, class V>
class AVLTree
{
typedef AVLTreeNode<K, V> Node;
public:
//方法
private:
Node* _root = nullptr;//根
};
三：AVL的旋转
在发生失衡时，AVL通过旋转来进行调整。
3.1 简单左旋
- 如下图，我们发现结点4平衡因子是-2，失衡了。
- 我们将失衡结点左旋 （即 失衡结点以右儿子为中心向左旋转），此时发现树平衡了。
- 并且失衡结点与它的右儿子的平衡因子变为0
- 对两个树中序遍历得到相同的结果，也就是说在二叉搜索树的意义上（右儿子大于根，左儿子小于根），两棵树等价，但是树高降低了，更加均衡。
3.2 复杂左旋
- 如下图，我们发现结点5平衡因子是-2，失衡了。
- 但此时9的左孩子在，结点5左旋会与结点6冲突，我们会将结点6变成结点5的右孩子。
（简单记为“冲突的左孩子变成右孩子”） - 并且失衡结点与它的右儿子的平衡因子变为0。
- 对两个树中序遍历得到相同的结果，也就是说在二叉搜索树的意义上（右儿子大于根，左儿子小于根），两棵树等价，但是树高降低了，更加均衡。
3.3 简单右旋
- 如下图，我们发现结点10平衡因子是-2，失衡了。
- 我们将失衡结点右旋 （即 失衡结点向右旋转），此时发现树平衡了
- 并且失衡结点与它的右儿子的平衡因子变为0
- 对两个树中序遍历得到相同的结果，也就是说在二叉搜索树的意义上（右儿子大于根，左儿子小于根），两棵树等价，但是树高降低了，更加均衡。
3.4 复杂右旋
- 如下图，我们发现结点14平衡因子是-2，失衡了。
- 但此时6的右孩子在，结点14右旋会与结点9冲突，我们会将结点9变成结点14的左孩子。
（简单记为“冲突的右孩子变成左孩子”） - 并且失衡结点与它的右儿子的平衡因子变为0
- 对两个树中序遍历得到相同的结果，也就是说在二叉搜索树的意义上（右儿子大于根，左儿子小于根），两棵树等价，但是树高降低了，更加均衡。
总结
- 左旋：向左旋转，冲突的左孩变右孩
- 右旋：向右旋转，冲突的右孩变左孩子
四：插入导致旋转的四种情况
第一种 LL型
-
因为结点3的插入，是在结点14的左孩子的左子树上，所以这种失衡状态，也被称作LL型。
LL型的特征：- 失衡结点的平衡因子 = 2
- 失衡结点左孩子的平衡因子 = 1
-
LL型通过右旋即可解决
-
解决时的特征：
- 失衡结点的平衡因子 = 0
- 失衡结点左孩子的平衡因子 = 0
第二种 RR型
- 因为结点17的插入，是在结点5的右孩子的右子树上，所以这种失衡状态，也被称作RR型。
RR型的特征：- 失衡结点的平衡因子 = -2
- 失衡结点右孩子的平衡因子 = -1
- RR型通过左旋即可解决
- 解决时的特征：
- 失衡结点的平衡因子 = 0
- 失衡结点右孩子的平衡因子 = 0
第三种 LR型
- 因为结点6的插入，是在结点9的左孩子的右子树上，所以这种失衡状态，也被称作LR型。
LR型的特征：- 失衡结点的平衡因子 = 2
- 失衡结点左孩子的平衡因子 = -1
- LR型通过先左旋左孩子，然后再失衡结点右旋解决
- 左旋左孩子
- 右旋失衡结点
- 左旋左孩子
解决时的特征有三种：
第一种 LR的平衡因子 = 0时
如图所示为LR型
左旋左儿子，右旋失衡结点解决失衡问题，得到结果:
- 失衡结点 平衡因子 = 0；
- 左儿子L 平衡因子 = 0；
- 插入结点LR 平衡因子 = 0；
第二种 LR的平衡因子 = 1时
如图所示为LR型
左旋左儿子，右旋失衡结点解决失衡问题，得到结果:
- 失衡结点 平衡因子 = -1；
- 左儿子L 平衡因子 = 0；
- LR 平衡因子 = 0；
第三种 LR的平衡因子 = -1时
如图所示为LR型
左旋左儿子，右旋失衡结点解决失衡问题，得到结果:
- 失衡结点 平衡因子 = 0；
- 左儿子L 平衡因子 = 1；
- LR 平衡因子 = 0；
第四种 RL型
- 因为结点8的插入，是在结点5的右孩子的左子树上，所以这种失衡状态，也被称作RL型。
RL型的特征：- 失衡结点的平衡因子 = -2
- 失衡结点左孩子的平衡因子 = 1
- RL型通过先右旋右孩子，然后再失衡结点左旋解决
- 右旋右孩子
- 左旋失衡结点
- 右旋右孩子
解决时的特征有三种：
第一种 RL的平衡因子 = 0时
右旋右儿子，左旋失衡结点解决失衡问题，得到结果:
- 失衡结点 平衡因子 = 0；
- 右儿子R 平衡因子 = 0；
- RL 平衡因子 = 0；
第二种 RL的平衡因子 = 1时
右旋右儿子，左旋失衡结点解决失衡问题，得到结果:
- 失衡结点 平衡因子 = 0；
- 右儿子R 平衡因子 = -1；
- RL 平衡因子 = 0；
第三种 RL的平衡因子 = -1时
右旋右儿子，左旋失衡结点解决失衡问题，得到结果:
- 失衡结点 平衡因子 = 1；
- 右儿子R 平衡因子 = 0；
- RL 平衡因子 = 0；
通常用平衡因子来判断失衡状态
如果碰到多个祖先结点同时失衡的情况时
- 如图所示：
- 我们只需要调整距离9最近的失衡结点就可以了。
原因是因为我们只是将导致3失衡的右子树还原成原来的高度就好了。 - 因此其实结点3的平衡因子就从未改变，我们也无需将结点3的平衡因子更新成-2，再调整回来。
四：删除导致旋转
也是通过平衡因子判断失衡状态，旋转调整树，但与插入操作不同的是：
- 插入操作如果碰到多个祖先结点同时失衡的情况时，只需要调整距离9最近的失衡结点就可以了。
- 删除操作删除结点后需要依次对每个祖先检查并且调整。
五：AVL树旋转的代码实现
RR型时旋转处理
- 左旋
- 更新平衡因子
//左旋
void RotateL(Node* parent)
{
//获得失衡结点的右儿子和右儿子的左儿子
Node* subR = parent->_right;
Node* subRL = subR->_left;
//冲突的左孩子变成右孩子
parent->_right = subRL;
//如果右孩子存在，需要调整右孩子的父亲
if (subRL)
{
subRL->_parent = parent;
}
//向左旋转，失衡结点变成右儿子的左儿子
subR->_left = parent;
//更新失衡结点的父亲，记录原来的父亲
Node* ppNode = parent->_parent;
parent->_parent = subR;
//如果根是失衡结点，则根更改为失衡结点原来的右孩子，并且右孩子的父亲应该更新为空
if (_root == parent)
{
_root = subR;
subR->_parent = nullptr;
}
//如果不是根，则失衡结点的父亲应该指向失衡结点原来的右儿子，并且更新右儿子的父亲
else
{
if (ppNode->_left == parent)
{
ppNode->_left = subR;
}
else
ppNode->_right = subR;
subR->_parent = ppNode;
}
//旋转完后，失衡结点和失衡结点的右孩子的平衡因子将会变为0
parent->_bf = subR->_bf = 0;
}
LL型时旋转处理
- 右旋
- 更新平衡因子
//右旋
void RotateR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
parent->_left = subLR;
if (subLR)
{
subLR->_parent = parent;
}
subL->_right = parent;
Node* ppNode = parent->_parent;
parent->_parent = subL;
if (_root == parent)
{
_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;
}
RL型时旋转处理
- 先右旋右儿子
- 再左旋失衡结点
- 更新平衡因子
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)
{
subR->_bf = 0;
parent->_bf = 0;
subRL->_bf = 0;
}
}
LR型时旋转处理
- 先左旋左儿子
- 再右旋失衡结点
- 更新平衡因子
void RotateLR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
int bf = subLR->_bf;
RotateL(subL);
RotateR(parent);
if (bf == 1)
{
parent->_bf = -1;
subL->_bf = 0;
subLR->_bf = 0;
}
else if (bf == -1)
{
parent->_bf = 0;
subL->_bf = 1;
subLR->_bf = 0;
}
else if (bf == 0)
{
subL->_bf = 0;
parent->_bf = 0;
subLR->_bf = 0;
}
}
整体代码实现
#pragma once
#include <iostream>
using namespace std;
#include<utility>
template<class K,class V>
struct AVLTreeNode
{
AVLTreeNode(const pair<K,V>& kv):_kv(kv),_left(nullptr),_right(nullptr),_bf(0),_parent(nullptr){}
AVLTreeNode<K, V>* _left; //左孩子
AVLTreeNode<K, V>* _right;//右孩子
AVLTreeNode<K, V>* _parent;//父亲
int _bf;// 平衡因子
pair<K, V> _kv;//KV模型值
};
template<class K,class V>
class AVLTree
{
typedef AVLTreeNode<K,V> Node;
public:
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;
}
//更新父亲和祖先的平衡因子
while (parent)
{
//如果插入的是父亲的右孩子，那么父亲的平衡因子应该-1，如果是左孩子，则父亲的平衡因子+1
if (cur == parent->_right)
{
parent->_bf--;
}
else
{
parent->_bf++;
}
//如果父亲的平衡因子 = 0
//说明父亲所在的子树高度不变，因为只是把空的一边补上了一个结点
if(parent->_bf == 0)
{
break;
}
//如果父亲的平衡因子 == -1 或者 1 说明父亲所在的子树的高度变了，继续往上更新
else if (parent->_bf == -1 || parent->_bf == 1)
{
cur = parent;
parent = parent->_parent;
}
//如果出现平衡因子变成2，-2的情况，则需要进行平衡处理
else if (parent->_bf == 2 || parent->_bf == -2)
{
if (parent->_bf == 2)
{
//LL型
if (cur->_bf == 1)
{
RotateR(parent);
}
//LR型
else if (cur->_bf == -1)
{
RotateLR(parent);
}
}
else if (parent->_bf == -2)
{
//RR型
if (cur->_bf == -1)
{
RotateL(parent);
}
//RL型
else if (cur->_bf == 1)
{
RotateRL(parent);
}
}
break;
}
}
}
//左旋
void RotateL(Node* parent)
{
//获得失衡结点的右儿子和右儿子的左儿子
Node* subR = parent->_right;
Node* subRL = subR->_left;
//冲突的左孩子变成右孩子
parent->_right = subRL;
//如果右孩子存在，需要调整右孩子的父亲
if (subRL)
{
subRL->_parent = parent;
}
//向左旋转，失衡结点变成右儿子的左儿子
subR->_left = parent;
//更新失衡结点的父亲，记录原来的父亲
Node* ppNode = parent->_parent;
parent->_parent = subR;
//如果根是失衡结点，则根更改为失衡结点原来的右孩子，并且右孩子的父亲应该更新为空
if (_root == parent)
{
_root = subR;
subR->_parent = nullptr;
}
//如果不是根，则失衡结点的父亲应该指向失衡结点原来的右儿子，并且更新右儿子的父亲
else
{
if (ppNode->_left == parent)
{
ppNode->_left = subR;
}
else
ppNode->_right = subR;
subR->_parent = ppNode;
}
//旋转完后，失衡结点和失衡结点的右孩子的平衡因子将会变为0
parent->_bf = subR->_bf = 0;
}
void RotateR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
parent->_left = subLR;
if (subLR)
{
subLR->_parent = parent;
}
subL->_right = parent;
Node* ppNode = parent->_parent;
parent->_parent = subL;
if (_root == parent)
{
_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 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)
{
subR->_bf = 0;
parent->_bf = 0;
subRL->_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)
{
parent->_bf = -1;
subL->_bf = 0;
subLR->_bf = 0;
}
else if (bf == -1)
{
parent->_bf = 0;
subL->_bf = 1;
subLR->_bf = 0;
}
else if (bf == 0)
{
subL->_bf = 0;
parent->_bf = 0;
subLR->_bf = 0;
}
}
int get_height(Node* root)
{
if (root == nullptr)
return 0;
int leftHeight = get_height(root->_left);
int rightHeight = get_height(root->_right);
return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}
bool is_banlance() {
return _is_banlance(_root);
}
bool _is_banlance(Node* root)
{
if (root == nullptr)
return true;
int leftHeight = get_height(root->_left);
int rightHeight = get_height(root->_right);
return abs(leftHeight - rightHeight) < 2
&& _is_banlance(root->_left)
&& _is_banlance(root->_right);
}
void inOrder()
{
_inOrder(_root);
}
void _inOrder(Node* root)
{
if (root == nullptr)
return;
_inOrder(root->_left);
cout << root->_kv.first << " " << root->_kv.second << endl;
_inOrder(root->_right);
}
private:
Node* _root = nullptr;
};
void test()
{
int a[] = { 16,3,7,11,9,26,18,14,15,2,5,1,4,8,12,15,13};
AVLTree<int, int> t;
for (auto e : a)
{
t.insert(make_pair(e,e));
}
t.inOrder();
cout << t.is_banlance() << endl;
}
原文地址：https://blog.csdn.net/qq_72680384/article/details/145231074
免责声明：本站文章内容转载自网络资源，如侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！