红黑树原理讲解

 我来答
科创17
2022-06-23 · TA获得超过5903个赞
知道小有建树答主
回答量:2846
采纳率:100%
帮助的人:175万
展开全部

性质1: 每个节点要么是 黑色 ,要么是 红色 。
性质2: 根节点是 黑色
性质3: 每个叶子节点(NIL)是黑色。
性质4: 每个 红色 节点的两个子节点一定都是 黑色
性质5: 任意一个节点到每个叶子节点的路径都包含 数量相同 黑节点 。俗称: 黑高 !
从性质5又可以推出:
性质5.1: 如果一个节点存在黑子节点,那么该结点肯定有两个子节点。

插入操作包括两部分工作:

注意: 插入结点,必须为 红色 ,理由很简单,红色在父节点(如果存在)为黑色节点时,红黑树的黑色平衡没被破坏,不需要做自平衡操作。如果插入结点是黑色,那么插入位置所在的子树黑色结点总是1,必须做自平衡。

最简单的一种情景,直接把插入结点作为根结点就行
注意: 根据红黑树性质2: 根结点是黑色。还需要把插入结点设为黑色。

处理: 更新当前结点的值,为插入结点的值

由于插入的结点是红色的,当插入结点的父结点为黑色时,并不会影响红黑树的平衡,直接插入即可,无需做自平衡。

再次回想红黑树的性质2: 根结点是黑色。如果插入结点的父结点为 红结点 ,那么该父结点不可能为根结点,所以插入结点总是存在祖父结点。这一点很重要,因为后序的旋转操作肯定需要祖父结点的参与。

依据红黑树 性质4可知,红色结点不能相连===>祖父结点肯定为黑结点
因为不可以同时存在两个相连的红结点。那么此时该插入子树的红黑层数的情况是:黑红红。显然最简单的处理方式是把其改为: 红黑红
处理:
1.将P和U结点改为黑色
2.将PP改为红色
3.将PP设置为当前结点,进行后序处理

注意: 单纯从插入前来看,叔叔结点非红即空(NIL结点),否则的话破坏了红黑树性质5,此路径比其它路径多一个黑色结点。

处理:

处理:

该情景对应情景4.2,只是方向反转,直接看图

处理:

处理:

已赞过 已踩过<
你对这个回答的评价是?
评论 收起
DFRobot
2024-11-10 广告
图形化编程是一种直观的编程方式,它通过拖拽图形化的编程积木来构建程序,降低了编程的学习门槛。在上海智位机器人股份有限公司,我们致力于将图形化编程应用于机器人教育等领域,使学习者能够以更加轻松、有趣的方式掌握编程技能。我们的图形化编程平台界面... 点击进入详情页
本回答由DFRobot提供
推荐律师服务: 若未解决您的问题,请您详细描述您的问题,通过百度律临进行免费专业咨询

为你推荐:

下载百度知道APP,抢鲜体验
使用百度知道APP,立即抢鲜体验。你的手机镜头里或许有别人想知道的答案。
扫描二维码下载
×

类别

我们会通过消息、邮箱等方式尽快将举报结果通知您。

说明

0/200

提交
取消

辅 助

模 式