查看“树：红黑树”的源代码

[[category:数据结构]]

== 关于 ==
红黑树（Red Black Tree） 是一种含有红黑结点并能'''自平衡二叉查找树'''。
* 它可以在“O(log n)”时间内做查找，插入和删除（n 是树中元素的数目）。


Question：
# 红黑树是平衡二叉树吗？
#: 红黑树是一种特化的 AVL树，但其并非严格的 AVL树，其平衡因子的绝对值可能大于 1。但对其进行平衡的代价较低，其平均统计性能要强于 AVL 。
# 红黑树的应用？
#: 红黑树的应用十分广泛，如下：
## JDK 的集合类 TreeMap 和 TreeSet 底层实现，Java8 中 HashMap 的实现。
## Linux 的进程管理、内存管理，设备驱动及虚拟内存跟踪等一系列场景中。
## 一些数据库的索引实现等。

== 定义和性质 ==
# 每个节点要么是黑色，要么是红色。
# 根节点是黑色。
# 每个叶子节点（NIL）是黑色。
# '''每个红色结点的两个子结点一定都是黑色'''。【？】
#* 从每个叶子到根的所有路径上不能有两个连续的红色节点。
# '''任意一结点到每个叶子结点的路径都包含数量相同的黑结点'''。【？？？】
#* 如果一个结点存在黑子结点，那么该结点肯定有两个子结点。【所以，不存在只有一个叶子节点的节点？？？（因为叶子节点为黑色）】

这些规则限制保证了红黑树的自平衡。保证了红黑树的关键性质: '''从根到叶子的最长的可能路径不多于最短的可能路径的两倍长'''。【？？？】


典型的红黑树，如图：
: [[File:典型的红黑树.jpg|700px]]

== 自平衡 ==
红黑树总是通过'''旋转'''和'''变色'''达到自平衡。
* 旋转，包括“左旋”、“右旋”，与平衡二叉树同理。

== 操作 ==
在进行“插入”和“删除”等可能会破坏树的平衡的操作时，需要进行自平衡以到平衡状态。
* “读取”操作与排序二叉树同理，不会对树结构造成破坏，所以不需要进行自平衡。
【红黑树的插入、删除包含很多种情况，每种情况有不同的处理方式，较为复杂（4种插入case和5种删除case）】

=== 插入 ===
插入操作包括两部分工作：
# 查找插入的位置；
# 插入后自平衡。
查找插入的父结点很简单，跟查找操作区别不大。重点在于自平衡。


'''插入的节点都是红色'''。原因如下：
# 如果插入结点是红色：在父结点（如果存在）为黑色结点时，红黑树的黑色平衡没被破坏，不需要做自平衡操作。而在父结点（如果存在）为红色结点时，才需要自平衡。
# 如果插入结点是黑色：那么插入位置所在的子树黑色结点总是多 1，必须做自平衡。


所有插入情景：
:[[File:红黑树插入操作结点的叫法约定.png|400px]]
:[[File:红黑树插入情景.png|1000px]]
如上，情景1、2和3的处理很简单，而情景4.2和情景4.3只是方向反转而已。所以难点并不多。

==== 标题文字 ====

=== 删除 ===