介绍
红黑树（Red–black tree）是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型的用途是实现关联数组。它是复杂的，但它的操作有着良好的最坏情况运行时间，并且在实践中是高效的：它可以在O(log n) 时间内做查找，插入和删除，这里的n是树中元素的数目。红黑树相对于AVL树来说，牺牲了部分平衡性以换取插入/删除操作时少量的旋转操作，整体来说性能要优于AVL树。
性质
红黑树是每个节点都带有颜色属性的二叉查找树，颜色为红色或黑色。在二叉查找树强制一般要求以外，对于任何有效的红黑树我们增加了如下的额外要求：
- 节点是红色或黑色。
- 根是黑色。
- 所有叶子都是黑色（叶子是NIL节点）。
- 每个红色节点必须有两个黑色的子节点。（从每个叶子到根的所有路径上不能有两个连续的红色节点。）
- 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。
下面是一个具体的红黑树的图例：
红黑树
这些约束确保了红黑树的关键特性：从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。结果是这个树大致上是平衡的。因为操作比如插入、删除和查找某个值的最坏情况时间都要求与树的高度成比例，这个在高度上的理论上限允许红黑树在最坏情况下都是高效的，而不同于普通的二叉查找树。
要知道为什么这些性质确保了这个结果，注意到性质4导致了路径不能有两个毗连的红色节点就足够了。最短的可能路径都是黑色节点，最长的可能路径有交替的红色和黑色节点。因为根据性质5所有最长的路径都有相同数目的黑色节点，这就表明了没有路径能多于任何其他路径的两倍长。
在很多树数据结构的表示中，一个节点有可能只有一个子节点，而叶子节点包含数据。用这种范例表示红黑树是可能的，但是这会改变一些性质并使算法复杂。为此，本文中我们使用"nil叶子"或"空（null）叶子"，如上图所示，它不包含数据而只充当树在此结束的指示。这些节点在绘图中经常被省略，导致了这些树好像同上述原则相矛盾，而实际上不是这样。与此有关的结论是所有节点都有两个子节点，尽管其中的一个或两个可能是空叶子。
查找操作
因为每一个红黑树也是一个特化的二叉查找树，因此红黑树上的只读操作与普通二叉查找树上的只读操作相同。然而，在红黑树上进行插入操作和删除操作会导致不再匹配红黑树的性质。恢复红黑树的性质需要少量O(log n)的颜色变更和不超过三次树旋转（对于插入操作是两次）。虽然插入和删除很复杂，但操作时间仍可以保持为O(log n)次。
插入操作
我们首先以二叉查找树的方法增加新节点并标记它为红色。（如果设为黑色，就会导致根到叶子的路径上有一条路上，多一个额外的黑节点，这个是很难调整的。但是设为红色节点后，可能会导致出现两个连续红色节点的冲突，那么可以通过颜色调换和树旋转来调整。）下面要进行什么操作取决于其他临近节点的颜色。我们将使用术语叔父节点来指一个节点的父节点的兄弟节点。注意：
- 性质1和性质3总是保持着，不会被破坏。
- 性质4只在增加红色节点、重绘黑色节点为红色，或做旋转时可能被破坏。
- 性质5只在增加黑色节点、重绘红色节点为黑色，或做旋转时可能被破坏。
将要插入的节点标为N，N的父节点标为P，N的祖父节点标为G，N的叔父节点标为U。
通过下列函数，可以找到一个节点的叔父和祖父节点：
node* grandparent(node *n){
return n->parent->parent;
}
node* uncle(node *n){
if(n->parent == grandparent(n)->left)
return grandparent (n)->right;
else
return grandparent (n)->left;
}
case1: 新节点N位于树的根上，没有父节点。在这种情形下，我们把它重绘为黑色以满足性质2。因为它在每个路径上对黑节点数目增加一，性质5匹配。
void insert_case1(node *n){
if(n->parent == NULL)
n->color = BLACK;
else
insert_case2 (n);
}
case2: 新节点的父节点P是黑色，所以性质4没有失效（新节点是红色的）。在这种情形下，树仍是有效的。性质5也未受到威胁。
void insert_case2(node *n){
if(n->parent->color == BLACK)
return; /* 树仍旧有效*/
else
insert_case3 (n);
}
case3: 如果父节点P和叔父节点U二者都是红色，（此时新插入节点N做为P的左子节点或右子节点都属于情形3，下图仅显示N做为P左子的情形）则我们可以将它们两个重绘为黑色并重绘祖父节点G为红色（用来保持性质5）。现在我们的新节点N有了一个黑色的父节点P。因为通过父节点P或叔父节点U的任何路径都必定通过祖父节点G，在这些路径上的黑节点数目没有改变。但是，红色的祖父节点G可能是根节点，这就违反了性质2，也有可能祖父节点G的父节点是红色的，这就违反了性质4。为了解决这个问题，我们在祖父节点G上递归地进行情形1的整个过程。（把G当成是新加入的节点进行各种情形的检查）
Red-black_tree_insert_case_3
void insert_case3(node *n){
if(uncle(n) != NULL && uncle (n)->color == RED) {
n->parent->color = BLACK;
uncle (n)->color = BLACK;
grandparent (n)->color = RED;
insert_case1(grandparent(n));
}
else
insert_case4 (n);
}
case4: 父节点P是红色而叔父节点U是黑色或缺少，并且新节点N是其父节点P的右子节点而父节点P又是其父节点的左子节点。在这种情形下，我们进行一次左旋转调换新节点和其父节点的角色或者新节点N是其父节点P的左子节点而父节点P又是其父节点的右子节点。在这种情形下，我们进行一次右旋转调换新节点和其父节点的角色;接着，我们按情形5处理以前的父节点P以解决仍然失效的性质4。但由于这两个节点都是红色的，所以性质5仍有效。
Red-black_tree_insert_case_4
void insert_case4(node *n){
if(n == n->parent->right && n->parent == grandparent(n)->left) {
rotate_left(n->parent);
n = n->left;
} else if(n == n->parent->left && n->parent == grandparent(n)->right) {
rotate_right(n->parent);
n = n->right;
}
insert_case5 (n);
}
case5: 父节点P是红色而叔父节点U是黑色或缺少，新节点N是其父节点的左子节点，而父节点P又是其父节点G的左子节点。在这种情形下，我们进行针对祖父节点G的一次右旋转或者新节点N是其父节点的右子节点，而父节点P又是其父节点G的右子节点。在这种情形下，我们进行针对祖父节点G的一次左旋转；在旋转产生的树中，以前的父节点P现在是新节点N和以前的祖父节点G的父节点。我们切换以前的父节点P和祖父节点G的颜色，结果的树满足性质4。性质5也仍然保持满足。
Red-black_tree_insert_case_5
void insert_case5(node *n){
/*changed P and G color */
n->parent->color = BLACK;
grandparent (n)->color = RED;
if(n == n->parent->left && n->parent == grandparent(n)->left) {
rotate_right(grandparent(n));
} else {
/* Here, n == n->parent->right && n->parent == grandparent (n)->right */
rotate_left(grandparent(n));
}
}
删除操作
对于二叉查找树，在删除带有两个非叶子儿子的节点的时候，我们要么找到它左子树中的最大元素、要么找到它右子树中的最小元素，并把它的值转移到要删除的节点中。我们接着删除我们从中复制出值的那个节点，它必定有少于两个非叶子的儿子。因为只是复制了一个值，不违反任何性质，这就把问题简化为如何删除最多有一个儿子的节点的问题。它不关心这个节点是最初要删除的节点还是我们从中复制出值的那个节点。
如果我们删除一个红色节点，它的父亲和儿子一定是黑色的。所以我们可以简单的用它的黑色儿子替换它，并不会破坏性质3和性质4。通过被删除节点的所有路径只是少了一个红色节点，这样可以继续保证性质5。另一种简单情况是在被删除节点是黑色而它的儿子是红色的时候。如果只是去除这个黑色节点，用它的红色儿子顶替上来的话，会破坏性质5，但是如果我们重绘它的儿子为黑色，则曾经通过它的所有路径将通过它的黑色儿子，这样可以继续保持性质5。
需要进一步讨论的是在要删除的节点和它的儿子二者都是黑色的时候，这是一种复杂的情况（这种情况下该结点的两个儿子都是叶子结点，否则若其中一个儿子是黑色非叶子结点，另一个儿子是叶子结点，那么从该结点通过非叶子结点儿子的路径上的黑色结点数最小为2，而从该结点到另一个叶子结点儿子的路径上的黑色结点数为1，违反了性质5）。我们首先把要删除的节点替换为它的儿子。出于方便，称呼这个儿子为N（在新的位置上），称呼它的兄弟（它父亲的另一个儿子）为S。在下面的示意图中，我们还是使用P称呼N的父亲，SL称呼S的左儿子，SR称呼S的右儿子。我们将使用下述函数找到兄弟节点：
struct node *
sibling(struct node *n)
{
if(n == n->parent->left)
return n->parent->right;
else
return n->parent->left;
}
我们可以使用下列代码表示上述分析的概要步骤，这里的函数replace_node替换child到n在树中的位置。
void
delete_one_child(struct node *n)
{
/*
* Precondition: n has at most one non-null child.
*/
struct node *child = is_leaf(n->right)? n->left : n->right;
replace_node(n, child);
if(n->color == BLACK){
if(child->color == RED)
child->color = BLACK;
else
delete_case1 (child);
}
free (n);
}
如果N和它初始的父亲是黑色，则删除它的父亲导致通过N的路径都比不通过它的路径少了一个黑色节点。因为这违反了性质5，树需要被重新平衡。有几种情形需要考虑：
case1：删除节点之后N成为新的根。在这种情形下，我们就做完了。我们从所有路径去除了一个黑色节点，而新根是黑色的，所以性质都保持着。
void
delete_case1(struct node *n)
{
if(n->parent != NULL)
delete_case2 (n);
}
case2: S是红色，N是父节点P的左子树。在这种情形下我们在N的父亲上做左旋转，把红色兄弟转换成N的祖父，如果N是父节点P的右子树。在这种情形下我们在N的父亲上做右旋转，把红色兄弟转换成N的祖父，我们接着对调N的父亲和祖父的颜色。完成这两个操作后，尽管所有路径上黑色节点的数目没有改变，但现在N有了一个黑色的兄弟和一个红色的父亲，所以我们可以接下去按case4、case5或case6来处理。
注意：这里的图中没有显示出来，N是删除了黑色节点后替换上来的子节点，所以这个过程中由P->X->N变成了P->N，实际上是少了一个黑色节点。
Red-black_tree_delete_case_2
void
delete_case2(struct node *n)
{
struct node *s = sibling (n);
if(s->color == RED){
n->parent->color = RED;
s->color = BLACK;
if(n == n->parent->left)
rotate_left(n->parent);
else
rotate_right(n->parent);
}
delete_case3 (n);
}
case3：N的父亲P、S和S的儿子都是黑色的。在这种情形下，我们简单的重绘S为红色。其结果是通过S的所有路径，它们就是以前不通过N的那些路径，都少了一个黑色节点。因为删除N的初始的父亲使通过N的所有路径少了一个黑色节点，这使事情都平衡了起来。但是，通过P的所有路径现在比不通过P的路径少了一个黑色节点，所以仍然违反性质5。要修正这个问题，我们要从情形1开始，在P上做重新平衡处理。
Red-black_tree_delete_case_3
void
delete_case3(struct node *n)
{
struct node *s = sibling (n);
if((n->parent->color == BLACK)&&
(s->color == BLACK)&&
(s->left->color == BLACK)&&
(s->right->color == BLACK)) {
s->color = RED;
delete_case1(n->parent);
} else
delete_case4 (n);
}
case4: S和S的儿子都是黑色，但是N的父亲是红色。在这种情形下，我们简单的交换N的兄弟和父亲的颜色。这不影响不通过N的路径的黑色节点的数目，但是它在通过N的路径上对黑色节点数目增加了一，添补了在这些路径上删除的黑色节点。
Red-black_tree_delete_case_4
void
delete_case4(struct node *n)
{
struct node *s = sibling (n);
if（(n->parent->color == RED)&&
(s->color == BLACK)&&
(s->left->color == BLACK)&&
(s->right->color == BLACK)) {
s->color = RED;
n->parent->color = BLACK;
} else
delete_case5 (n);
}
case5: S是黑色，S的左儿子是红色，S的右儿子是黑色，而N是它父亲的左儿子。在这种情形下我们在S上做右旋转，这样S的左儿子成为S的父亲和N的新兄弟。我们接着交换S和它的新父亲的颜色。所有路径仍有同样数目的黑色节点，但是现在N有了一个黑色兄弟，他的右儿子是红色的，所以我们进入了情形6。N和它的父亲都不受这个变换的影响。
Red-black_tree_delete_case_5
void
delete_case5(struct node *n)
{
struct node *s = sibling (n);
if（s->color == BLACK){ /* this if statement is trivial,
due to Case 2(even though Case two changed the sibling to a sibling's child,
the sibling's child can't be red, since no red parent can have a red child). */
// the following statements just force the red to be on the left of the left of the parent,
// or right of the right, so case six will rotate correctly.
if((n == n->parent->left)&&
(s->right->color == BLACK)&&
(s->left->color == RED)) { // this last test is trivial too due to cases 2-4.
s->color = RED;
s->left->color = BLACK;
rotate_right (s);
} else if((n == n->parent->right)&&
(s->left->color == BLACK)&&
(s->right->color == RED)) {// this last test is trivial too due to cases 2-4.
s->color = RED;
s->right->color = BLACK;
rotate_left (s);
}
}
delete_case6 (n);
}
case6: S是黑色，S的右儿子是红色，而N是它父亲的左儿子。在这种情形下我们在N的父亲P上做左旋转，这样S成为N的父亲（P）和S的右儿子的父亲。我们接着交换N的父亲和S的颜色，并使S的右儿子为黑色。子树在它的根上的仍是同样的颜色，所以性质3没有被违反。但是，N现在增加了一个黑色祖先：要么N的父亲变成黑色，要么它是黑色而S被增加为一个黑色祖父。所以，通过N的路径都增加了一个黑色节点。
此时，如果一个路径不通过N，则有两种可能性：
- 它通过N的新兄弟。那么它以前和现在都必定通过S和N的父亲，而它们只是交换了颜色。所以路径保持了同样数目的黑色节点。
- 它通过N的新叔父，S的右儿子。那么它以前通过S、S的父亲和S的右儿子，但是现在只通过S，它被假定为它以前的父亲的颜色，和S的右儿子，它被从红色改变为黑色。合成效果是这个路径通过了同样数目的黑色节点。
在任何情况下，在这些路径上的黑色节点数目都没有改变。所以我们恢复了性质4。在示意图中的白色节点可以是红色或黑色，但是在变换前后都必须指定相同的颜色。
Red-black_tree_delete_case_6
void
delete_case6(struct node *n)
{
struct node *s = sibling (n);
s->color = n->parent->color;
n->parent->color = BLACK;
if(n == n->parent->left){
s->right->color = BLACK;
rotate_left(n->parent);
} else {
s->left->color = BLACK;
rotate_right(n->parent);
}
}
python
class TreeNode(object):
def __init__(self, data, left=None, right=None, parent=None, color="RED"):
self.data = data
self.left = left
self.right = right
self.parent = parent
self.color = color
class RBTree(object):
def __init__(self):
self.root = None
self.size = 0
def find(self, key, node):
if not node:
return None
elif key < node.data:
return self.find(key, node.left)
elif key > node.data:
return self.find(key, node.right)
else:
return node
def findMin(self, node):
"""
找到以 node 节点为根节点的树的最小值节点 并返回
:param node: 以该节点为根节点的树
:return: 最小值节点
"""
temp_node = node
while temp_node.left:
temp_node = temp_node.left
return temp_node
def findMax(self, node):
"""
找到以 node 节点为根节点的树的最大值节点 并返回
:param node: 以该节点为根节点的树
:return: 最大值节点
"""
temp_node = node
while temp_node.right:
temp_node = temp_node.right
return temp_node
def transplant(self, tree, node_u, node_v):
"""
用 v 替换 u
:param tree: 树的根节点
:param node_u: 将被替换的节点
:param node_v: 替换后的节点
:return: None
"""
if not node_u.parent:
tree.root = node_v
elif node_u == node_u.parent.left:
node_u.parent.left = node_v
elif node_u == node_u.parent.right:
node_u.parent.right = node_v
# 加一下为空的判断
if node_v:
node_v.parent = node_u.parent
def left_rotate(self, node):
'''
* 左旋示意图：对节点x进行左旋
* parent parent
* / /
* node right
* / \ / \
* ln right -----> node ry
* / \ / \
* ly ry ln ly
* 左旋做了三件事：
* 1. 将right的左子节点ly赋给node的右子节点,并将node赋给right左子节点ly的父节点(ly非空时)
* 2. 将right的左子节点设为node，将node的父节点设为right
* 3. 将node的父节点parent(非空时)赋给right的父节点，同时更新parent的子节点为right(左或右)
:param node: 要左旋的节点
:return:
'''
parent = node.parent
right = node.right
# 把右子子点的左子点节 赋给右节点 步骤1
node.right = right.left
if node.right:
node.right.parent = node
# 把 node 变成基右子节点的左子节点 步骤2
right.left = node
node.parent = right
# 右子节点的你节点更并行为原来节点的父节点。 步骤3
right.parent = parent
if not parent:
self.root = right
else:
if parent.left == node:
parent.left = right
else:
parent.right = right
def right_rotate(self, node):
'''
* 左旋示意图：对节点y进行右旋
* parent parent
* / /
* node left
* / \ / \
* left ry -----> ln node
* / \ / \
* ln rn rn ry
* 右旋做了三件事：
* 1. 将left的右子节点rn赋给node的左子节点,并将node赋给rn右子节点的父节点(left右子节点非空时)
* 2. 将left的右子节点设为node，将node的父节点设为left
* 3. 将node的父节点parent(非空时)赋给left的父节点，同时更新parent的子节点为left(左或右)
:param node:
:return:
'''
parent = node.parent
left = node.left
# 处理步骤1
node.left = left.right
if node.left:
node.left.parent = node
# 处理步骤2
left.right = node
node.parent = left
# 处理步骤3
left.parent = parent
if not parent:
self.root = left
else:
if parent.left == node:
parent.left = left
else:
parent.right = left
def insert(self, node):
# 找到最接近的节点
temp_root = self.root
temp_node = None
while temp_root:
temp_node = temp_root
if node.data == temp_node.data:
return False
elif node.data > temp_node.data:
temp_root = temp_root.right
else:
temp_root = temp_root.left
# 在相应位置插入节点
if not temp_node:
# insert_case1
self.root = node
node.color = "BLACK"
elif node.data < temp_node.data:
temp_node.left = node
node.parent = temp_node
else:
temp_node.right = node
node.parent = temp_node
# 调整树
self.insert_fixup(node)
def insert_fixup(self, node):
if node.value == self.root.data:
return
# 为什么是这个终止条件？
# 因为如果不是这个终止条件那就不需要调整
while node.parent and node.parent.color == "RED":
# 只要进入循环则必有祖父节点 否则父节点为根节点 根节点颜色为黑色 不会进入循环
if node.parent == node.parent.parent.left:
node_uncle = node.parent.parent.right
# 1. 没有叔叔节点 若此节点为父节点的右子 则先左旋再右旋 否则直接右旋
# 2. 有叔叔节点 叔叔节点颜色为黑色
# 3. 有叔叔节点 叔叔节点颜色为红色 父节点颜色置黑 叔叔节点颜色置黑 祖父节点颜色置红 continue
# 注: 1 2 情况可以合为一起讨论 父节点为祖父节点右子情况相同 只需要改指针指向即可
if node_uncle and node_uncle.color == "RED":
# insert_case3
node.parent.color = "BLACK"
node_uncle.color = "BLACK"
node.parent.parent.color = "RED"
node = node.parent.parent
continue
elif node == node.parent.right:
# insert_case4
self.left_rotate(node.parent)
node = node.left
# insert_case5
node.parent.color = "BLACK"
node.parent.parent.color = "RED"
self.right_rotate(node.parent.parent)
return
# 对称情况
elif node.parent == node.parent.parent.right:
node_uncle = node.parent.parent.left
if node_uncle and node_uncle.color == "RED":
node.parent.color = "BLACK"
node_uncle.color = "BLACK"
node.parent.parent.color = "RED"
node = node.parent.parent
continue
elif node == node.parent.left:
self.right_rotate(node)
node = node.right
node.parent.color = "BLACK"
node.parent.parent.color = "RED"
self.left_rotate(node.parent.parent)
return
# 最后记得把根节点的颜色改为黑色 保证红黑树特性
self.root.color = "BLACK"
def delete(self, node):
# 找到以该节点为根节点的右子树的最小节点
node_color = node.color
if not node.left:
temp_node = node.right
self.transplant(node, node.right)
elif not node.right:
temp_node = node.left
self.transplant(node, node.left)
else:
# 最麻烦的一种情况 既有左子 又有右子 找到右子中最小的做替换 类似于二分查找树的删除
node_min = self.findMin(node.right)
node_color = node_min.color
temp_node = node_min.right
if node_min.parent != node:
self.transplant(node_min, node_min.right)
node_min.right = node.right
node_min.right.p = node_min
self.transplant(node, node_min)
node_min.left = node.left
node_min.left.parent = node_min
node_min.color = node.color
# 当删除的节点的颜色为黑色时 需要调整红黑树
if node_color == "BLACK":
self.delete_fixup(temp_node)
def delete_fixup(self, node):
# 实现过程还需要理解 比如为什么要删除 为什么是那几种情况
while node != self.root and node.color == "BLACK":
if node == node.parent.left:
node_brother = node.parent.right
if node_brother.color == "RED":
# delete_case2
node_brother.color = "BLACK"
node.parent.color = "RED"
self.left_rotate(node.parent)
node_brother = node.parent.right
if (not node_brother.left or node_brother.left.color == "BLACK") and \
(not node_brother.right or node_brother.right.color == "BLACK"):
# delete_case3
node_brother.color = "RED"
node = node.parent
else:
if not node_brother.right or node_brother.right.color == "BLACK":
# delete_case5
node_brother.color = "RED"
node_brother.left.color = "BLACK"
self.right_rotate(node_brother)
node_brother = node.parent.right
# delete_case6
node_brother.color = node.parent.color
node.parent.color = "BLACK"
node_brother.right.color = "BLACK"
self.left_rotate(node.parent)
node = self.root
break
else:
node_brother = node.parent.left
if node_brother.color == "RED":
node_brother.color = "BLACK"
node.parent.color = "RED"
self.left_rotate(node.parent)
node_brother = node.parent.right
if (not node_brother.left or node_brother.left.color == "BLACK") and \
(not node_brother.right or node_brother.right.color == "BLACK"):
node_brother.color = "RED"
node = node.parent
else:
if not node_brother.left or node_brother.left.color == "BLACK":
node_brother.color = "RED"
node_brother.right.color = "BLACK"
self.left_rotate(node_brother)
node_brother = node.parent.left
node_brother.color = node.parent.color
node.parent.color = "BLACK"
node_brother.left.color = "BLACK"
self.right_rotate(node.parent)
node = self.root
break
node.color = "BLACK"
网友评论