模拟实现AVL树插入操作
avl树
本文展示的是通过平衡因子控制高度的avl树。
平衡因子(balance factor简称bf)等于右子树高度-左子树高度,我们要控制树中的所有平衡因子都小于等于1。
结构
树中节点的成员如下
template<class K, class V>// k为键值
struct AVLTreeNode
{
// 本树使用三叉链可方便操作
AVLTreeNode<K, V>* _left;
AVLTreeNode<K, V>* _right;
AVLTreeNode<K, V>* _parent;
pair<K, V> _kv;
int _bf;
AVLTreeNode(const pair<K, V>& kv)
:_left(nullptr)
,_right(nullptr)
,_parent(nullptr)
,_kv(kv)
,_bf(0)
{}
};
插入
插入操作与搜索树类似,如下图
我们想把7插入,那么我们就会找到6的右节点,将7插入即可。不同点是,在avl树中,我们需要控制bf值,我们发现将7插入后,6的bf将成为1,5的bf值将变成2,此时5的bf值大于1,不符合avl树的规则,因此我们需要一定的操作来使avl树重新平衡,这个操作就叫旋转,我们接下来将详细解释旋转的做法。
旋转
左旋转
在刚刚的例子中我们发现根节点的bf值为2,且他的右节点的bf值为1,此时我们需要使用左旋转。这是一张抽象图,代表需要左旋转的情况。
具体操作是把subR的左子树给parent作为右子树,再把parent作为subR的左子树,如下图
左单旋代码
void RotateL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
Node* pParent = parent->_parent;
parent->_right = subRL;
if (subRL != nullptr)
{
subRL->_parent = parent;
}
subR->_left = parent;
parent->_parent = subR;
if (parent == _root)
{
_root = subR;
_root->_parent = nullptr;
}
else
{
subR->_parent = pParent;
if (pParent->_left == parent)
{
pParent->_left = subR;
}
else
{
pParent->_right = subR;
}
}
parent->_bf = subR->_bf = 0;
}
右旋转
当父节点的bf值为-2,且他的左节点的bf值为-1时即需要使用右旋转,如下图是需要右旋转的抽象图
右旋转的操作与左旋转向反,先把subL的右子树作为parent的左子树,再把parent作为subL的右子树即可,如下图
右旋转代码
void RotateR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
Node* pParent = parent->_parent;
parent->_left = subLR;
if (subLR != nullptr)
{
subLR->_parent = parent;
}
subL->_right = parent;
parent->_parent = subL;
if (parent == _root)
{
_root = subL;
_root->_parent = nullptr;
}
else
{
subL->_parent = pParent;
if (pParent->_left == parent)
{
pParent->_left = subL;
}
else
{
pParent->_right = subL;
}
}
subL->_bf = parent->_bf = 0;
}
右左双旋
在一些情况下以此单旋无法解决问题,比如下面这三种情况
这三种情况有一个共同点,父节点的bf值都是2,右节点的bf值都是-1,在这种情况下都需要使用右左双旋,即先对subR进行一次右旋,再对parent进行一次左旋,唯一需要考虑的是bf值的控制,这点在后面会详细介绍。
先从最简单的情况三开始,
我们发现情况三在右左双旋之后parent,subR,subRL的bf值都变成了0
情况一:
情况二:
右左双旋代码
void RotateRL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
int bf = subRL->_bf;
RotateR(subR);
RotateL(parent);
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 if (bf == 0)
{
parent->_bf = 0;
subR->_bf = 0;
subRL->_bf = 0;
}
}
左右双旋
在父节点的bf值为-2,父节点的左节点的bf值为1时就需要使用左右双旋,如下图所示的三种情况
左右双旋代码
void RotateLR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
int bf = subLR->_bf;
RotateL(subL);
RotateR(parent);
if (bf == -1)
{
subLR->_bf = 0;
subL->_bf = 0;
parent->_bf = 1;
}
else if (bf == 1)
{
subLR->_bf = 0;
subL->_bf = -1;
parent->_bf = 0;
}
else if (bf == 0)
{
subLR->_bf = 0;
subL->_bf = 0;
parent->_bf = 0;
}
}
insert代码
bool Insert(const pair<K, V>& kv)
{
Node* parent = nullptr, * cur = _root;
if (_root == nullptr)
{
_root = new Node(kv);
return true;
}
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);
cur->_parent = parent;
if (kv.first < parent->_kv.first)
{
parent->_left = cur;
}
else
{
parent->_right = cur;
}
while (parent)
{
if (cur == parent->_left)
{
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 && parent->_left->_bf == -1)
{
RotateR(parent);
}
else if (parent->_bf == 2 && parent->_right->_bf == 1)
{
RotateL(parent);
}
else if (parent->_bf == 2 && parent->_right->_bf == -1)
{
RotateRL(parent);
}
else if (parent->_bf == -2 && parent->_left->_bf == 1)
{
RotateLR(parent);
}
}
}
}
void RotateR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
Node* pParent = parent->_parent;
parent->_left = subLR;
if (subLR != nullptr)
{
subLR->_parent = parent;
}
subL->_right = parent;
parent->_parent = subL;
if (parent == _root)
{
_root = subL;
_root->_parent = nullptr;
}
else
{
subL->_parent = pParent;
if (pParent->_left == parent)
{
pParent->_left = subL;
}
else
{
pParent->_right = subL;
}
}
subL->_bf = parent->_bf = 0;
}
void RotateL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
Node* pParent = parent->_parent;
parent->_right = subRL;
if (subRL != nullptr)
{
subRL->_parent = parent;
}
subR->_left = parent;
parent->_parent = subR;
if (parent == _root)
{
_root = subR;
_root->_parent = nullptr;
}
else
{
subR->_parent = pParent;
if (pParent->_left == parent)
{
pParent->_left = subR;
}
else
{
pParent->_right = subR;
}
}
parent->_bf = subR->_bf = 0;
}
void RotateRL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
int bf = subRL->_bf;
RotateR(subR);
RotateL(parent);
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 if (bf == 0)
{
parent->_bf = 0;
subR->_bf = 0;
subRL->_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->_bf = 0;
subL->_bf = 0;
parent->_bf = 1;
}
else if (bf == 1)
{
subLR->_bf = 0;
subL->_bf = -1;
parent->_bf = 0;
}
else if (bf == 0)
{
subLR->_bf = 0;
subL->_bf = 0;
parent->_bf = 0;
}
}
private:
Node* _root;
};
插入操作和搜索树一样,从根节点开始,若插入值大于根节点就向右
这篇好文章是转载于:学新通技术网
- 版权申明: 本站部分内容来自互联网,仅供学习及演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,请提供相关证据及您的身份证明,我们将在收到邮件后48小时内删除。
- 本站站名: 学新通技术网
- 本文地址: /boutique/detail/tanhgggahk
-
photoshop保存的图片太大微信发不了怎么办
PHP中文网 06-15 -
《学习通》视频自动暂停处理方法
HelloWorld317 07-05 -
Android 11 保存文件到外部存储,并分享文件
Luke 10-12 -
word里面弄一个表格后上面的标题会跑到下面怎么办
PHP中文网 06-20 -
photoshop扩展功能面板显示灰色怎么办
PHP中文网 06-14 -
微信公众号没有声音提示怎么办
PHP中文网 03-31 -
excel下划线不显示怎么办
PHP中文网 06-23 -
excel打印预览压线压字怎么办
PHP中文网 06-22 -
TikTok加速器哪个好免费的TK加速器推荐
TK小达人 10-01 -
怎样阻止微信小程序自动打开
PHP中文网 06-13