目录
前言
前面对 map/multimap/set/multiset 进行了简单的介绍，在其文档介绍中发现，这几个容器有个共同点是： 其底层都是按照二叉搜索树来实现的 ，但是二叉搜索树有其自身的缺陷，假如往树中插入的元素有序或者接近有序，二叉搜索树就会退化成单支树，时间复杂度会退化成O(N) ，因此map、 set 等关联式容器的底层结构是对二叉树进行了平衡处理，即采用平衡树来实现。
AVL树的概念
二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树，查找元素相当于在顺序表中搜索元素，效率低下。因此，两位俄罗斯的数学家G.M.Adelson-Velskii 和E.M.Landis在1962年 发明了一种解决上述问题的方法：当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的 绝对值 不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均 搜索长度。
一棵AVL树或者是空树，或者是具有以下性质的二叉搜索树：
- 它的左右子树都是AVL树
- 左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1）
如果一棵二叉搜索树是高度平衡的，它就是AVL树。如果它有n个结点，其高度可保持在
O(log2_ n)，搜索时间复杂度O(log2_ n)。
AVL树结点的定义
我们这里直接实现KV模型的AVL树，为了方便后续的操作，这里将AVL树中的结点定义为三叉链结构，并在每个结点当中引入平衡因子（右子树高度-左子树高度）。除此之外，还需编写一个构造新结点的构造函数，由于新构造结点的左右子树均为空树，于是将新构造结点的平衡因子初始设置为0即可。
template<class T> struct AVLTreeNode { AVLTreeNode(const T& data) : _pLeft(nullptr), _pRight(nullptr), _pParent(nullptr) , _data(data), _bf(0) {} AVLTreeNode<T>* _pLeft; // 该节点的左孩子 AVLTreeNode<T>* _pRight; // 该节点的右孩子 AVLTreeNode<T>* _pParent; // 该节点的双亲 T _data; int _bf; // 该节点的平衡因子 };
注意：
- 给每个结点增加平衡因子并不是必须的，只是实现AVL树的一种方式，不引入平衡因子也可以实现AVL树，只不过会麻烦一点
- 树中最大元素一定是无左子树，因为最大元素如果存在左子树，中序遍历就不可能是降序序列
- 插入时，AVL树最多只需要旋转两次
AVL树的插入
AVL树插入结点时有以下三个步骤：
- 按照二叉搜索树的插入方法，找到待插入位置。
- 找到待插入位置后，将待插入结点插入到树中。
- 更新平衡因子，如果出现不平衡，则需要进行旋转。
因为AVL树本身就是一棵二叉搜索树，因此寻找结点的插入位置是非常简单的，按照二叉搜索树的插入规则：
- 待插入结点的key值比当前结点小就插入到该结点的左子树。
- 待插入结点的key值比当前结点大就插入到该结点的右子树。
- 待插入结点的key值与当前结点的key值相等就插入失败。
如此进行下去，直到找到与待插入结点的key值相同的结点判定为插入失败，或者最终走到空树位置进行结点插入。
AVL树的平衡调整（重点）
向AVL树中插入新数据
- 和BST一样，首先在叶节点插入数据
- 若插入导致不平衡，则需对以插入路径上离插入节点最近的平衡因子绝对值大于1的节点为根的树进行调整
LL型不平衡（需右单旋转)
- 在某个子树的左子树的左子树上插入新节点，导致根节点的平衡因子由1变为2
右单旋的步骤如下：
- 让y的右子树作为x的左子树。
- 让x作为y的右子树。
- 让y作为整个子树的根。
- 更新平衡因子。
右单旋后满足二叉搜索树的性质：
- y的右子树当中结点的值本身就比x的值小，因此可以作为x的左子树。
- x及其右子树当中结点的值本身就比y的值大，因此可以作为y的右子树。
右单选代码实现
void RotateR(Node* pParent)
{
Node* pSubL = pParent->_pLeft;
Node* pSubLR = pSubL->_pRight;
// 改变pParent和pSubL孩子的指向
pParent->_pLeft = pSubLR;
if (pSubLR)
pSubLR->_pParent = pParent;
pSubL->_pRight = pParent;
// 更新pParent和pSubL的双亲
Node* pPParent = pParent->_pParent;
pParent->_pParent = pSubL;
pSubL->_pParent = pPParent;
// 更新原pParent双亲的左||右指针域指向
if (nullptr == pPParent)
{
_pRoot = pSubL;
}
else
{
if (pParent == pPParent->_pLeft)
pPParent->_pLeft = pSubL;
else
pPParent->_pRight = pSubL;
}
pParent->_bf = pSubL->_bf = 0;
}RR型不平衡（需左单旋转)
- 在某个子树的右子树的右子树上插入新节点，导致根节点的平衡因子由-1变为-2
左单旋的步骤如下：
- 让y的左子树作为x的右子树。
- 让x作为y的左子树。
- 让y作为整个子树的根。
- 更新平衡因子。
左单旋后满足二叉搜索树的性质：
- y的左子树当中结点的值本身就比x的值大，因此可以作为x的右子树。
- x及其左子树当中结点的值本身就比y的值小，因此可以作为y的左子树。
左单旋代码实现
void RotateL(Node* pParent)
{
Node* pSubR = pParent->_pRight;
Node* pSubRL = pSubR->_pLeft;
pParent->_pRight = pSubRL;
if (pSubRL)
pSubRL->_pParent = pParent;
pSubR->_pLeft = pParent;
Node* pPParent = pParent->_pParent;
pParent->_pParent = pSubR;
pSubR->_pParent = pPParent;
if (nullptr == pPParent)
{
_pRoot = pSubR;
}
else
{
if (pParent == pPParent->_pLeft)
pPParent->_pLeft = pSubR;
else
pPParent->_pRight = pSubR;
}
pParent->_bf = pSubR->_bf = 0;
}LR型不平衡（需左右双旋转)
- 在某个子树的左子树的右子树上插入新节点，导致根节点的平衡因子由1变为2
左右双旋的步骤如下：
- 以y为旋转点进行左单旋。
- 以x为旋转点进行右单旋。
- 更新平衡因子。
左右双旋后满足二叉搜索树的性质：
左右双旋后，实际上就是让z的左子树和右子树，分别作为y和x的右子树和左子树，再让y和x分别作为z的左右子树，最后让z作为整个子树的根（结合图理解）。
- z的左子树当中的结点本身就比y的值大，因此可以作为y的右子树。
- z的右子树当中的结点本身就比x的值小，因此可以作为x的左子树。
- 经过步骤1/2后，y及其子树当中结点的值都就比z的值小，而x及其子树当中结点的值都就比z的值大，因此它们可以分别作为z的左右子树。
左右双旋转代码实现
void RotateRL(Node* pParent)
{
Node* pSubR = pParent->_pRight;
Node* pSubRL = pSubR->_pLeft;
int bf = pSubRL->_bf;
RotateR(pParent->_pRight);
RotateL(pParent);
// 更新部分节点的平衡因子
if (bf == -1)
pSubR->_bf = 1;
else if (bf == 1)
pParent->_bf = -1;
}RL型不平衡（需右左双旋转)
- 在某个子树的右子树的左子树上插入新节点，导致根节点的平衡因子由-1变为-2
右左双旋的步骤如下：
- 以y为旋转点进行右单旋。
- 以x为旋转点进行左单旋。
- 更新平衡因子。
右左双旋后满足二叉搜索树的性质：
右左双旋后，实际上就是让z的左子树和右子树，分别作为x和y的右子树和左子树，再让x和y分别作为x的左右子树，最后让z作为整个子树的根（结合图理解）。
- z的左子树当中的结点本身就比x的值大，因此可以作为x的右子树。
- z的右子树当中的结点本身就比y的值小，因此可以作为y的左子树。
- 经过步骤1/2后，x及其子树当中结点的值都就比z的值小，而y及其子树当中结点的值都就比z的值大，因此它们可以分别作为z的左右子树。
右左双旋转代码实现
void RotateLR(Node* pParent)
{
Node* pSubL = pParent->_pLeft;
Node* pSubLR = pSubL->_pRight;
int bf = pSubLR->_bf;
RotateL(pParent->_pLeft);
RotateR(pParent);
if (-1 == bf)
pParent->_bf = 1;
else if (1 == bf)
pSubL->_bf = -1;
}AVL树简单实现以及验证-插入
函数接口
template<class T>
struct AVLTreeNode
{
AVLTreeNode(const T& data = T())
: _pLeft(nullptr)
, _pRight(nullptr)
, _pParent(nullptr)
, _data(data)
, _bf(0)
{}
AVLTreeNode<T>* _pLeft;
AVLTreeNode<T>* _pRight;
AVLTreeNode<T>* _pParent;
T _data;
int _bf; // 节点的平衡因子
};
// AVL: 二叉搜索树 + 平衡因子的限制
template<class T>
class AVLTree
{
typedef AVLTreeNode<T> Node;
public:
AVLTree()
: _pRoot(nullptr)
{}
// 在AVL树中插入值为data的节点
bool Insert(const T& data);
// AVL树的验证
bool IsAVLTree()
{
return _IsAVLTree(_pRoot);
}
private:
// 根据AVL树的概念验证pRoot是否为有效的AVL树
bool _IsAVLTree(Node* pRoot);
size_t _Height(Node* pRoot);
// 右单旋
void RotateR(Node* pParent);
// 左单旋
void RotateL(Node* pParent);
// 右左双旋
void RotateRL(Node* pParent);
// 左右双旋
void RotateLR(Node* pParent);
private:
Node* _pRoot;
};完整代码实现：
template<class T>
struct AVLTreeNode
{
AVLTreeNode(const T& data = T())
: _pLeft(nullptr)
, _pRight(nullptr)
, _pParent(nullptr)
, _data(data)
, _bf(0)
{}
AVLTreeNode<T>* _pLeft;
AVLTreeNode<T>* _pRight;
AVLTreeNode<T>* _pParent;
T _data;
int _bf; // 节点的平衡因子
};
// AVL: 二叉搜索树 + 平衡因子的限制
template<class T>
class AVLTree
{
typedef AVLTreeNode<T> Node;
public:
AVLTree()
: _pRoot(nullptr)
{}
bool Insert(const T& data)
{
// 先按照二叉搜索树的方式进行插入
if (nullptr == _pRoot)
{
_pRoot = new Node(data);
return true;
}
// 按照二叉搜索树特性：找待插入节点在树中的位置
// 并保存其双亲
Node* pCur = _pRoot;
Node* pParent = nullptr;
while (pCur)
{
pParent = pCur;
if (data < pCur->_data)
pCur = pCur->_pLeft;
else if (data > pCur->_data)
pCur = pCur->_pRight;
else
return false;
}
// 插入新节点
pCur = new Node(data);
if (data < pParent->_data)
pParent->_pLeft = pCur;
else
pParent->_pRight = pCur;
pCur->_pParent = pParent;
while (pParent)
{
// 更新pParent的平衡因子
if (pCur == pParent->_pLeft)
pParent->_bf--;
else
pParent->_bf++;
if (0 == pParent->_bf)
break;
else if (-1 == pParent->_bf || 1 == pParent->_bf)
{
pCur = pParent;
pParent = pCur->_pParent;
}
else
{
// pParent->_bf: 2 || -2
// pParent的节点失去平衡
if (2 == pParent->_bf)
{
// 右子树高-->最后必须左单旋
if (1 == pCur->_bf)
RotateL(pParent);
else
RotateRL(pParent);
}
else
{
if (-1 == pCur->_bf)
RotateR(pParent);
else
RotateLR(pParent);
}
break;
}
}
return true;
}
void InOrder()
{
_InOrder(_pRoot);
}
Node* LeftMost()
{
if (nullptr == _pRoot)
return nullptr;
Node* pCur = _pRoot;
while (pCur->_pLeft)
pCur = pCur->_pLeft;
return pCur;
}
Node* RightMost()
{
if (nullptr == _pRoot)
return nullptr;
Node* pCur = _pRoot;
while (pCur->_pRight)
pCur = pCur->_pRight;
return pCur;
}
bool IsAVLTree()
{
return _IsAVLTree(_pRoot);
}
private:
// 验证二叉搜索树是否为有效的
bool _IsAVLTree(Node* pRoot)
{
if (nullptr == pRoot)
return true;
int leftHeight = _Height(pRoot->_pLeft);
int rightHeight = _Height(pRoot->_pRight);
if (abs(rightHeight - leftHeight) > 1 ||
rightHeight - leftHeight != pRoot->_bf)
return false;
return _IsAVLTree(pRoot->_pLeft) && _IsAVLTree(pRoot->_pRight);
}
size_t _Height(Node* pRoot)
{
if (nullptr == pRoot)
return 0;
size_t leftHeight = _Height(pRoot->_pLeft);
size_t rightHeight = _Height(pRoot->_pRight);
return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}
void RotateR(Node* pParent)
{
Node* pSubL = pParent->_pLeft;
Node* pSubLR = pSubL->_pRight;
// 改变pParent和pSubL孩子的指向
pParent->_pLeft = pSubLR;
if (pSubLR)
pSubLR->_pParent = pParent;
pSubL->_pRight = pParent;
// 更新pParent和pSubL的双亲
Node* pPParent = pParent->_pParent;
pParent->_pParent = pSubL;
pSubL->_pParent = pPParent;
// 更新原pParent双亲的左||右指针域指向
if (nullptr == pPParent)
{
_pRoot = pSubL;
}
else
{
if (pParent == pPParent->_pLeft)
pPParent->_pLeft = pSubL;
else
pPParent->_pRight = pSubL;
}
pParent->_bf = pSubL->_bf = 0;
}
void RotateL(Node* pParent)
{
Node* pSubR = pParent->_pRight;
Node* pSubRL = pSubR->_pLeft;
pParent->_pRight = pSubRL;
if (pSubRL)
pSubRL->_pParent = pParent;
pSubR->_pLeft = pParent;
Node* pPParent = pParent->_pParent;
pParent->_pParent = pSubR;
pSubR->_pParent = pPParent;
if (nullptr == pPParent)
{
_pRoot = pSubR;
}
else
{
if (pParent == pPParent->_pLeft)
pPParent->_pLeft = pSubR;
else
pPParent->_pRight = pSubR;
}
pParent->_bf = pSubR->_bf = 0;
}
void RotateRL(Node* pParent)
{
Node* pSubR = pParent->_pRight;
Node* pSubRL = pSubR->_pLeft;
int bf = pSubRL->_bf;
RotateR(pParent->_pRight);
RotateL(pParent);
// 更新部分节点的平衡因子
if (bf == -1)
pSubR->_bf = 1;
else if (bf == 1)
pParent->_bf = -1;
}
void RotateLR(Node* pParent)
{
Node* pSubL = pParent->_pLeft;
Node* pSubLR = pSubL->_pRight;
int bf = pSubLR->_bf;
RotateL(pParent->_pLeft);
RotateR(pParent);
if (-1 == bf)
pParent->_bf = 1;
else if (1 == bf)
pSubL->_bf = -1;
}
void _InOrder(Node* pRoot)
{
if (pRoot)
{
_InOrder(pRoot->_pLeft);
cout << pRoot->_data << " ";
_InOrder(pRoot->_pRight);
}
}
private:
Node* _pRoot;
};