数据结构进阶——AVL树
学习本章，需要大家先掌握搜索二叉树，了解键值对pair。int _bf;// balance factor 平衡因子, _kv(kv), _bf(0){}该节点的定义是一个三叉链，_left和_right分别指向左右子树，_parent指向父节点；节点中存储的有效数据为pair，类型的键值对；_bf为平衡因子，在此我们定义为右树高度减去左树高度，用来控制左右子树的高度（注意：平衡因子只是其中一种控
·
数据结构进阶——AVL树
0. 前言
学习本章，需要大家先掌握搜索二叉树，了解键值对pair。
1. AVL树的概念
1. 搜索二叉树的弊端：
- 搜索二叉树虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树，查找元素相当于在顺序表中搜索元素，效率低下。因此，两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了一种解决上述问题的方法：当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，就可以降低树的高度，从而减少平均搜索长度。
2. AVL树的性质：
- 左右子树都是AVL树；
- 左右子树高度之差（简称平衡因子）的绝对值不超过1；
- 空树是AVL树。
如果一棵二叉搜索树是高度平衡的，它就是AVL树。如果它有n个结点，其高度可保持在 O ( l o g 2 n ) O(log_2 n) O(log2n)，搜索时间复杂度 O ( l o g 2 n ) O(log_2 n) O(log2n)。
2. AVL树节点，和树的定义
1. 节点：
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)
{}
};
- 该节点的定义是一个三叉链，
_left和_right分别指向左右子树，_parent指向父节点； - 节点中存储的有效数据为
pair<K, V>，类型的键值对； _bf为平衡因子，在此我们定义为右树高度减去左树高度，用来控制左右子树的高度（注意：平衡因子只是其中一种控制平衡的手段，并不是唯一的）；- 定义了一个模版构造函数，以便后续使用。
2. 树：
template<class K, class V>
class AVLTree
{
typedef AVLTreeNode<K, V> Node;
public:
...
private:
Node* _root = nullptr;
size_t _size = 0;
};
_size记录树中一共有多少数据（多少节点）。
3. AVL树的插入
1. 思路：
- AVL树就是在搜索二叉树的基础上引入了平衡因子，因此AVL树也可以看成是搜索二叉树。那么AVL树的插入过程可以分为两步：
- 按照二叉搜索树的方式插入新节点；
- 调整节点的平衡因子。
- 调整平衡因子的过程，又可以细分为两部分：
- 平衡因子的更新；
- 节点的调整（旋转）+ 平衡因子的更新。
1. 模拟插入过程（红色节点表示新插入节点）：
- 插入新节点后，第一件事，是更新该新节点的父亲的平衡因子：
- 新增节点在左，父亲
bf--； - 新增节点在右，父亲
bf++。
- 新增节点在左，父亲
- 更新完该新节点的父亲后，还要判断是否需要往上更新（新增节点可能会影响祖先，但是一定不会影响兄弟）：
- 更新后，父亲
bf == 0，父亲所在的子树高度不变，不用再继续往上更新了，插入结束。 （ps：在插入节点前，父亲bf == 1 or -1，子树一边高，一边低，新插入节点填补低的那边） - 更新后，父亲
bf == 1 or -1，父亲所在的子树高度变了，需要继续往上更新。（ps：在插入节点前，父亲bf == 0，两边一样高，插入新节点导致高度变化） - 更新后，父亲
bf == 2 or -2，父亲所在的子树不平衡，需要旋转调整。
- 更新后，父亲
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);
_size++;
return true;
}
// 通过parent向上找父节点
Node* parent = nullptr;
Node* cur = _root;
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;
cur->_parent = parent;
}
else
{
parent->_left = cur;
cur->_parent = parent;
}
_size++;
// 调整，AVL树的核心部分
while (parent)
{
// 平衡因子的更新
if (cur == parent->_left)
{
// 插入在左节点，_bf--
parent->_bf--;
}
else
{
// 插入在右节点，_bf++
parent->_bf++;
}
// 判断是否要继续向上更新，和是否旋转调整
if (parent->_bf == 0)
{
// 更新后 _bf == 0，说明子树高度不变，不需要往上更新
break;
}
else if (parent->_bf == 1 || parent->_bf == -1)
{
// 更新后子树高度改变，需要往上更新
cur = parent;
parent = parent->_parent;
}
else if (parent->_bf == 2 || parent->_bf == -2)
{
// 旋转调整
...
}
else
{
// 平衡因子绝对值大于2，直接报错
assert(false);
}
}
return true;
}
...
private:
Node* _root = nullptr;
size_t _size = 0;
};
4. AVL树的旋转
- 如果在一棵原本是平衡的AVL树中插入一个新节点，可能造成不平衡，此时必须调整树的结构，使之平衡化。根据节点插入位置的不同，AVL树的旋转分为四种：
1. 新节点插入较高左子树的左侧—右右：左单旋
-
先考虑一种最简单的场景（场景1）：
- 直接将8节点链接到9节点的左边即可。
- 直接将8节点链接到9节点的左边即可。
-
再看一种更复杂的场景（场景2）：
- 需要将13节点链接到9节点的右子树，将9节点链接到15节点的左子树。
- 需要将13节点链接到9节点的右子树，将9节点链接到15节点的左子树。
-
还有更加复杂的情况，但是我们可以对所有的情况进行一个归类，画出抽象图：
- a，b，c 都是高度为h的AVL平衡树；
- 只需要将b框中的节点（subRL），链接到30节点（parent）的右子树（将60节点的左子树链接到30节点的右边）；再将30节点（parent），连接到60节点（subR）的左子树即可。（别忘了是三叉链，要同步更新父节点）
- 旋转完后别忘了更新平衡因子，左单旋后，
parent和subR节点的_bf都为0，其余节点的平衡因子均不会受到印象。 h = 0时，就对应场景1的情况；h = 1时，就对应场景2的情况。
- 代码实现：
- 注意，在更新
subRL节点的父节点时，需要先判断subRL是否为空（h=0的情况），如果为空，就不要访问subRL了； - 还需要记录
parent的父节点，方便旋转后将subR链接给parent->_parent，和整棵树链接起来； - 当
parent就是根节点时，需要特殊处理，要更新根节点为subR。
- 注意，在更新
template<class K, class V>
class AVLTree
{
typedef AVLTreeNode<K, V> Node;
public:
// 左单旋
void RotateL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
// 更新左右节点
parent->_right = subRL;
subR->_left = parent;
// 提前记录parent的parent
Node* parentParent = parent->_parent;
// 更新_parent
parent->_parent = subR;
if (subRL) // 判断为不为空，subRL是唯一一个可能为空的节点
{
subRL->_parent = parent;
}
// 处理根，将旋转后的子树和整个树链接
if (_root == parent)
{
// 如果parent原来是root根节点，就让subR成为新的根节点
_root = subR;
subR->_parent = nullptr;
}
else if (parentParent->_left == parent)
{
// parent原来在左子树，就和左子树链接
parentParent->_left = subR;
subR->_parent = parentParent;
}
else
{
// parent原来在右子树，就和右子树链接
parentParent->_right = subR;
subR->_parent = parentParent;
}
// 更新平衡因子
parent->_bf = subR->_bf = 0;
}
...
private:
Node* _root = nullptr;
size_t _size = 0;
};
2. 新节点插入较高左子树的左侧—左左：右单旋
- 这里不带着大家一步一步分析了，直接上抽象图：
- a，b，c 均为高度为h的AVL平衡树；
- 只需要将
subLR给parent的左，再将parent给subL的右即可； - 随后更新平衡因子，
subL和parent的_bf都更新为0。
- 类比左单旋，直接上代码：
template<class K, class V>
class AVLTree
{
typedef AVLTreeNode<K, V> Node;
public:
// 右单旋
void RotateR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
// 更新左右节点
subL->_right = parent;
parent->_left = subLR;
Node* parentParent = parent->_parent;
// 更新_parent
parent->_parent = subL;
if (subLR)
{
subLR->_parent = parent;
}
if (_root == parent)
{
_root = subL;
subL->_parent = nullptr;
}
else if (parentParent->_left == parent)
{
parentParent->_left = subL;
subL->_parent = parentParent;
}
else
{
parentParent->_right = subL;
subL->_parent = parentParent;
}
parent->_bf = subL->_bf = 0;
}
...
private:
Node* _root = nullptr;
size_t _size = 0;
};
3. 新节点插入较高左子树的右侧—左右：先左单旋再右单旋（左右双旋）
-
注意：该抽象图只是左右双旋中的一种情况，为在60的左子树新增。还有两种情况没有画出来，分别是（1）60作为新增节点的情况；（2）在60的右子树新增的情况。不同的情况，旋转后得到的平衡因子有差别。
-
h = 0的情况：60就是新插入节点。此时b，c子树不存在，注意是不存在，连空都不是。旋转后的parent，subL，subLR的平衡因子均为0。
-
h = 1的情况（该情况又分两种）：-
在60的左子树新增：注意此时旋转后，
subL和subLR的平衡因子均为0，只有parent的平衡因子为1，和h = 0的情况不一样。
-
在60的右子树新增：这种情况最后的到的子树，和上图只有一处区别，就是
b变成了NULL，c变成了50，故此时旋转后，subL的平衡因子为-1，parent，subLR的平衡因子均为0。和在60左子树新增的情况，平衡因子又不一样。
-
-
代码实现：
- 我们可以根据新节点插入后，
subLR的平衡因子来确定到底是上述哪种情况。（1）subLR->_bf == 0，说明subLR就是新增节点；（2）subLR->_bf == -1，说明是在subLR的左子树新增；（3）subLR->_bf == 1，说明是在subLR的右子树新增。
- 我们可以根据新节点插入后，
template<class K, class V>
class AVLTree
{
typedef AVLTreeNode<K, V> Node;
public:
// 左右双旋
void RotateLR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
int bf = subLR->_bf; // 提前记录subLR的平衡因子，避免单旋操作后，值丢失
// 先左旋再右旋
RotateL(parent->_left);
RotateR(parent);
// 更新平衡因子
if (bf == 0)
{
// subLR自己就是新增节点
subL->_bf = subLR->_bf = parent->_bf = 0;
}
else if (bf == -1)
{
// subLR的左子树新增
parent->_bf = 1;
subL->_bf = subLR->_bf = 0;
}
else if (bf == 1)
{
// subLR的右子树新增
parent->_bf = subLR->_bf = 0;
subL->_bf = -1;
}
else
{
assert(false); // 检查点
}
}
...
private:
Node* _root = nullptr;
size_t _size = 0;
};
4. 新节点插入较高右子树的左侧—右左：先右单旋再左单旋（右左双旋）
- 注意：该抽象图只是右左双旋中的一种情况，为在60的右子树新增。还有两种情况没有表示出来，分别是（1）60就是新增节点；（2）在60的左子树新增。
- 类比左右双旋，上代码：
- 还是要注意，可以通过
subRL的平衡因子区分上述三种情况。（1）subRL->_bf == 0，说明subRL就是新增节点；（2）subRL->_bf == 1，说明是在subRL的右子树新增，parent->_bf == -1；（3）subRL->_bf == -1，说明是在subRL的左子树新增，subR->_bf == 1。
- 还是要注意，可以通过
template<class K, class V>
class AVLTree
{
typedef AVLTreeNode<K, V> Node;
public:
// 右左双旋
void RotateRL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
int bf = subRL->_bf; // 提前记录subRL的平衡因子，避免单旋操作后，值丢失
// 先右旋再左旋
RotateR(parent->_right);
RotateL(parent);
// 更新平衡因子
if (bf == 0)
{
// subRL自己就是新增节点
parent->_bf = subR->_bf = subRL->_bf = 0;
}
else if (bf == -1)
{
// subRL的左子树新增
parent->_bf = 0;
subR->_bf = 1;
subRL->_bf = 0;
}
else if(bf == 1)
{
// subRL的右子树新增
parent->_bf = -1;
subR->_bf = 0;
subRL->_bf = 0;
}
else
{
assert(false); // 检查点
}
}
...
private:
Node* _root = nullptr;
size_t _size = 0;
};
5. 完善插入：
- 旋转完成后是不需要继续向上更新平衡因子的，因为（1）旋转让这棵树平衡了；（2）旋转降低了这棵子树的高度，恢复到更插入前一样的高度，所以对上一层没有影响，不用更新。
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);
_size++;
return true;
}
Node* parent = nullptr;
Node* cur = _root;
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;
cur->_parent = parent;
}
else
{
parent->_left = cur;
cur->_parent = parent;
}
_size++;
// 调整，AVL树的核心部分
while (parent)
{
// 平衡因子的更新
if (cur == parent->_left)
{
// 插入在左节点，_bf--
parent->_bf--;
}
else
{
// 插入在右节点，_bf++
parent->_bf++;
}
// 判断是否要继续向上更新，和是否旋转调整
if (parent->_bf == 0)
{
// 更新后 _bf == 0，说明子树高度不变，不需要往上更新
break;
}
else if (parent->_bf == 1 || parent->_bf == -1)
{
// 更新后子树高度改变，需要往上更新
cur = parent;
parent = parent->_parent;
}
else if (parent->_bf == 2 || parent->_bf == -2)
{
// 平衡因子绝对值等于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)
{
// 先右边高，再左边高，右左双旋
RotateRL(parent);
}
else if (parent->_bf == -2 && cur->_bf == 1)
{
// 先左边高，再右边高，左右双旋
RotateLR(parent);
}
else
{
assert(false);
}
// 完成旋转后，不需要再往上更新平衡因子了，直接break
// 1、旋转让这棵树平衡了
// 2、旋转降低了这棵子树的高度，恢复到更插入前一样的高度，所以对上一层没有影响，不用更新
break;
}
else
{
// 平衡因子绝对值大于2，直接报错
assert(false);
}
}
return true;
}
...
private:
Node* _root = nullptr;
size_t _size = 0;
};
5. AVL树的验证
1. 验证其为二叉搜索树：
- 如果中序遍历可得到一个有序的序列，就说明为二叉搜索树。
2. 验证其为平衡树：
- 每个节点子树高度差的绝对值不超过1；
- 节点的平衡因子是否计算正确。
3. 相关函数实现：
template<class K, class V>
class AVLTree
{
typedef AVLTreeNode<K, V> Node;
public:
void _InOrder(Node* root)
{
if (root == nullptr)
return;
_InOrder(root->_left);
cout << root->_kv.first << " ";
_InOrder(root->_right);
}
void InOrder()
{
_InOrder(_root);
cout << endl;
}
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;
}
int Height()
{
return _Height(_root);
}
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 << "平衡因子异常" << endl;
return false;
}
return abs(rightHeight - leftHeight) < 2
&& _IsBalance(root->_left)
&& _IsBalance(root->_right);
}
size_t Size() const
{
return _size;
}
...
private:
Node* _root = nullptr;
size_t _size = 0;
};
4. 测试代码：
void Test()
{
const int N = 100;
srand(time(0));
vector<int> v;
for (int i = 0; i < N; i++)
{
v.push_back(rand());
}
AVLTree<int, int> tree;
for (auto e : v)
{
tree.Insert(make_pair(e, e));
}
tree.InOrder(); // 检查是否有序
cout << tree.IsBalance() << endl; // 检查是否平衡
cout << tree.Height() << endl; // 看看高度
cout << tree.Size() << endl; // 看看数据量
}
6. AVL树的删除（了解）
1. 思路：
- 因为AVL树也是二叉搜索树，可按照二叉搜索树的方式将节点删除，然后再更新平衡因子。只不过，平衡因子更新最差情况下要一直调整到根节点的位置。
2. 例：
- 假如我们要删除根节点，可以先在右子树找到替换节点6，进行替换删除，然后更新平衡因子，得到的树如下图所示：
- 更新7这个节点的平衡因子，更新为2，不用继续向上更新了，对7节点进行左单旋调整即可。
删除的代码不再写了，面试时也几乎不会考察，最多考察思路。
7. AVL树实现完整代码
#pragma once
#include<iostream>
#include<assert.h>
using namespace std;
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)
{}
};
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);
_size++;
return true;
}
Node* parent = nullptr;
Node* cur = _root;
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;
cur->_parent = parent;
}
else
{
parent->_left = cur;
cur->_parent = parent;
}
_size++;
// 调整，AVL树的核心部分
while (parent)
{
// 平衡因子的更新
if (cur == parent->_left)
{
// 插入在左节点，_bf--
parent->_bf--;
}
else
{
// 插入在右节点，_bf++
parent->_bf++;
}
// 判断是否要继续向上更新，和是否旋转调整
if (parent->_bf == 0)
{
// 更新后 _bf == 0，说明子树高度不变，不需要往上更新
break;
}
else if (parent->_bf == 1 || parent->_bf == -1)
{
// 更新后子树高度改变，需要往上更新
cur = parent;
parent = parent->_parent;
}
else if (parent->_bf == 2 || parent->_bf == -2)
{
// 平衡因子绝对值等于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)
{
// 先右边高，再左边高，右左双旋
RotateRL(parent);
}
else if (parent->_bf == -2 && cur->_bf == 1)
{
// 先左边高，再右边高，左右双旋
RotateLR(parent);
}
else
{
assert(false);
}
// 完成旋转后，不需要再往上更新平衡因子了，直接break
// 1、旋转让这棵树平衡了
// 2、旋转降低了这棵子树的高度，恢复到更插入前一样的高度，所以对上一层没有影响，不用更新
break;
}
else
{
// 平衡因子绝对值大于2，直接报错
assert(false);
}
}
return true;
}
// 左单旋
void RotateL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
// 更新左右节点
parent->_right = subRL;
subR->_left = parent;
// 提前记录parent的parent
Node* parentParent = parent->_parent;
// 更新_parent
parent->_parent = subR;
if (subRL) // 判断为不为空，subRL是唯一一个可能为空的节点
{
subRL->_parent = parent;
}
// 处理根
if (_root == parent)
{
_root = subR;
subR->_parent = nullptr;
}
else if (parentParent->_left == parent)
{
parentParent->_left = subR;
subR->_parent = parentParent;
}
else
{
parentParent->_right = subR;
subR->_parent = parentParent;
}
// 更新平衡因子
parent->_bf = subR->_bf = 0;
}
// 右单旋
void RotateR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
// 更新左右节点
subL->_right = parent;
parent->_left = subLR;
Node* parentParent = parent->_parent;
// 更新_parent
parent->_parent = subL;
if (subLR)
{
subLR->_parent = parent;
}
if (_root == parent)
{
_root = subL;
subL->_parent = nullptr;
}
else if (parentParent->_left == parent)
{
parentParent->_left = subL;
subL->_parent = parentParent;
}
else
{
parentParent->_right = subL;
subL->_parent = parentParent;
}
parent->_bf = subL->_bf = 0;
}
// 右左双旋
void RotateRL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
int bf = subRL->_bf; // 提前记录subRL的平衡因子，避免单旋操作后，值丢失
// 先右旋再左旋
RotateR(parent->_right);
RotateL(parent);
// 更新平衡因子
if (bf == 0)
{
// subRL自己就是新增节点
parent->_bf = subR->_bf = subRL->_bf = 0;
}
else if (bf == -1)
{
// subRL的左子树新增
parent->_bf = 0;
subR->_bf = 1;
subRL->_bf = 0;
}
else if(bf == 1)
{
// subRL的右子树新增
parent->_bf = -1;
subR->_bf = 0;
subRL->_bf = 0;
}
else
{
assert(false); // 检查点
}
}
// 左右双旋
void RotateLR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
int bf = subLR->_bf; // 提前记录subLR的平衡因子，避免单旋操作后，值丢失
// 先左旋再右旋
RotateL(parent->_left);
RotateR(parent);
// 更新平衡因子
if (bf == 0)
{
// subLR自己就是新增节点
subL->_bf = subLR->_bf = parent->_bf = 0;
}
else if (bf == -1)
{
// subLR的左子树新增
parent->_bf = 1;
subL->_bf = subLR->_bf = 0;
}
else if (bf == 1)
{
// subLR的右子树新增
parent->_bf = subLR->_bf = 0;
subL->_bf = -1;
}
else
{
assert(false); // 检查点
}
}
Node* Find(const K& key)
{
Node* cur = _root;
while (cur)
{
if (cur->_kv.first < key)
{
cur = cur->_right;
}
else if (cur->_kv.first > key)
{
cur = cur->_left;
}
else
{
return cur;
}
}
return nullptr;
}
void _InOrder(Node* root)
{
if (root == nullptr)
return;
_InOrder(root->_left);
cout << root->_kv.first << " ";
_InOrder(root->_right);
}
void InOrder()
{
_InOrder(_root);
cout << endl;
}
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;
}
int Height()
{
return _Height(_root);
}
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 << "平衡因子异常" << endl;
return false;
}
return abs(rightHeight - leftHeight) < 2
&& _IsBalance(root->_left)
&& _IsBalance(root->_right);
}
size_t Size() const
{
return _size;
}
private:
Node* _root = nullptr;
size_t _size = 0;
};
8. AVL树的性能
AVL树是一棵绝对平衡的二叉搜索树，其要求每个节点的左右子树高度差的绝对值都不超过1，这样可以保证查询时高效的时间复杂度，即 l o g 2 ( N ) log_2 (N) log2(N)。但是如果要对AVL树做一些结构修改的操作，性能非常低下，比如：
- 插入时要维护其绝对平衡，旋转的次数比较多，更差的是在删除时，有可能一直要让旋转持续到根的位置。
因此：如果需要一种查询高效且有序的数据结构，而且数据的个数为静态的(即不会改变)，可以考虑AVL树。但是一个经常修改的结构，就不太适合用AVL树。
9. AVL的封装，终极版本
记得是大二的时候，本人曾经用AVL树做过一个课题。当时需要一颗功能完善的AVL树，需要能够遍历和删除节点。为了实现这两个功能，本人曾经手撕了AVL树。时隔多年，无意间翻到当初的代码，竟然忘了自己曾经实现过迭代器部分和删除部分，这部分代码还差点被删除。为了让自己努力成果保存下来，现在将这棵终极AVL树放在博客里，实现赛博永生！！！
1. 树的源码：
#pragma once
#include<iostream>
#include<assert.h>
using namespace std;
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)
{}
};
template<class K, class V>
struct __TreeIterator
{
typedef AVLTreeNode<K, V> Node;
typedef __TreeIterator<K, V> Self;
Node* _node;//迭代器存的是二叉树的节点
__TreeIterator(Node* node)
:_node(node)
{}
pair<K, V>& operator*()
{
return _node->_kv;
}
pair<K, V>* operator->()
{
return &_node->_kv;
}
//这就是平衡二叉树迭代器的运行核心 一定要理解这部分逻辑才能理解好这个迭代器
Self& operator++()
{
if (_node->_right)
{
// 下一个就是右子树的最左节点
Node* cur = _node->_right;
while (cur->_left)
{
cur = cur->_left;
}
_node = cur;
}
else
{
// 左子树 根 右子树
// 右为空，找孩子是父亲左的那个祖先
Node* cur = _node;
Node* parent = cur->_parent;
while (parent && cur == parent->_right)
{
cur = parent;
parent = parent->_parent;
}
_node = parent;
}
return *this;
}
//给外界判断提供的
bool operator!=(const Self& s)
{
return _node != s._node;
}
bool operator==(const Self& s)
{
return _node == s._node;
}
};
template<class K, class V>
class AVLTree
{
typedef AVLTreeNode<K, V> Node;
typedef struct __TreeIterator<K, V> iterator;
public:
iterator begin()
{
Node* cur = _root;
if (cur == nullptr)
return cur;
while (cur->_left)
{
cur = cur->_left;
}
return cur;
}
iterator end()
{
return nullptr;
}
bool Insert(const pair<K, V>& kv)
{
// 插入，类比搜索二叉树插入
if (_root == nullptr)
{
_root = new Node(kv);
_size++;
return true;
}
Node* parent = nullptr;
Node* cur = _root;
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;
cur->_parent = parent;
}
else
{
parent->_left = cur;
cur->_parent = parent;
}
_size++;
// 调整，AVL树的核心部分
while (parent)
{
// 平衡因子的更新
if (cur == parent->_left)
{
// 插入在左节点，_bf--
parent->_bf--;
}
else
{
// 插入在右节点，_bf++
parent->_bf++;
}
// 判断是否要继续向上更新，和是否旋转调整
if (parent->_bf == 0)
{
// 更新后 _bf == 0，说明子树高度不变，不需要往上更新
break;
}
else if (parent->_bf == 1 || parent->_bf == -1)
{
// 更新后子树高度改变，需要往上更新
cur = parent;
parent = parent->_parent;
}
else if (parent->_bf == 2 || parent->_bf == -2)
{
// 平衡因子绝对值等于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)
{
// 先右边高，再左边高，右左双旋
RotateRL(parent);
}
else if (parent->_bf == -2 && cur->_bf == 1)
{
// 先左边高，再右边高，左右双旋
RotateLR(parent);
}
else
{
assert(false);
}
// 完成旋转后，不需要再往上更新平衡因子了，直接break
// 1、旋转让这棵树平衡了
// 2、旋转降低了这棵子树的高度，恢复到更插入前一样的高度，所以对上一层没有影响，不用更新
break;
}
else
{
// 平衡因子绝对值大于2，直接报错
assert(false);
}
}
return true;
}
// 左单旋
void RotateL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
// 更新左右节点
parent->_right = subRL;
subR->_left = parent;
// 提前记录parent的parent
Node* parentParent = parent->_parent;
// 更新_parent
parent->_parent = subR;
if (subRL) // 判断为不为空，subRL是唯一一个可能为空的节点
{
subRL->_parent = parent;
}
// 处理根
if (_root == parent)
{
_root = subR;
subR->_parent = nullptr;
}
else if (parentParent->_left == parent)
{
parentParent->_left = subR;
subR->_parent = parentParent;
}
else
{
parentParent->_right = subR;
subR->_parent = parentParent;
}
// 更新平衡因子
parent->_bf = subR->_bf = 0;
}
// 右单旋
void RotateR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
// 更新左右节点
subL->_right = parent;
parent->_left = subLR;
Node* parentParent = parent->_parent;
// 更新_parent
parent->_parent = subL;
if (subLR)
{
subLR->_parent = parent;
}
if (_root == parent)
{
_root = subL;
subL->_parent = nullptr;
}
else if (parentParent->_left == parent)
{
parentParent->_left = subL;
subL->_parent = parentParent;
}
else
{
parentParent->_right = subL;
subL->_parent = parentParent;
}
parent->_bf = subL->_bf = 0;
}
// 右左双旋
void RotateRL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
int bf = subRL->_bf; // 提前记录subRL的平衡因子，避免单旋操作后，值丢失
// 先右旋再左旋
RotateR(parent->_right);
RotateL(parent);
// 更新平衡因子
if (bf == 0)
{
// subRL自己就是新增节点
parent->_bf = subR->_bf = subRL->_bf = 0;
}
else if (bf == -1)
{
// subRL的左子树新增
parent->_bf = 0;
subR->_bf = 1;
subRL->_bf = 0;
}
else if(bf == 1)
{
// subRL的右子树新增
parent->_bf = -1;
subR->_bf = 0;
subRL->_bf = 0;
}
else
{
assert(false); // 检查点
}
}
// 左右双旋
void RotateLR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
int bf = subLR->_bf; // 提前记录subLR的平衡因子，避免单旋操作后，值丢失
// 先左旋再右旋
RotateL(parent->_left);
RotateR(parent);
// 更新平衡因子
if (bf == 0)
{
// subLR自己就是新增节点
subL->_bf = subLR->_bf = parent->_bf = 0;
}
else if (bf == -1)
{
// subLR的左子树新增
parent->_bf = 1;
subL->_bf = subLR->_bf = 0;
}
else if (bf == 1)
{
// subLR的右子树新增
parent->_bf = subLR->_bf = 0;
subL->_bf = -1;
}
else
{
assert(false); // 检查点
}
}
void Erase_rotate(Node* cur) //删除节点的操作函数 传入的是已经修改过bf的删除节点的父节点
{
Node* prev = nullptr;
while (cur)
{
if (cur->_bf == 1 || cur->_bf == -1)
break;
else if (cur->_bf == 0)
{
prev = cur;
cur = cur->_parent;
}
else if (cur->_bf == 2)
{
if (cur->_right->_bf == 1) //左单旋
{
RotateL(cur);
prev = cur->_parent;
cur = prev->_parent;
continue;
}
else if (cur->_right->_bf == -1) //先来一个右单旋 再来一个左单旋
{
Node* subR = cur->_left;
Node* subRL = subR->_left;
int _bf = subRL->_bf;
RotateR(cur->_right);
RotateL(cur);
if (_bf == 1)
{
cur->_bf = -1;
subR->_bf = 0;
}
else if (_bf == -1)
{
cur->_bf = 0;
subR->_bf = 1;
}
else if (_bf == 0)
{
cur->_bf = 0;
subR->_bf = 0;
}
cur = subRL->_parent;
prev = subRL;
continue;
}
else if (cur->_right->_bf == 0)
{
RotateL(cur);
cur->_parent->_bf = -1;
cur->_bf = 1;
break; //由于旋转完的树的bf的值为-1，所以不用继续循环
}
}
else if (cur->_bf == -2)
{
if (cur->_left->_bf == 1) // 先来一个左单旋 再来一个右单旋
{
Node* subL = cur->_left;
Node* subLR = subL->_right;
int _bf = subLR->_bf;
RotateL(cur->_left);
RotateR(cur);
if (_bf == 1)
{
cur->_bf = 0;
subL->_bf = -1;
}
else if (_bf == -1)
{
cur->_bf = 1;
subL->_bf = 0;
}
else if (_bf == 0)
{
cur->_bf = 0;
subL->_bf = 0;
}
cur = subLR->_parent;
prev = subLR;
continue;
}
else if (cur->_left->_bf == -1) //右单旋
{
RotateR(cur);
prev = cur->_parent;
cur = prev->_parent;
continue;
}
else if (cur->_left->_bf == 0)
{
RotateR(cur);
cur->_bf = -1;
cur->_parent->_bf = 1;
break;
}
}
if (cur && prev == cur->_left)
{
(cur->_bf)++;
}
else if (cur && prev == cur->_right)
{
(cur->_bf)--;
}
}
}
bool Erase(const pair<K, V>& x)
{
if (_root == nullptr) //开头检查一下是否是空树
assert(_root == nullptr);
Node* cur = _root;
Node* father = _root;
while (cur)
{
if (cur->_kv.first < x.first)
{
father = cur;
cur = cur->_right;
}
else if (cur->_kv.first > x.first)
{
father = cur;
cur = cur->_left;
}
else
{
//删除操作
if (cur->_left == nullptr || cur->_right == nullptr) //左右子树至少一个为空
{
if (cur == _root) //cur是根结点的情况要考虑一下！
{
_root = (cur->_left == nullptr) ? cur->_right : cur->_left; //不可能出现旋转的情况
}
else if (cur->_left == nullptr && cur->_right == nullptr) //左右子树均为空
{
if (father->_left == cur)
{
father->_left = nullptr;
delete cur;
father->_bf++;
}
else
{
father->_right = nullptr;
delete cur;
father->_bf--;
}
Erase_rotate(father);
}
else if (cur->_left == nullptr && cur->_right != nullptr) //左空右不空
{
cur->_kv = cur->_right->_kv;
Node* temp = cur->_right;
cur->_right = nullptr;
delete temp;
cur->_bf--;
Erase_rotate(cur);
}
else if (cur->_right == nullptr && cur->_left == nullptr) //右空左不空
{
cur->_kv = cur->_left->_kv;
Node* temp = cur->_left;
cur->_left = nullptr;
delete temp;
cur->_bf++;
Erase_rotate(cur);
}
}
else //左右子树都不为空
{
//找到右子树中的最小值与cur节点的值进行替换
//找右子树最小节点,也就是右子树的最左边的节点，这个节点：左子树一定为null，右子树未知
Node* Newcur = cur->_left;
Node* Newcur_father = cur;
while (Newcur->_right)
{
Newcur_father = Newcur;
Newcur = Newcur->_right;
}
cur->_kv = Newcur->_kv;
//现在要搞清楚等效删除的是哪个节点，以及从哪个节点开始向上检查！
if (Newcur_father == cur)
{
if (Newcur->_left) //相当于删除的是Newcur的右节点，改变Newcur的bf，并从Newcur节点向上检查
{
Newcur->_kv = Newcur->_left->_kv;
Node* temp = Newcur->_left;
Newcur->_left = nullptr;
delete temp;
Newcur->_bf++;
Erase_rotate(Newcur);
}
else //相当于删除的是Newcur节点，改变Newcur_father的bf，并从Newcur_father向上检查
{
Newcur_father->_left = nullptr;
delete Newcur;
Newcur_father->_bf++; //这是if (Newcur_father == cur)两种情况的本质区别
Erase_rotate(Newcur_father);
}
}
else
{
if (Newcur->_left) //相当于删除的是Newcur的右节点，改变Newcur的bf，并从Newcur节点向上检查
{
//这种情况就是上面 左子树为空右子树不为空
Newcur->_kv = Newcur->_left->_kv;
Node* temp = Newcur->_left;
Newcur->_left = nullptr;
delete temp;
Newcur->_bf++;
Erase_rotate(Newcur);
}
else //相当于删除的是Newcur节点，改变Newcur_father的bf，并从Newcur_father向上检查
{
//这种情况就是上面 左右子树 均为空的删除情况
Newcur_father->_right = nullptr;
delete Newcur;
Newcur_father->_bf--;
Erase_rotate(Newcur_father);
}
}
}
return true;
}
}
return false;
}
Node* Find(const K& key)
{
Node* cur = _root;
while (cur)
{
if (cur->_kv.first < key)
{
cur = cur->_right;
}
else if (cur->_kv.first > key)
{
cur = cur->_left;
}
else
{
return cur;
}
}
return nullptr;
}
void _InOrder(Node* root)
{
if (root == nullptr)
return;
_InOrder(root->_left);
cout << root->_kv.first << " ";
_InOrder(root->_right);
}
void InOrder()
{
_InOrder(_root);
cout << endl;
}
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;
}
int Height()
{
return _Height(_root);
}
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 << "平衡因子异常" << endl;
return false;
}
return abs(rightHeight - leftHeight) < 2
&& _IsBalance(root->_left)
&& _IsBalance(root->_right);
}
size_t Size() const
{
return _size;
}
private:
Node* _root = nullptr;
size_t _size = 0;
};
2. 测试样例：
#include<iostream>
#include"AVLTree.h"
#include<vector>
// 测试insert
void Test()
{
const int N = 100;
srand(time(0));
vector<int> v;
for (int i = 0; i < N; i++)
{
v.push_back(rand());
}
AVLTree<int, int> tree;
for (auto e : v)
{
tree.Insert(make_pair(e, e));
}
tree.InOrder();
cout << tree.IsBalance() << endl;
cout << tree.Height() << endl;
cout << tree.Size() << endl;
}
// 测试find，并记录时间
void Test2()
{
const int N = 100000;
srand(time(0));
vector<int> v;
for (int i = 0; i < N; i++)
{
v.push_back(rand());
}
AVLTree<int, int> tree;
for (auto e : v)
{
tree.Insert(make_pair(e, e));
}
size_t begin = clock();
for (size_t i = 0; i < N; i++)
{
tree.Find((rand() + i));
}
size_t end = clock();
cout << "Find time:" << end - begin << endl;
}
// 测试迭代器功能
void Test3()
{
const int N = 100;
srand(time(0));
vector<int> v;
for (int i = 0; i < N; i++)
{
v.push_back(rand());
}
AVLTree<int, int> tree;
for (auto e : v)
{
tree.Insert(make_pair(e, e));
}
tree.InOrder();
cout << "=======================" << endl;
for (auto e : tree)
{
cout << e.second << " ";
}
cout << endl;
}
// 测试删除功能
void Test4()
{
const int N = 100;
vector<int> v;
for (int i = 0; i < N; i++)
{
v.push_back(i);
}
AVLTree<int, int> tree;
for (auto e : v)
{
tree.Insert(make_pair(e, e));
}
tree.InOrder();
cout << "=======================" << endl;
for (auto e : tree)
{
cout << e.second << " ";
}
cout << endl;
cout << "=======================" << endl;
tree.Erase(make_pair(99, 99));
tree.InOrder();
cout << tree.IsBalance() << endl;
tree.Erase(make_pair(90, 90));
tree.Erase(make_pair(66, 66));
tree.Erase(make_pair(35, 35));
cout << "=======================" << endl;
tree.InOrder();
cout << tree.IsBalance() << endl;
}
int main()
{
// Test1();
// Test2();
// Test3();
Test4();
return 0;
}
一座年轻的奋斗人之城，一个温馨的开发者之家。在这里，代码改变人生，开发创造未来！
更多推荐
19
0- 0
已为社区贡献1条内容
所有评论(0)