目录
一、定义与起源
二、特点与规则
五大规则：
左旋（Left Rotate）：
右旋（Right Rotate）：
变色
三、操作与性能
四、应用场景
红黑树（Red Black Tree）是一种自平衡的二叉查找树，即在插入和删除节点后，通过特定的旋转和重新着色操作来保持树的平衡，以确保查找、插入和删除操作的高效性。以下是对红黑树的详细解释：
一、定义与起源
- 红黑树是在计算机科学中用到的一种数据结构，典型的用途是实现关联数组，如C++中的map和set容器。
- 它是在1972年由Rudolf Bayer发明的，当时被称为平衡二叉B树（symmetric binary B-trees）。
- 在1978年，Leo J. Guibas和Robert Sedgewick将其修改为如今的“红黑树”。
二、特点与规则
- 红黑树的每个节点都带有颜色属性，颜色为红色或黑色。
-
五大规则：
- 每个节点要么是红色的，要么是黑色的。
- 根节点必须是黑色的。
- 所有叶子节点（NIL节点，即空节点）都是黑色的。这里的叶子节点通常指的是树的最底层节点，它们被视为黑色的空节点。
- 每个红色节点的两个子节点都是黑色的，即红色节点不能有红色的子节点。
- 从任一节点到其每个叶子节点的所有路径都包含相同数目的黑色节点，这确保了最长路径不会超过最短路径的两倍长。
-
左旋（Left Rotate）：
- 左旋是将一个节点以其右孩子为轴进行顺时针旋转的操作。
- 旋转后，原右孩子成为新的根节点，原节点成为新根节点的左孩子，原右孩子的左孩子（如果有）成为原节点的右孩子。
-
右旋（Right Rotate）：
- 右旋是将一个节点以其左孩子为轴进行逆时针旋转的操作。
- 旋转后，原左孩子成为新的根节点，原节点成为新根节点的右孩子，原左孩子的右孩子（如果有）成为原节点的左孩子。
-
变色
-
着色规则：
- 新插入的节点默认被着色为红色。
- 在插入或删除节点后，如果违反了红黑树的规则（如红色节点不能有红色子节点、从任一节点到其每个叶子节点的所有路径都包含相同数目的黑色节点等），则需要进行重新着色操作。
-
着色调整：
- 如果旋转操作无法解决问题，红黑树可能会对节点进行重新着色。
- 重新着色操作需要确保不会违反红黑树的规则。
-
三、操作与性能
- 查找操作：与普通的二叉查找树相同，通过比较关键字在树中进行查找。
- 插入操作：首先按照二叉查找树的插入逻辑进行新节点的插入，然后将其着色为红色。如果插入后违反了红黑树的规则，则需要进行旋转和重新着色操作来恢复平衡。
- 删除操作：删除节点后，同样需要检查是否违反了红黑树的规则，并进行相应的调整。
- 性能：红黑树可以在O(log n)时间内完成查找、插入和删除操作，其中n是树中元素的数目。
四、应用场景
- 红黑树常用于实现关联数组、有序集合等数据结构。
- 在数据库、操作系统、编译器等领域也有广泛的应用。
