本章主要讲解map和set的底层结构平衡二叉搜索树的一种-AVL树的特性及其实现
对于数据有序或接近有序二叉搜索树将退化为单支树的情况,两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年 发明了一种解决上述问题的方法:当向二叉搜索树中插入新结点后,如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整),即可降低树的高度,从而减少平均搜索长度。
注:如果一棵二叉搜索树是高度可保持在1(-1/0/1),则非常接近完全二叉树 ,搜索时间复杂度O(logN)
为了方便找到子树对应的父亲节点,这里我们选择使用三叉链结构
template<class T>
struct AVLTreeNode
{
//三叉链
AVLTreeNode<T>* _left;
AVLTreeNode<T>* _right;
AVLTreeNode<T>* _parent;
int _bf;//平衡因子
T _kv;//T可以是key也可以是pair<K,V>类型便于封装成map或set
AVLTreeNode(const T& t)
:_left(nullptr)
,_right(nullptr)
,_parent(nullptr)
,_bf(0)
,_kv(t)
{}
};
AVL树就是在二叉搜索树的基础上引入了平衡因子,因此AVL树也可以看成是二叉搜索树
平衡因子数值=右子树高度-左子树的高度
1.如果新增结点在祖父节点的左子树中,则父节点平衡因子数值减1 2.如果新增结点在祖父节点的右子树中,则父节点平衡因子数值加1
1.更新后平衡因子为1或-1,那么说明该平衡因子更新前为0,子树的高度发生变化,则也会影响父亲结点的平衡因子,继续向上更新平衡因子 2.更新后平衡因子为0,那么说明该平衡因子更新前为1或-1,子树的高度未发生变化,则也不会影响父亲结点的平衡因子,停止向上更新平衡因子 3.更新后平衡因子为2或-2,那么当前子树不符合AVL树的规则,需要进行旋转子树进行调节高度
注:更新平衡因子之前,该树本身就满足AVL树的规则,平衡因子为1或0或-1
实现代码:
pair<Node*, bool> Insert(const pair<K,V>& kv)
{
if (_root == nullptr)//空树的情况
{
_root = new Node(kv);
return make_pair(_root, true);
}
//插入需要链接父子节点,但是插入的位置是空节点,需要另一个指针记录父结点
Node* cur = _root, *parent = _root;
while (cur)
{
if (cur->_kv.first > kv.first)
{
parent = cur;
cur = cur->_left;
}
else if (cur->_kv.first < kv.first)
{
parent = cur;
cur = cur->_right;
}
else//找到了相同的
{
return make_pair(cur,false);
}
}
//找到插入位置,创建链接节点
cur = new Node(kv);
Node* newnode = cur;//记录新结点地址,便于返回
if (parent->_kv.first > kv.first)
{
parent->_left = cur;
}
else
{
parent->_right = cur;
}
cur->_parent = parent;
//向上更新平衡因子
while (cur != _root)
{
if (parent->_right == cur)
{
parent->_bf++;
}
else
{
parent->_bf--;
}
if (parent->_bf == 0)//子树高度不变,不影响上面路径的结点平衡因子
{
break;
}
else if (parent->_bf == 1 || parent->_bf == -1)//子树高度改变,继续向上更新节点平衡因子
{
cur = parent;
parent = parent->_parent;
}
else if (parent->_bf == 2 || parent->_bf == -2)//子树已经不平衡了,需要进行旋转处理
{
if (parent->_bf == -2)
{
if (cur->_bf == -1)//右单旋
{
RotateR(parent);
}
else//左右双旋
{
RotateLR(parent);
}
}
else
{
if (cur->_bf == 1)//右单旋
{
RotateL(parent);
}
else//右左双旋
{
RotateRL(parent);
}
}
break;
}
else//已经出错了
{
assert(false);
}
}
return make_pair(newnode, true);
}
如果在一棵原本是平衡的AVL树中插入一个新节点,可能造成不平衡,此时必须调整树的结构,使之平衡
// 左单旋
void RotateL(Node* parent)
{
//记录节点信息
Node* subR = parent->_right;
Node* subRL = subR->_left;
Node* parentP = parent->_parent;
//修改链接关系
parent->_right = subRL;
if (subRL)//避免为空节点的情况
subRL->_parent = parent;
subR->_left = parent;
parent->_parent = subR;
//讨论父节点的情况
if (parent == _root)
{
_root = subR;
subR->_parent = nullptr;
}
else
{
if (parentP->_left == parent)
{
parentP->_left = subR;
}
else
{
parentP->_right = subR;
}
subR->_parent = parentP;
}
//更新平衡因子
subR->_bf = parent->_bf = 0;
}
注:具体思路和步骤可以参考左单旋
// 右单旋
void RotateR(Node* parent)
{
//记录节点信息
Node* subL = parent->_left;
Node* subLR = subL->_right;
Node* parentP = parent->_parent;
//修改链接关系
parent->_left = subLR;
if (subLR)//避免为空节点的情况
subLR->_parent = parent;
subL->_right = parent;
parent->_parent = subL;
//讨论父节点的情况
if (parent == _root)
{
_root = subL;
subL->_parent = nullptr;
}
else
{
if (parentP->_left == parent)
{
parentP->_left = subL;
}
else
{
parentP->_right = subL;
}
subL->_parent = parentP;
}
//更新平衡因子
subL->_bf = parent->_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)//新增节点为subLR的左子树
{
subLR->_bf = 0;
parent->_bf = 1;
subL->_bf = 0;
}
else if (bf == 1)//新增节点为subRL的右子树
{
subL->_bf = -1;
parent->_bf = 0;
subLR->_bf = 0;
}
else if (bf == 0)//新增节点就是subRL
{
subLR->_bf = 0;
parent->_bf = 0;
subL->_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)//新增节点为subLR的左子树
{
subRL->_bf = 0;
parent->_bf = 0;
subR->_bf = 1;
}
else if (bf == 1)//新增节点为subLR的右子树
{
subRL->_bf = 0;
parent->_bf = -1;
subR->_bf = 0;
}
else if (bf == 0)//新增节点就是subLR
{
subRL->_bf = 0;
parent->_bf = 0;
subR->_bf = 0;
}
else //旋转之前就已经存在错误了
{
assert(false);
}
}
从视角上来看,当旋转相关结点成直线,则进行单旋;当旋转相关结点成折线,则进行双旋
旋转完成后,原pParent为根的子树个高度降低,已经平衡,不需要再向上更新
AVL树是在二叉搜索树的基础上加入了平衡性的限制
如果中序遍历可得到一个有序的序列,就说明为二叉搜索树
void _InOrder(Node* root)
{
if (root == nullptr)
return;
_InOrder(root->_left);
cout << root->_kv.first << " : " << root->_kv.second << endl;
_InOrder(root->_right);
}
每个结点子树高度差的绝对值不超过1(注意结点中如果没有平衡因子)以及结点的平衡因子是否计算正确
//验证pRoot是否为有效的AVL树
bool _IsAVLTree(Node* root)
{
//空树
if (root == nullptr)
return true;
//比较高度
int heightL = _Height(root->_left);
int heightR = _Height(root->_right);
//检查平衡因子是否有误
if (heightR - heightL != root->_bf)
{
cout << "平衡因子错误:" << root->_kv.first << endl;
return false;
}
return abs(heightR - heightL) < 2
&& _IsAVLTree(root->_left)
&& _IsAVLTree(root->_right);//递归检查左右子树
}
//高度
size_t _Height(Node* root)
{
//空节点
if (root == nullptr)
return 0;
size_t left = _Height(root->_left);
size_t right = _Height(root->_right);
return left > right ? left + 1 : right + 1;
}
如果需要一种查询高效且有序的数据结构,而且数据的个数为静态的(即不会改变),可以考虑AVL树,但一个结构经常修改,就不太适合