yu766588220
花公子丶
2019-01-09 15:04

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

10
  • 神经网络
  • 搜索引擎
  • 开发语言

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

图片说明

  • 点赞
  • 回答
  • 收藏
  • 复制链接分享

1条回答