引入
二叉搜索树有其自身的缺陷，假如往树中 插入的元素有序或者接近有序，二叉搜索树就会退化成单支树，时间复杂度会退化成O(N)，因此 map、set等关联式容器的底层结构是对二叉树进行了平衡处理，即采用平衡树来实现。简单来说就是之前二叉搜索树由于可能在某一个节点上一直深入，按照最坏情况算这的时间复杂度就高了起来，而AVL树这其中之一的平衡树
1.AVL树的概念
二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树，查 找元素相当于在顺序表中搜索元素，效率低下。因此，两位俄罗斯的数学家G.M.Adelson-Velskii 和E.M.Landis在1962年 发明了一种解决上述问题的方法：当向二叉搜索树中插入新结点后，如果能保证每个结点的左右 子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均 搜索长度
AVL树又称高度平衡二叉搜索树
任何AVL树都满足一下条件:
- 它的左右子树都是AVL树
- 任何树及其子树的高度差(也就是平衡因子)的绝对值不超过1
比如：
当然平衡因子不一定是必须的，它只是一种控制方式(让我们更便捷地控制这棵树)
为何是不超过1，而不是0呢？0不是更加平衡吗？
由于树的节点是一个个插入的，无法保证绝对的平衡(有些情况无法满足高度差为0)；因此高度差不超过1
2.AVL树节点的定义
和二叉搜索树类似，只不过多了个平衡因子
//AVL树的节点
template<class K,class V>
struct AVLTreeNode
{
AVLTreeNode<K,V>* _left;
AVLTreeNode<K,V>* _right;
AVLTreeNode<K,V>* _parent;
int _bf = 0;//平衡因子
pair<K, V> _kv;
//构造
AVLTreeNode(const pair<K, V>& kv)
:_left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _bf(0)
, _kv(kv)
{}
};
3.AVL树的插入
3.1插入
AVL树就是在二叉搜索树的基础上引进了平衡因子(bf)，因此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 (kv.first > cur->_kv.first)//插入的值比遍历的值大
{
parent = cur;//cur往下遍历时，父节点同时要往下走
cur = cur->_right;//往右走
}
else if (kv.first < cur->_kv.first)//插入的值比遍历的值小
{
parent = cur;
cur = cur->_left;//往左走
}
else//说明插入的值已经存在，return false
{
return false;
}
}
//走到这说明已经找到可以插入的地方
//创建一个新节点
cur = new Node(kv);
//判断插入的节点该连接到父节点的左还是右
if (cur->_kv.first > parent->_kv.first)//cur 的值大于父节点的值，连右
{
parent->_right = cur;
}
else
{
parent->_left = cur;
}
//接下来就是判断平衡因子的时候了
return true;
}判断平衡因子
平衡因子 = 右子树高度-左子树高度
插入节点会影响哪些节点的平衡因子呢？新增节点的部分祖先
更新原则：
若cur是此父节点的左子树(节点)那么父节点的平衡因子-- ，是右子树(节点)那么父节点平衡因子++
是否继续更新取决于父节点的高度是否变化，是否会影响爷爷节点
一直往上走直至parent为nullptr(根节点的父节点为空)或者平衡因子为0或者平衡因子为2(需要旋转)
当cur(新增节点插入后)，有三种情况
情况1：
更新后 父节点(parent)的平衡因子(bf)为 0 ，parent所在子树高度不变，不会影响爷爷；说明更新前parent的bf为1或-1，往父节点矮的那边插入节点，左右均衡，parent所在子树的高度不变
情况2：
更新后 父节点的平衡因子为1或-1，parent所在子树高度改变了，会影响爷爷，继续往上更新；说明更新前parent的bf为0(本身平衡了)，往p的任意一边插入，使父节点变得不均衡，但不违反规则
情况3：
更新后父节点的平衡因子为2或-2，说明父节点所在的子树违反了平衡规则，需要旋转处理
//接下来就是判断平衡因子的时候了
cur->_parent = parent;
while (parent)
{
if (cur == parent->_left)//cur在父左 父bf--
{
parent->_bf--;
}
else//cur在父右 父bf++
{
parent->_bf++;
}
if (parent->_bf == 0)//父bf==0 break
{
break;
}
else if (parent->_bf == 1 || parent->_bf == -1)//父bf为1 or -1继续往上
{
cur = 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)//两边都高左右双旋
{
RotateLR(parent);
}
else//右左双旋
{
RotateRL(parent);
}
}
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 (kv.first > cur->_kv.first)//插入的值比遍历的值大
{
parent = cur;//cur往下遍历时，父节点同时要往下走
cur = cur->_right;//往右走
}
else if (kv.first < cur->_kv.first)//插入的值比遍历的值小
{
parent = cur;
cur = cur->_left;//往左走
}
else//说明插入的值已经存在，return false
{
return false;
}
}
//走到这说明已经找到可以插入的地方
//创建一个新节点
cur = new Node(kv);
//判断插入的节点该连接到父节点的左还是右
if (cur->_kv.first > parent->_kv.first)//cur 的值大于父节点的值，连右
{
parent->_right = cur;
}
else
{
parent->_left = cur;
}
//接下来就是判断平衡因子的时候了
cur->_parent = parent;
//若cur是此父节点的左子树(节点)那么父节点的平衡因子-- ，是右子树(节点)那么父节点平衡因子++
//一直往上走直至parent为nullptr(根节点的父节点为空)或者平衡因子为0或者平衡因子为2(需要旋转)
while (parent)
{
if (cur == parent->_left)//cur在父左 父bf--
{
parent->_bf--;
}
else//cur在父右 父bf++
{
parent->_bf++;
}
if (parent->_bf == 0)//父bf==0 break
{
break;
}
else if (parent->_bf == 1 || parent->_bf == -1)//父bf为1 or -1继续往上
{
cur = 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)//两边都高左右双旋
{
RotateLR(parent);
}
else//右左双旋
{
RotateRL(parent);
}
}
else
{
assert(false);
}
}
return true;
}3.2旋转
如果在一棵原本是平衡的AVL树中插入一个新节点，可能造成不平衡，此时必须调整树的结构，使之平衡化。根据节点插入位置的不同，AVL树的旋转分为四种：左单旋、右单旋、左右双旋以及右左双旋
左单旋——新节点插入较高右子树的右侧---右右
void RotateL(Node* parent)//左单旋
{
//sub是parent ，subR是parent的右节点，subRL是subR的左节点
Node* subR = parent->_right;
Node* subRL = subR->_left;
parent->_right = subRL;//父节点的右节点指向subRL
//subRL可能为空节点，也就是这颗树(子树)只有sub(parent节点)、subR、以及新增节点这三个节点 如果subRL为空，就不用将其父节点指向sub了
if (subRL)
{
subRL->_parent = parent;
}
Node* ppnode = parent->_parent;
parent->_parent = subR;//把父节点的父节点指向subR
//父节点(sub)有可能是一颗树(子树)的根节点
//如果(sub)是一颗树的根节点的话 subR直接为根节点，subR的parent直接是空
if (parent = _root)
{
subR = _root;
subR->_parent = nullptr;
}
else//sub是一颗子树的根节点
{
//得看sub是其父节点的左节点还是右节点
//然后subR连接sub的父节点
if (parent == ppnode->_left)
{
ppnode->_left = subR;
}
else
{
ppnode->_right = subR;
}
subR->_parent = ppnode;
}
//sub和subR平衡因子置为0
subR->_bf = 0;
parent->_bf = 0;
}右单旋——新节点插入较高左子树的左侧---左左
//右单旋思路和左单旋差不多
void RotateR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
parent->_left = subLR;
if (subLR)
subLR->_parent = parent;
Node* ppnode = parent->_parent;
parent->_parent = subL;
if (parent == _root)
{
subL = _root;
subL->_parent = nullptr;
}
else
{
if (parent == ppnode->_left)
{
ppnode->_left = subL;
}
else
{
ppnode->_right = subL;
}
subL->_parent = ppnode;
}
subL->_bf = 0;
parent->_bf = 0;
}左右双旋—— 新节点插入较高左子树的右侧---左右(先左单旋再右单旋)
左右两边都高单旋解决不了问题
//左右双旋
void RotateLR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
//subLR的平衡因子不同时对其它节点的平衡因子的改变也不同
int bf = subLR->_bf;
RotateL(parent->_left);//先走左单旋
RotateR(parent);//再走右单旋
if (bf == -1)//若subLR的bf为-1，则新增节点是subLR的左子树
{
subLR->_bf = 0;
subL->_bf = 0;
parent->_bf = 1;
}
else if (bf == 1)//若subLR的bf为1，则新增节点是subLR的右子树
{
subLR->_bf = 0;
subL->_bf = -1;
parent->_bf = 0;
}
else if (bf == 0) //若subLR的bf为0,那么subLR其本身就是新增节点
{
subLR->_bf = 0;
subL->_bf = 0;
parent->_bf = 0;
}
else
{
assert(false);
}
}右左双旋——新节点插入较高右子树的左侧---右左(先右单旋再左单旋)
void RotateRL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
int bf = subRL->_bf;
RotateR(subR);
RotateL(parent);
if (bf == -1)
{
subRL->_bf = 0;
subR->_bf = 1;
parent->_bf = 0;
}
else if (bf == 1)
{
subRL->_bf = 0;
subR->_bf = 0;
parent->_bf = -1;
}
else if (bf == 0)
{
subRL->_bf = 0;
subR->_bf = 0;
parent->_bf = 0;
}
else
{
assert(false);
}
}4.判断是否为AVL树
AVL树是在二叉搜索树的基础上加入了平衡性的限制，因此要验证AVL树，可以分两步：
1. 验证其为二叉搜索树 如果中序遍历可得到一个有序的序列，就说明为二叉搜索树
void _Inorder(Node* root)
{
if (root == nullptr)
return;
_Inorder(root->_left);
cout << root->_kv.first << "[" << root->_bf << "]" << endl;
_Inorder(root->_right);
}
void Inorder()
{
_Inorder(_root);
}2. 验证其为平衡树 每个节点子树高度差的绝对值不超过1(注意节点中如果没有平衡因子) 节点的平衡因子是否计算正确
int _Height(Node* root)
{
if (root == nullptr)
return;
int leftHight = Height(root->_left);
int rightHight = Height(root->_right);
return leftHight > rightHight ? leftHight + 1 : rightHight + 1;
}
int Height()
{
return _Height(_root);
}
bool _IsAVLTree(Node* root)
{
if (root == nullptr)
{
return true;
}
int leftHeight = Height(root->_left);
int rightHeight = Height(root->_right);
if (abs(leftHeight - rightHeight) >= 2)
{
cout << "不平衡" << endl;
return false;
}
if (rightHeight - leftHeight != root->_bf)
{
cout << root->_kv.first << "平衡因子异常" << endl;
return false;
}
return _IsAVLTree(root->_left)&&_IsAVLTree(root->_right);
}
bool IsAVLTree()
{
return _IsAVLTree(_root);
}如果走前序递归的话计算高度和前序递归会存在大量重复，所以还是走后序的同时求高度
后序先走左子树判断平衡返回高度；再走右子树判断平衡返回高度
bool _IsAVLTree(Node* root, int& height)
{
if (root == nullptr)
{
height = 0;
return true;
}
//走个后序
int leftHeight, rightHeight = 0;
if (!_IsAVLTree(root->_left, leftHeight) || !_IsAVLTree(root->_right, rightHeight))
{
return false;
}
if (abs(leftHeight - rightHeight) >= 2)
{
cout << "不平衡" << endl;
return false;
}
if (rightHeight - leftHeight != root->_bf)
{
cout << root->_kv.first << "平衡因子异常" << endl;
return false;
}
height = leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
return true;
}
bool IsAVLTree()
{
int height = 0;
return _IsAVLTree(_root, height);
}
