红黑树是树的数据结构中最为重要的一种。Java的容器TreeSet、TreeMap均使用红黑树实现。JDK1.8中HashMap中也加入了红黑树。C++ STL中的map和set同样使用红黑树实现。
红黑树保证在O(logN)的时间内完成查找、插入和删除操作。
定义
红黑树是每个节点都带有颜色属性的平衡二叉查找树 ,颜色为红色或黑色。除了二叉查找树一般要求以外,对于任何有效的红黑树我们增加了如下的额外要求:
(1)节点是要么红色或要么是黑色。
(2)根一定是黑色节点。
(3)每个叶子节点都带有两个空的黑色节点(称之为NIL节点,它又被称为黑哨兵)。
(4)每个红色节点的两个子节点都是黑色(或者说从每个叶子到根的所有路径上不能有两个连续的红色节点)。
(5)从任一节点到它所能到达得叶子节点的所有简单路径都包含相同数目的黑色节点。
例如:图示的一棵红黑树:
在上图中,因为通常不需要,我们隐去了一些节点,而实际上根据红黑树的定义第三点,每个子节点有两个空的黑色节点。下面为完整的节点图。
课程介绍
课程目录
往期学员作品
用户评论
课程介绍
课程目录
往期学员作品
用户评论
你将获得
- 红黑树的算法
教学服务
录播课程
讲师介绍
课程详情
温馨提示
- 请勿私下交易请勿在平台外交易。与机构和老师私下交易造成的任何损失及纠纷,腾讯课堂不承担任何责任
- 听课说明
1、电脑:访问腾讯课堂官网 ke.qq.com 查看我的课表或下载win/mac客户端听课
2、手机/平板:下载腾讯课堂APP, 进入学习页面听课