数据结构与算法 —— 红黑树
一、定义
- 根节点是黑色的。
- 叶子节点是空的且是黑色的。
- 任何相邻的节点不能都为红色。
- 任意节点到其每个叶子节点的路径上,黑色的节点的数量相同。
二、性质
红黑树解决了 AVL 树增、删时耗时过大的问题。
因为,定义中 3 和 4 使得红黑树的根节点到叶子节点的最长的可能路径不多于最短的可能路径的两倍长,导致该树是大致平衡的树,所以对于增、删的操作没有那么的严格。
三、时间复杂度
增、删、查的时间复杂度的平均和最坏都维持在O(logn),推导过程如下链接。
https://mp.****.net/postedit/103172135
四、源码
相关代码参考 linux 内核中红黑树的实现。
五、树的演化
六、拓展
1、根节点为什么必须是黑色的?
主要还是因为性质 3 和 4 。假设树只有两个节点(5)和(2),并且根节点设置为红色且子节点不能为红色,那么红黑树如下所示:
尴尬,不满足性质 4 。所以需要旋转,使其满足。结果如下所示:
既然如此,可以直接规定根节点必须为黑色。
(SAW:Game Over!)