{{ selected_gold.title }}
树(Tree)
树是计算机世界里常用的数据结构，它类似于现实世界里的树，具有根节点和孩子节点。计算机里的目录树就采用了树状结构，一个目录里可能包含文件，也可能包含子目录。这种类型的数据结构有很多种，比如二叉树，红黑树，B 树，它们都是树类型，只不过做了一些限制。比如，二叉树规定了父亲节点最多允许拥有2个孩子节点。
- 定义
- 实现和操作
- 空间复杂度和时间复杂度
定义
In computer science, a binary tree is a tree data structure in which each node has at most two children, which are referred to as the left child and the right child. A recursive definition using just set theory notions is that a (non-empty) binary tree is a tuple (L, S, R), where L and R are binary trees or the empty set and S is a singleton set containing the root.[1] Some authors allow the binary tree to be the empty set as well.[2]
从以上定义可知二叉树是特殊的树，每个节点最多有2个孩子节点，分别是左孩子和右孩子，孩子节点又遵循着二叉树的定义，没有孩子的节点叫叶子节点，如下图所示:
通过上图可知，二叉树有以下特性类型:
- 能够把数据对半分，也就是说n个数据可以分成两份(n-1)/2和1个父节点，其中左子树包含(n-1)/2个节点，右子树包含另外的(n-1)/2个节点
- 每一层最多有2^(h-1)个节点，其中h是节点所在的层高，从0开始计算，比如第0层只存在一个根结点，第1层最多有2个节点
然而，在现实世界中，我们需要为二叉树添加一些约束，使它拥有更多的特性，进而能够更加高效地查找或插入数据。
红黑树就是一种有序的二叉树，也就是说，左子树上所有节点的值比父节点的值小，而右子树上所有节点的值比父节点大。这种特性使得查找一个元素时，可以直接排除一半元素，从而大大降低了查找时间。
另外，红黑树近似一颗完全二叉树，完全二叉树的定义是指:除了最下面一层，其它层的节点数一定是2^(h-1)，而且每层的节点必须从左到右增加，这种特性使得整颗树从横向平铺开，树的高度变得更矮，进而继续降低查找时间。
实际上一颗完全二叉树的高度是log(n)，底数为2，试着想一想，如果有一颗红黑树，包含了1000000000个节点，从中查找一个元素，最多会查找1000次。本质上这种思想就是二分查找，只不过它是基于红黑树来实现的。
然而，红黑树存在其它问题。比如，它会占用多余的空间(节点的定义必须包含指向孩子的信息)。插入一个新的元素，你需要调整该树的平衡性，也就是把左子树和右子树的高度差维持在2之内，它的时间复杂度是log(n)。
一般情况下，你经常会用到有序且平衡的二叉树，因为它具有较好的查询性能。具有这类特性的二叉树有红黑树。
实现和操作
一般情况下，我们会实现一个近似平衡的有序二叉树，因为有序和平衡能够保持高效的查询性能。实现近似平衡的有序二叉树有2种AVL树和红黑树，前者比后者更加平衡，但是节点的插入和删除操作会涉及更多的旋转操作。因此，如果你的插入和删除操作很少，而查询操作很频繁，那么应该选择AVL树；如果你会频繁插入和删除节点，并需要尽可能地保持树的平衡性，那么你应该选择红黑树。无论是红黑树还是AVL树，它们往往会提供以下操作：
- 查找树种的某一个节点（search）
- 往树里增加一个新的节点（insert）
- 从树里删除一个节点（remove）
接下来，我们以红黑树为例，分别介绍如何实现以上操作。以下是红黑树必须满足的特性：
- 每一个节点，要么是红色，要么是黑色
- 根节点必须是黑色
- 每一个NIL节点必须是黑色，而且不记录任何信息
- 如果一个节点是红色，那么它肯定有2个黑色的孩子节点或者有2个NIL节点
- 选择任何一个节点，从该节点到所有它的子孙叶子节点所生成的路径，每条路径上的黑色节点数量是相同的
下面这棵红黑树满足了以上所有特性：
- 根节点13是黑色
- NIL均是黑色
- 任意一个红色节点，它的孩子节点一定是黑色，比如红色节点8
- 任意选择一个节点，比如17，以它为起点，向下查找所有叶子节点，也就是上图的15、22、27节点，它们经过的黑色节点数是一样的
在之前的3个操作种，插入和删除操作会破坏红黑树的特性，因此，在做这两个操作的时候，需要恢复红黑树的特性。在恢复过程种需要使用到以下操作：
- 左旋：假设你需要对节点x做左旋操作，x节点会向左下方向下沉，而x节点的右边孩子y会上浮成为父亲节点，整个过程如下图所示：
- 右旋：假设你需要对节点y做右旋操作，y节点会向右下方向下沉，而y节点的左边孩子x会上浮成为父亲节点，整个过程如下图所示：
- 修改节点颜色：如果节点的颜色是红色，那么切换成黑色，反之亦然
通常，我们会使用以上操作，或者将其组合在一起，使得删除或移除节点之后，二叉树依然满足红黑树的特性。接下来让我们看看插入操作。
向红黑树中插入节点
为了向红黑树插入节点K，我们需要按照以下步骤：
- 按照BST的规程向红黑树中插入节点K
- 将节点K设置成红色
- 检查插入K节点之后，红黑树的特性是否满足，如果不满足，那么根据以下几种情况来调整
首先，让我们假设P是K的父亲节点，U是K的叔叔节点，S是K的兄弟节点，G是K的爷爷节点。接下来，让我们分析以下几种场景：
CASE 1：整棵树为空
如果整棵树为空，那么我们让K节点成为根节点，并将其颜色修改成黑色
CASE 2：节点P为黑色
如果节点P为黑色，那么说明此时插入的节点K，不会破坏红黑树的特性，因此无需调整。
CASE 3：节点P为红色
如果节点P为红色，那么会违背了红黑树的特性：红色节点的孩子节点必须是黑色。在这种条件下，可以得出节点G一定是黑色。为了解决恢复红黑树的特性，我们还需要依据节点U的颜色来选择相应的操作。
CASE 3.1：节点P和节点U均为红色
如果是这种情况，那么我们需要改变节点P，U和G的颜色，也就是节点P变成黑色，节点U变成黑色，节点G变成红色。整个过程如下图所示：
有一点需要注意的是，如果节点G刚好是根节点，那么无需修改节点G的颜色。
CASE 3.2：节点P是红色，节点U是黑色，这里的节点U有可能是叶子节点
这种情况会衍生出更多的情况，比如如果U是黑色的，那么我们需要根据节点K是节点P的左孩子还是右孩子来分别使用一次旋转或2次旋转的操作。
CASE 3.2.1：P是G的右孩子，K是P的右孩子
我们首先对节点G进行左旋操作，使得G成为K的兄弟节点，也就是说G变成了S。接下来，将S修改成红色，节点P修改成黑色。整个过程用到了左旋和切换颜色的操作，如下图所示：
CASE 3.2.2：P是G的右孩子，而K是P的左孩子
在这种情况下，我们首先对P进行右旋操作，整个操作使得整棵树的状态回到场景3.2.1，接下来要做的是根据场景3.2.1来继续调整这棵树。整个过程用到了右旋，左旋和切换颜色的操作，如下图所示：
CASE 3.2.3：P是G的左孩子，K是P的左孩子
这种场景刚好是场景CASE 3.2.1的镜像，思路是一样的，主要的改变是左旋操作变成了右旋操作
CASE 3.2.4：P是G的左孩子，而K是P的右孩子
这种场景刚好是CASE 3.2.2的镜像，思路是一样的，主要的改变是要对P进行左旋操作，然后进入CASE3.2.3状态，然后继续根据CASE3.2.3的状态来调整
整个实现思路如下所示：
def insert(self, key, value):
if self.is_empty(): # Case 1
root = create_tree_node(key, value, BLACK)
self.root = root
return root
else:
new_node = create_tree_node(key, value, RED)
parent, left = find_parent(self.root, new_node.key)
add_child(parent, new_node, left)
if is_red_node(parent): # Case 3
grand_parent = get_parent(parent)
uncle = get_sibling(parent)
if is_red_node(uncle): # Case 3.1
if not is_root(grand_parent):
set_color_to(grand_parent, RED)
set_color_to(uncle, BLACK)
set_color_to(parent, BLACK)
else: # Case 3.2
# uncle's color is black
if parent == grand_parent.right_child:
if parent.left_child == new_node: # Case 3.2.2
parent = right_rotate(parent)
grand_parent.right_child = parent
new_node = parent.right_child
if parent.right_child == new_node: # Case 3.2.1
parent = left_rotate(grand_parent)
get_parent(parent).right_child = parent
set_color_to(parent, BLACK)
set_color_to(parent.left_child, RED)
if is_root(parent):
self.root = parent
else:
if parent.right_child == new_node: # Case 3.2.4
parent = left_rotate(parent)
grand_parent.left_child = parent
new_node = parent.left_child
if parent.left_child == new_node: # Case 3.2.3
parent = right_rotate(grand_parent)
get_parent(parent).left_child = parent
set_color_to(parent, BLACK)
set_color_to(parent.right_child, RED)
if is_root(parent):
self.root = parent
删除一个节点
与插入操作相比，删除操作还是比较复杂的。为了删除节点x，你需要根据BST树的规则来删除x节点，有一点非常重要：如果x节点有2个孩子节点，那么需要在x节点的左子树（右子树）上找到最大（最小）的节点max（min），并互换2个节点的内容，最终，x节点要么是叶子节点，要么是只有一个孩子的节点。
调整完位置之后再删除节点x，仅仅满足了红黑树的有序性，并不一定满足红黑树自身的特性。因此，在删除节点x时，我们需要根据以下几种情况来调整，以便能够满足红黑树自身的特性。
假设节点u是x的兄弟节点，z是x的父亲节点，删除操作时，需要考虑以下几种情况：
Case 1： x的颜色为红色
由于x是红色，而且它肯定有一个孩子是NIL节点（由BST删除规则决定了x最多有一个孩子节点），又因为红黑树的特性：根节点到任意一个NIL节点所经过的黑色节点数一定是一样的，就意味着节点x是有2个NIL节点的叶子节点，颜色为红色。如果是这种情况，那么直接删除x节点，无需做任何调整。
Case 2： x的颜色为黑色，且有一个非NIL节点
由于x的颜色为黑色，而且它有一个孩子是非NIL节点，这个孩子节点的颜色肯定是红色（如果是黑色，那么会破坏红黑树的规则5，详细见上面红黑树的规则），而且是该红色的孩子肯定是叶子节点（也就是该红色孩子的2个孩子节点指向了NIL节点）。如果是这种情况，那么只需要将红色的孩子改成黑色并覆盖x。
Case 3： x的颜色为黑色，而且是叶子节点（也就是x的2个孩子均指向了NIL节点）
由于删除的节点的颜色是黑色，而且是叶子节点，因此从根节点到即将删除的节点上的路径，黑色节点的个数会减1，因此破坏了红黑树的特性5。
为了恢复特性5，我们引入了DOUBLE_BLACK_NODE概念，也就是将即将删除的节点x替换成DOUBLE_BLACK_NODE类型的节点，它相当于2个黑色节点，此时的x节点就变成了DOUBLE_BLACK_NODE类型的节点。接下来的任务就是将DOUBLE_BLACK_NODE类型的节点变换成单个黑色节点。要想完成转换，我们需要考虑以下几种情况（我们只考虑x是右孩子的场景）：
Case 3.1：x为DOUBLE_BLACK_NODE类型节点，它的父亲节点z为黑色，它的兄弟节点u也为黑色，如下图左边部分所示：
这种场景下，又划分为以下3种场景，不过，在执行以下场景之前，我们需要对节点z执行pull_black操作，该操作会把它的孩子节点的颜色降级（颜色减1），比如黑色降级成红色，DOUBLE_BLACK\颜色变成黑色，同时会把当前节点z的颜色升一级（颜色加1），比如节点z从黑色改成DOUBLE_BLACK\颜色。
Case 3.1.1： 兄弟节点u的孩子节点均是黑色
也就是说1和5两个节点均是黑色，它们的父亲节点是u，也就是上图左边部分的3。由于节点u的孩子都是黑色，做完pull_black操作后节点u是红色，因此，u节点所表示的子树无需调整，而节点z的颜色是DOUBLE_BLACK\，为了消除这种颜色，我们需要继续以节点z来做调整，以下2种情况会停止调整：
- 如果当前的z是根节点，那么只需要将z的颜色修改成黑色 or
- 根据条件执行任意一个Case 3.1.2、 Case 3.1.3、Case 3.2或Case 3.3，每个操作都会把z的颜色修改成黑色
Case 3.1.2： 兄弟节点u的左孩子节点是红色，如下图左边部分所示：
上图表明：节点1是红色，而且是u的左孩子。这种情况需要借助操作flip_right和push_black来完成，这2步操作最终会将DOUBLE_BLACK节点消除，如上图的最右边部分。
Case 3.1.3： 兄弟节点u的右孩子节点是红色，如下图左边部分所示：
由上图可知，节点5是红色且节点1是黑色，它们的父亲u是节点3。这种情况需要借助rotate_left操作来将条件变换成Case 3.1.2，然后再根据Case 3.1.2的操作来消除DOUBLE_BLACK节点。
Case 3.2：x为DOUBLE_BLACK_NODE类型节点，它的父亲节点z为红色，它的兄弟节点也为黑色，如下图所示：
该场景与Case 3.1是一样的，唯一的区别在于这个场景操作完之后，DOUBLE_BLACK_NODE类型的节点就消失了，也就是没有Case 3.1.1。
Case 3.3：x为DOUBLE_BLACK_NODE类型节点，它的父亲节点z为黑色，它的兄弟节点也为红色，如下图所示：
这个场景能够通过旋转和调整节点的颜色（也就是借助flip_right）来变换成Case 3.2，然后最终通过Case 3.2的方式来消除DOUBLE_BLACK_NODE类型节点。
因此，整个Case3的逻辑应该如下所示：
if is_red_node(node.left_child):
# Case 3.3
node = flip_right(node) #Transform to Case 3.2
node.right_child = fix_right_doubleblack_left_black(node.right_child)
return node
else:
# Case 3.1 and Case 3.2
return fix_right_doubleblack_left_black(node)
Case 4： x的颜色为黑色，而且是叶子节点（也就是x的2个孩子均指向了NIL节点），x是左孩子
由于Case 3只考虑了删除的节点是右孩子，因此还要考虑删除的节点是左孩子的情况，Case 4与Case 3的区别在于所有的旋转操作都反着来，其余都一样，因此理解Case 3至关重要。如果你依然无法理解，那么可以参考源码来帮助你理解。
以上删除操作还是非常的复杂的，因此我只打算梳理出以下逻辑框架，具体的细节，还需要你参考源码来学习。
def remove(self, key):
# 从根节点出发，找到要删除的节点
node = find_node(self.root, key)
if node is None:
return
# 如果该节点有2个孩子，那么找到比该节点大的下一个临近的节点
if not is_nil(node.left_child) and not is_nil(node.right_child):
#internal node
new_node = find_min_successor(node)
switch_node(new_node, node)
node = new_node
if is_red_node(node): # Case 1
# Red
remove_child(node.parent, node)
else:
# Black
if is_leaf(node):
new_child = replace_child(node.parent, node, DOUBLE_BLACK_NODE)
node = new_child
while is_double_black_node(node):
if node.parent.right_child == node: # Case 3
node = fix_right_double_black(node.parent)
else: # Case 4
node = fix_left_double_black(node.parent)
if is_root(node):
if node == DOUBLE_BLACK_NODE:
self.root = NIL
set_color_to(node, BLACK)
else: # Case 2
red_leaf_child = remove_child(node.parent, node)
set_color_to(red_leaf_child, BLACK)
查找操作
红黑树的查找操作比较简单，具体的实现如下所示：
def find_node(start, key):
current = start
while not is_nil(current):
if current.key == key:
return current
if key < current.key:
current = current.left_child
else:
current = current.right_child
return None
其中start是任何一个节点，通常是根节点，因为我们的查找范围是整棵树。
空间复杂度和时间复杂度
终于把红黑树讲完了，真的很复杂，接下来，让我们分析红黑树提供的以下方法的时间复杂度和空间复杂度：
- 查找树种的某一个节点（search），由于红黑树具有较好的平衡性，因此，它的查找一个时间的最坏和平均的时间复杂度是O(log(n))，空间复杂度是O(1)
- 往树里增加一个新的节点（insert），由于插入的过程涉及到查找，而且调整操作是O(1)，因此它的时间复杂度也是O(log(n))，空间复杂度是O(1)
- 从树里删除一个节点（remove），由于移除的过程也涉及查找，而且调整操作最多是O(log(n))，因此它的时间复杂度也是O(log(n))，空间复杂度是O(1)
文中没有给出具体的源码，原因是实现一个红黑树的代码量太多了，因此无法友好地呈现出来，不过，你可以到这里获取一个完整的红黑树实现。
总结
红黑树是非常基础的数据结构，它被广泛应用于各种高级的数据结构，比如C++中std的map和set，Java的HashMap用它来解决冲突碰撞。了解红黑树，能够让你更加高效地使用那些高级的数据结构，除此之外，你还可以根据自己的要求来使用红黑树。
参考
创建新文章
删除文章或章节
{{ c.user.name }}
{{ c.content }}