【C++】二叉搜索树+变身 = AVL树
目录
- 前言
- 一、AVL树
- 二、AVL树的实现
- 2.1 平衡因子
- 2.2 旋转处理
- 2.2.1 左单旋：插入新节点后单纯的右边高
- 2.2.2 右单旋：插入新节点后单纯的左边高
- 2.2.3 左右旋：插入新节点后不是单纯的左边高
- 2.2.4 右左旋：插入新节点后不是单纯的右边高
- 2.3 验证AVL树的平衡
- 三、完整代码
前言
本文仅适合了解二叉搜索树，但不了解AVL树底层原理的同学阅读哦。
本篇文章不会带你从头到尾实现AVL树，但会带你深入理解AVL树是怎么实现平衡的，怎么通过旋转变换实现保持平衡，以及实现平衡过程中的细节应该怎么处理等。
一、AVL树
前面的文章中我们分析过二叉搜索树的性能，得到的结果是理想情况下二叉搜索树的时间复杂度为O(LogN)，但在极端情况下（即树蜕化为单边树时），这些操作的时间复杂度会退化为O(n)，即使情况不那么极端，效率也不是特别高。
为了防止二叉搜索树出现一边偏高的情况，就需要想办法让二叉搜索树尽量保持平衡，所以两位苏联数学家（或称为俄罗斯数学家）G.M. Adelson-Velsky和E.M. Landis就发明了AVL树，其任何节点的两个子树的高度最大差别为1。
AVL树是具有一下性质的二叉搜索树：
- 其左右子树都是AVL树
- 左右子树高度差不超过1
二、AVL树的实现
本篇文章将沿用之前文章中Key-Value模型的代码，不再从底层开始实现，主要介绍在插入新节点后如何保持二叉搜索树的平衡问题。
2.1 平衡因子
如何保证AVL树的左右子树高度差不超过1？在AVL树的每个节点中存一个平衡因子，本文我们定义平衡因子 = 此节点右子树的高度 - 左子树的高度。
- 插入在左子树，平衡因子 - -
- 插入在右子树，平衡因子++
更新祖先节点的平衡因子时，我们首先需要找到祖先节点，因此每个节点中还需要增加一个指向父节点的指针。
按照我们的需求，其AVL树的节点可以定义为：
template<class K, class V>
struct AVLTreeNode
{
pair<K, V> _kv;
AVLTreeNode<K, V>* _left;
AVLTreeNode<K, V>* _right;
AVLTreeNode<K, V>* _parent;
int _bf;//平衡因子
//构造
AVLTreeNode(const pair<K, V>& kv)
:_kv(kv)
,_left(nullptr)
,_right(nullptr)
,_parent(nullptr)
,_bf(0)
{}
}；
是否继续往上更新祖先节点的平衡因子，要看parent所在子树的高度是否发生变化。
插入新节点后其父节点的平衡因子有以下几种情况：
- parent的平衡因子 == 0
parent的平衡因子更新前是 -1 / 1，新节点插入在矮的那边，高度不变，不再往上更新 - parent的平衡因子 == 1 / -1
parent的平衡因子更新前是0，parent所在子树高度都变化了，需要往上更新 - parent的平衡因子 == 2 / -2
parent的平衡因子更新前是 -1 / 1，插入新节点后树不再平衡，需要旋转处理
pcur = new Node(kv);
if (parent->_kv.first > kv.first)//判断新节点应该插入左还是右
{
parent->_left = pcur;
}
else
{
parent->_right = pcur;
}
pcur->_parent = parent;//与父节点链接关系
while (parent)//有可能更新到根节点去
{
parent->_bf = parent->_left == pcur ? parent->_bf - 1
: parent->_bf + 1;
if (parent->_bf == 0)//插入前后高度不变
{
break;
}
else if (parent->_bf == 1 || parent->_bf == -1)
{
//高度变了，继续往上更新
pcur = parent;
parent = parent->_parent;
}
else if (parent->_bf == 2 || parent->_bf == -2)
{
//插入节点后二叉树不平衡了，需要旋转处理
}
else
{
assert(false);//检测AVL树是否异常
}
}
2.2 旋转处理
当二叉搜索树出现不平衡的情况时，需要旋转处理，对应插入后二叉搜索树的各种情况，主要有四种旋转的方式来保持平衡。
其中：
- h代表子树的高度，可以是0、1、2…
- 我们用能代表所有情况的四种类型的抽象图来研究旋转方式，单纯研究某几种情况没有意义
原则：
- 保持搜索树的性质
- 降低高度，控制平衡
2.2.1 左单旋：插入新节点后单纯的右边高
旋转处理过程中，我们主要关注三个节点（以上图为例）：10（标记为
parent）、30（标记为subR）、b（标记为subLR）。
在旋转过程中，有以下几种情况需要考虑：
subR的左孩子可能存在，也可能不存在parent可能是根节点，也可能是子树。如果是根节点，旋转完成后，要更新根节点；如果是子树，可能是某个节点的左子树，也可能是右子树
//左单旋
void RotateL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;//subRL是有可能为空的
parent->_right = subRL;
subR->_left = parent;
Node* parentparent = parent->_parent;
parent->_parent = subR;
if (parentparent == nullptr)//subR有可能变成根
{
_root = subR;
}
else
{
if (parentparent->_left == parent)
{
parentparent->_left = subR;
}
else
{
parentparent->_right = subR;
}
}
subR->_parent = parentparent;
if (subRL)
{
subRL->_parent = parent;
}
parent->_bf = subR->_bf = 0;//更新平衡因子
}
旋转处理过程中主要是处理各节点的父节点指针的指向和平衡因子的更新。
2.2.2 右单旋：插入新节点后单纯的左边高
其处理方式和左单旋相似，可参考左单旋。
//右单旋
void RotateR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
parent->_left = subLR;
subL->_right = parent;
Node* parentparent = parent->_parent;
parent->_parent = subL;
if (parentparent == nullptr)
{
_root = subL;
}
else
{
if (parentparent->_left == parent)
{
parentparent->_left = subL;
}
else
{
parentparent->_right = subL;
}
}
subL->_parent = parentparent;
if (subLR)
{
subLR->_parent = parent;
}
subL->_bf = parent->_bf = 0;
}
2.2.3 左右旋：插入新节点后不是单纯的左边高
这种情况只用左旋或右旋只会原地打转，不能降低平衡。
我们需要先对subL进行左单旋，再对parent进行右单旋，最后更新平衡因子。
- 双旋后平衡因子的更新要根据插入新节点后
subLR的平衡因子来分情况讨论- 双旋最终结果是把
subLR推到最上面，让其平衡因子为0
//左右旋
void RotateLR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
int bf = subLR->_bf;
RotateL(parent->_left);
RotateR(parent);
if (bf == 0)
{
parent->_bf = 0;
subL->_bf = 0;
subLR->_bf = 0;
}
else 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
{
assert(false);
}
}
2.2.4 右左旋：插入新节点后不是单纯的右边高
可参考左右旋。
//右左旋
void RotateRL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
int bf = subRL->_bf;
RotateR(parent->_right);
RotateL(parent);
if (bf == 0)
{
parent->_bf = 0;
subR->_bf = 0;
subRL->_bf = 0;
}
else if (bf == -1)
{
parent->_bf = 0;
subR->_bf = 1;
subRL->_bf = 0;
}
else if (bf == 1)
{
parent->_bf = -1;
subR->_bf = 0;
subRL->_bf = 0;
}
else
{
assert(false);
}
}
旋转完成后，原parent为根的子树个高度降低，已经平衡，不需要再向上更新。
2.3 验证AVL树的平衡
我们可以分别计算出其左子树和右子树的高度，将其相减的值与节点中记录的平衡因子的值比较，看是否符合我们的预期。
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 _isBalanceTree(Node* root)
{
if (root == nullptr)
{
return true;
}
int leftheight = _Height(root->_left);
int rightheight = _Height(root->_right);
int bf = rightheight - leftheight;
if (abs(bf) > 1)
{
cout << root->_kv.first << "高度差异常" << endl;
return false;
}
if (root->_bf != bf)
{
cout << root->_kv.first << "平衡因子异常" << endl;
return false;
}
return _isBalanceTree(root->_left) && _isBalanceTree(root->_right);
}
三、完整代码
template<class K, class V>
struct AVLTreeNode
{
pair<K, V> _kv;
AVLTreeNode<K, V>* _left;
AVLTreeNode<K, V>* _right;
AVLTreeNode<K, V>* _parent;
int _bf;//平衡因子
AVLTreeNode(const pair<K, V>& kv)
:_kv(kv)
,_left(nullptr)
,_right(nullptr)
,_parent(nullptr)
,_bf(0)
{}
};
template<class K, class V>
class AVLTree
{
typedef AVLTreeNode<K, V> Node;
public:
AVLTree() = default;
AVLTree(const AVLTree<K, V>& t)
{
_root = copy(t._root);
}
AVLTree<K, V>& operator=(AVLTree<K, V> t)
{
swap(_root, t._root);
return *this;
}
~AVLTree()
{
Destroy(_root);
_root = nullptr;
}
bool Find(const K& key)
{
Node* pcur = _root;
while (pcur)
{
if (key < pcur->_kv.first)
{
pcur = pcur->_left;
}
else if (key > pcur->_kv.first)
{
pcur = pcur->_right;
}
else
{
return true;
}
}
return false;
}
bool Insert(const pair<K, V>& kv)
{
//没有节点时需要单独处理
if (_root == nullptr)
{
_root = new Node(kv);
return true;
}
Node* pcur = _root;
Node* parent = nullptr;
while (pcur)
{
if (kv.first < pcur->_kv.first)
{
parent = pcur;
pcur = pcur->_left;
}
else if (kv.first > pcur->_kv.first)
{
parent = pcur;
pcur = pcur->_right;
}
else
{
return false;
}
}
pcur = new Node(kv);
if (parent->_kv.first > kv.first)//判断新节点应该插入左还是右
{
parent->_left = pcur;
}
else
{
parent->_right = pcur;
}
pcur->_parent = parent;//与父节点链接关系
//更新平衡因子
while (parent)//有可能更新到根节点去
{
parent->_bf = parent->_left == pcur ? parent->_bf - 1 : parent->_bf + 1;
if (parent->_bf == 0)//插入前后高度不变
{
break;
}
else if (parent->_bf == 1 || parent->_bf == -1)
{
//高度变了，继续往上更新
pcur = parent;
parent = parent->_parent;
}
else if (parent->_bf == 2 || parent->_bf == -2)
{
//插入节点后二叉树不平衡了，需要旋转处理
if (parent->_bf == 2 && pcur->_bf == 1)
{
RotateL(parent);
}
else if (parent->_bf == -2 && pcur->_bf == -1)
{
RotateR(parent);
}
else if (parent->_bf == 2 && pcur->_bf == -1)
{
RotateRL(parent);
}
else if (parent->_bf == -2 && pcur->_bf == 1)
{
RotateLR(parent);
}
break;//不管是哪种情况，旋转完后子树的高度没有变化，所以不再调整
}
else
{
assert(false);//检测AVL树是否异常
}
}
return true;
}
void InOrder()
{
_InOrder(_root);
cout << endl;
}
bool IsBalanceTree()
{
return _isBalanceTree(_root);
}
private:
//左单旋
void RotateL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;//subRL是有可能为空的
parent->_right = subRL;
subR->_left = parent;
Node* parentparent = parent->_parent;
parent->_parent = subR;
if (parentparent == nullptr)//subR有可能变成根
{
_root = subR;
}
else
{
if (parentparent->_left == parent)
{
parentparent->_left = subR;
}
else
{
parentparent->_right = subR;
}
}
subR->_parent = parentparent;
if (subRL)
{
subRL->_parent = parent;
}
parent->_bf = subR->_bf = 0;//更新平衡因子
}
//右单旋
void RotateR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
parent->_left = subLR;
subL->_right = parent;
Node* parentparent = parent->_parent;
parent->_parent = subL;
if (parentparent == nullptr)
{
_root = subL;
}
else
{
if (parentparent->_left == parent)
{
parentparent->_left = subL;
}
else
{
parentparent->_right = subL;
}
}
subL->_parent = parentparent;
if (subLR)
{
subLR->_parent = parent;
}
subL->_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 == 0)
{
parent->_bf = 0;
subL->_bf = 0;
subLR->_bf = 0;
}
else 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
{
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 == 0)
{
parent->_bf = 0;
subR->_bf = 0;
subRL->_bf = 0;
}
else if (bf == -1)
{
parent->_bf = 0;
subR->_bf = 1;
subRL->_bf = 0;
}
else if (bf == 1)
{
parent->_bf = -1;
subR->_bf = 0;
subRL->_bf = 0;
}
else
{
assert(false);
}
}
Node* copy(Node* root)
{
if (root == nullptr)
{
return nullptr;
}
Node* copynode = new Node(root->_kv);
copynode->_left = copy(root->_left);
copynode->_right = copy(root->_right);
return copynode;
}
void Destroy(Node* root)
{
if (root == nullptr)
return;
Destroy(root->_left);
Destroy(root->_right);
delete root;
}
void _InOrder(Node* root)
{
if (root == nullptr)//递归一定要有结束条件
{
return;
}
_InOrder(root->_left);
cout << root->_kv.first << ":" << root->_kv.second << endl;
_InOrder(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;
}
bool _isBalanceTree(Node* root)
{
if (root == nullptr)
{
return true;
}
int leftheight = _Height(root->_left);
int rightheight = _Height(root->_right);
int bf = rightheight - leftheight;
if (abs(bf) > 1)
{
cout << root->_kv.first << "高度差异常" << endl;
return false;
}
if (root->_bf != bf)
{
cout << root->_kv.first << "平衡因子异常" << endl;
return false;
}
return _isBalanceTree(root->_left) && _isBalanceTree(root->_right);
}
private:
Node* _root = nullptr;
};
本篇文章的分享就到这里了，如果您觉得在本文有所收获，还请留下您的三连支持哦~
