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

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

图片说明

1个回答

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

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
立即提问

相似问题

0
在单链表中统计某区域内的元素,将获得元素插入新单链表,并打印新链表元素在原链表中的序号
1
把两个有序排列的单向整数链表合并成一个有序排列的的整数链表?
0
链表二叉树建树怎么建树
2
Java1.8中HashMap扩容的特殊情况?
2
Java语言编写程序一个链表,并且计算链表上所有数的和
1
重赏求助,用java eclipse,分别用二叉链表、三叉链表为成员方法,查找二叉树中某节点的父节点?
1
数据结构java实验四验证教材中树结构的基本操作,设计实现指定操作的算法,并做算法分析。 以下各题二叉树的存储结构是二叉链表表示,方法声明如下: 二叉树的二叉链表结点类:
1
如何用C++创建一个可以存入小数的链表?
2
编写一个函数,实现将一个带头结点的单向链表数据逆置,代码怎么写呀?
1
将两个递增的双向链表合并问题
1
采用用户输入元素并基于前序遍历的方式创建一个存储人名的二叉链表树包含7个节点,用户输入两个人的姓名,比较这两个人的子孙谁多
1
【C语言-链表】请问怎么判断链表已经被销毁?
2
这是一个关于数据结构链表的相关问题
0
Java语言设计实现一个链表的数据结构,不要使用现有的库的代码,并且插入5个数字再输出
0
大佬们为什么我的链表只能删除开头,删除不了中间?
2
这是一个关于链表结点的指针问题
1
这是一个关于数据结构的链表问题
2
这是一个关于链表的取值问题
1
C#单链表添加元素时局部变量为什么会影响整个链表?
1
如何理解链表中指针和节点的意义