第一范文网 - 专业文章范例文档资料分享平台

算法导论 - 实验四 常见平衡树的实现与比较

来源:用户分享 时间:2025/10/8 22:11:01 本文由loading 分享 下载这篇文档手机版
说明:文章内容仅供预览,部分内容可能不全,需要完整文档或者需要复制内容,请下载word后使用。下载word有问题请添加微信号:xxxxxxx或QQ:xxxxxx 处理(尽可能给您提供完整文档),感谢您的支持与谅解。

情况5:当前节点颜色是黑色,兄弟节点是黑色,兄弟的左子是红色,右子是黑色。 解法:把兄弟结点染红,兄弟左子节点染黑,之后再在兄弟节点为支点解右旋, 之后重新进入算法。此是把当前的情况转化为情况6,而性质5得以保持。 5.变化前:

5.变化后:

情况6:当前节点颜色是黑色,它的兄弟节点是黑色,但是兄弟节点的右子是红色,兄弟节点左子的颜色任意。

解法:把兄弟节点染成当前节点父节点的颜色,把当前节点父节点染成黑色,兄弟节点右子染成黑色,

之后以当前节点的父节点为支点进行左旋,此时算法结束,红黑树所有性质调整正确。 6.变化前:

6.变化后:

c) 平衡二叉树插入、删除操作的具体实现

i.

插入操作各种可能的情况 1. LL的情况:

由于在A的左孩子B的左子树上插入结点F,使A的平衡因子由1增至2而失去平衡。故需进行一次顺时针旋转操作。 即将A的左孩子B向右上旋转代替A作为根结点,A向右下旋转成为B的右子树的根结点。而原来B的右子树则变成A的左子树。

2. LR情况:

由于在A的左孩子B的右子数上插入结点F,使A的平衡因子由1增至2而失去平衡。故需进行两次旋转操作(先逆时针,后顺时针)。即先将A结点的左孩子B的右子树的根结点D向左上旋转提升到B结点的位置,然后再把该D结点向右上旋转提升到A结点的位置。即先使之成为LL型,再按LL型处理。

算法导论 - 实验四 常见平衡树的实现与比较.doc 将本文的Word文档下载到电脑,方便复制、编辑、收藏和打印
本文链接:https://www.diyifanwen.net/c2x43d3azhm83uyx9778t_3.html(转载请注明文章来源)
热门推荐
Copyright © 2012-2023 第一范文网 版权所有 免责声明 | 联系我们
声明 :本网站尊重并保护知识产权,根据《信息网络传播权保护条例》,如果我们转载的作品侵犯了您的权利,请在一个月内通知我们,我们会及时删除。
客服QQ:xxxxxx 邮箱:xxxxxx@qq.com
渝ICP备2023013149号
Top