花公子丶 2019-01-09 15:04 采纳率: 50%
浏览 1483
已结题

红黑树最坏情况为何不是退变为链表的情况?

红黑树性质:
1、每个节点或为红色或为黑色
2、根节点为黑色
3、叶子节点为黑色
4、如果一个节点为红色,则其子节点为黑色
5、对每个节点,从该节点到其所有后代叶节点的简单路径上,均包含相同数目的黑色节点
所以下图中的这个链表应该符合红黑树的这五个性质。如果红黑树经过插入,删除等一系列操作之后,退变为下图,那不就意义不大了?还是说下图这个不属于红黑树(为了让图更清楚,叶子节点nil省略)

图片说明

  • 写回答

1条回答

  • Liplus1 2019-01-09 21:09
    关注

    红黑树叶子结点的定义是nil结点,nil结点没有数据,每个数据结点的子结点如果少于两个都用nil填满,也就是上图1-4都有另一个nil子结点,n有两个nil子结点,规则5说的到所有叶子的距离,不是到最靠下的数据结点的距离,而是到所有nil结点的距离。

    评论

报告相同问题?

悬赏问题

  • ¥15 seatunnel-web使用SQL组件时候后台报错,无法找到表格
  • ¥15 fpga自动售货机数码管(相关搜索:数字时钟)
  • ¥15 用前端向数据库插入数据,通过debug发现数据能走到后端,但是放行之后就会提示错误
  • ¥30 3天&7天&&15天&销量如何统计同一行
  • ¥30 帮我写一段可以读取LD2450数据并计算距离的Arduino代码
  • ¥15 C#调用python代码(python带有库)
  • ¥15 飞机曲面部件如机翼,壁板等具体的孔位模型
  • ¥15 vs2019中数据导出问题
  • ¥20 云服务Linux系统TCP-MSS值修改?
  • ¥20 关于#单片机#的问题:项目:使用模拟iic与ov2640通讯环境:F407问题:读取的ID号总是0xff,自己调了调发现在读从机数据时,SDA线上并未有信号变化(语言-c语言)