红黑树【数据结构】

红黑树不仅可以保障数据的有序性，也可以在动态数据集中，提供快速的插入、删除和查找操作。它主要通过对任一节点颜色的改变（红色或黑色）以及部分树结构的旋转来实现。

红黑树插入操作

当我们插入一个新节点时，它首先作为一个红色节点插入，以保持黑平衡，也即性质5。然后需要检查并修复可能违反的红黑树性质。

我们继续详述之前提到的3个情况，并且引入两个新的情况：

3. 情景3（续）：插入节点的父节点是红色，叔叔节点也是红色
   这样的情况称为“双红”情况，需要进行颜色翻转。祖父节点由黑变红，父节点和叔叔节点由红变黑。然后，因为祖父节点可能成为新的双红问题，需要把祖父节点作为当前要处理的节点进行后续处理。

4. 情景4：插入节点的父节点是红色，叔叔节点是黑色，插入节点是其父节点的右子节点，父节点是祖父节点的左子节点
   这种情况需要左旋转父节点，让插入节点上升到父节点的位置，父节点下降到左子节点的位置，然后，问题转换为情景5。

5. 情景5：插入节点的父节点是红色，叔叔节点是黑色，插入节点是其父节点的左子节点，父节点是祖父节点的左子节点（对称情况同理）
   这时，我们对祖父节点进行右旋转，并交换父节点与祖父节点的颜色。这样可以恢复红黑树性质。

以下是插入操作示例的伪代码，包含必要的旋转和重新着色：

class RedBlackTreeNode:
    def __init__(self, key, color, left=None, right=None, parent=None):
        self.key = key
        self.color = color
        self.left = left
        self.right = right
        self.parent = parent

def left_rotate(tree, node):
    # 断言确保右子树非空
    right_node = node.right
    node.right = right_node.left
    if right_node.left != NIL:
        right_node.left.parent = node
    right_node.parent = node.parent
    if node.parent == NIL:
        tree.root = right_node
    elif node == node.parent.left:
        node.parent.left = right_node
    else:
        node.parent.right = right_node
    right_node.left = node
    node.parent = right_node

def right_rotate(tree, node):
    # 类似于左旋转，此处略去细节

def insert_fixup(tree, node):
    while node.parent.color == 'RED':
        if node.parent == node.parent.parent.left:
            uncle = node.parent.parent.right
            if uncle.color == 'RED':
                # 情景3
                node.parent.color = 'BLACK'
                uncle.color = 'BLACK'
                node.parent.parent.color = 'RED'
                node = node.parent.parent
            else:
                if node == node.parent.right:
                    # 情景4
                    node = node.parent
                    left_rotate(tree, node)
                # 情景5
                node.parent.color = 'BLACK'
                node.parent.parent.color = 'RED'
                right_rotate(tree, node.parent.parent)
        else:
            # 对称代码处理
            # ...
    tree.root.color = 'BLACK'

def insert(tree, key):
    node = RedBlackTreeNode(key, 'RED')
    y = NIL
    x = tree.root
    while x != NIL:
        y = x
        if node.key < x.key:
            x = x.left
        else:
            x = x.right
    node.parent = y
    if y == NIL:
        tree.root = node  # 树为空，插入的是根节点
    elif node.key < y.key:
        y.left = node
    else:
        y.right = node
    node.left = NIL
    node.right = NIL
    insert_fixup(tree, node)

在这个示例中，NIL 是一个哨兵节点，代表空的黑色节点。

这个插入操作实现同时考虑了树为空以及非空的情况。insert_fixup 函数负责调整颜色和进行必要的旋转来修复红黑树的性质。

需要注意的是，这只是一个高级伪代码描述。真实的实现需要考虑更多细节，比如当被插入节点的父节点不是根节点的情况下，我们可能需要显式地将NIL节点作为新插入节点的子节点。

红黑树插入操作虽然复杂，但得益于其对树平衡性的保证，它提供了非常高效的数据操作性能。在任何新节点被插入后，最多只需要三次旋转（在双红情景后的两次旋转和一个可能的颜色翻转）。这保证了最坏情况下时间复杂度保持为O(log n)。

红黑树的删除操作

删除操作在红黑树中是最复杂的操作之一，因为它可能会破坏树的平衡。当我们移除一个节点后，为了保持红黑树的性质，可能需要做一系列复杂的树旋转和重新着色。

以下面临的情况如何解决：

1. 删除的是红色节点: 直接删除，因为它不会影响黑高。
2. 删除的是黑色节点，而且有一个红色子节点: 用红色子节点替换该节点，并将其重新染成黑色。
3. 删除的是黑色节点，而且它的两个子节点都是黑色: 这种情况是最复杂的，因为它会影响路径上的黑高。

在删除时，我们通常使用后继节点来替换要删除的节点（如果它有两个子节点的话），然后调整树的平衡情况。这个后继节点是在右子树中找到的最小值节点，这个节点最多只有一个子节点。然后应用"替换-删除"策略，后继节点替代要删除的节点位置，然后删除原后继节点的位置。

修正函数是根据删除黑色节点后失衡的情况进行调整的，这里将删除后的修正操作称为 delete_fixup。

以下是删除节点的伪代码和解释：

def transplant(tree, u, v):
    if u.parent == NIL:
        tree.root = v
    elif u == u.parent.left:
        u.parent.left = v
    else:
        u.parent.right = v
    if v != NIL:
        v.parent = u.parent

def minimum(node):
    while node.left != NIL:
        node = node.left
    return node

def delete_fixup(tree, x):
    while x != tree.root and x.color == 'BLACK':
        if x == x.parent.left:
            w = x.parent.right
            if w.color == 'RED':
                w.color = 'BLACK'
                x.parent.color = 'RED'
                left_rotate(tree, x.parent)
                w = x.parent.right
            if w.left.color == 'BLACK' and w.right.color == 'BLACK':
                w.color = 'RED'
                x = x.parent
            else:
                if w.right.color == 'BLACK':
                    w.left.color = 'BLACK'
                    w.color = 'RED'
                    right_rotate(tree, w)
                    w = x.parent.right
                w.color = x.parent.color
                x.parent.color = 'BLACK'
                w.right.color = 'BLACK'
                left_rotate(tree, x.parent)
                x = tree.root
        else:
            # 对称的处理右子树的情况
            # ...
    x.color = 'BLACK'

def delete(tree, z):
    y = z
    y_original_color = y.color
    if z.left == NIL:
        x = z.right
        transplant(tree, z, z.right)
    elif z.right == NIL:
        x = z.left
        transplant(tree, z, z.left)
    else:
        y = minimum(z.right)
        y_original_color = y.color
        x = y.right
        if y.parent == z:
            x.parent = y
        else:
            transplant(tree, y, y.right)
            y.right = z.right
            y.right.parent = y
        transplant(tree, z, y)
        y.left = z.left
        y.left.parent = y
        y.color = z.color
    if y_original_color == 'BLACK':
        delete_fixup(tree, x)

这个伪代码包含了删除操作的核心逻辑，其中 transplant 函数用来替换节点，minimum 函数用于查找给定节点的后继。变量 y 保存原来的颜色，以判断是否需要调整。如果最初删除的或者移动的 y 节点是黑色的，那么可能会违反红黑性质，需要进一步通过 delete_fixup 来调整。

该调整过程是一个循环，它会在不违反红黑树性质的前提下，向上回溯并调整颜色和执行旋转，直到到达根节点或者 x 指向了一个红色节点。这里的 x 节点可以被认为是一个额外的黑色，它可以是红黑颜色，当它变成红-黑色时，它就变成普通的黑节点，循环就会结束。

如果你想更深入地了解人工智能的其他方面，比如机器学习、深度学习、自然语言处理等等，也可以点击这个链接，我按照如下图所示的学习路线为大家整理了100多G的学习资源，基本涵盖了人工智能学习的所有内容，包括了目前人工智能领域最新顶会论文合集和丰富详细的项目实战资料，可以帮助你入门和进阶。

链接： 人工智能交流群【最新顶会与项目实战】（点击跳转）