Python 中的红黑树 – 实现示例

在这篇文章中，让我们尝试了解红黑树。红黑树是一种自平衡二叉搜索树，由鲁道夫·拜尔 (Rudolf Bayer) 于 1972 年发明，他称之为“对称二叉 B 树”。

尽管红黑树很复杂，但它的操作在最坏情况下具有良好的运行时间，并且可以高效地用于搜索、插入和删除。这些都可以在 O(logN) 时间内完成，其中 N 是树中的节点数。

实际上，红黑树是一种二叉搜索树，可以智能地插入和删除，以保持树的合理平衡。关于红黑树需要特别注意的一点是，在该树中，叶子节点不存储任何数据。

另请阅读：波束搜索算法及其逻辑和 Python 实现

红黑树的性质

红黑树是一种二叉搜索树，其中每个节点的颜色要么是红色，要么是黑色。除了二叉搜索树的其他限制外，红黑树还有以下附加要求：

节点的颜色为红色或黑色。
根节点的颜色始终为黑色。
所有叶节点都是黑色的。
每个红色节点都有两个黑色的子节点。
从给定节点到其任何叶节点的每条简单路径都有相同数量的黑色

下图是红黑树的一个例子

例子

这些约束强化了红黑树的一个关键属性。

从根节点到任何叶节点的最长路径不超过从根到该树中任何其他叶节点的最短路径的两倍。

这会产生一棵大致平衡的树。由于插入、删除和搜索等操作所需的最坏情况时间与树的高度成正比，因此与普通二叉搜索树不同，这个理论上的高度上限允许红黑树在最坏情况下保持高效。

要理解这些属性的重要性，只需注意根据属性 4，任何路径都不能连续有两个红色节点。最短的可能路径将具有所有黑色节点，最长的可能路径将交替具有红色和黑色节点。由于所有最大路径都具有相同数量的黑色节点（属性 5），因此没有路径的长度超过任何其他路径的两倍。

红黑树的不同操作

在红黑树上执行只读操作（如遍历树中的节点）不需要对二叉搜索树进行任何修改。请记住，每棵红黑树都是二叉搜索树的特例。然而，插入和删除操作可能会违反红黑树的属性。因此，这些操作可能需要恢复红黑属性，这可能需要少量（O(log N) 或摊销 O(1)）颜色变化。

1. 插入节点

插入操作的开始方式与我们在二叉搜索树中添加新节点的方式相同。然而，在二叉搜索树中，我们总是将新节点添加为叶子，而在红黑树中，叶子节点不包含任何数据。因此，我们不是添加新节点作为叶节点，而是添加一个具有两个黑色叶节点的红色内部节点。请注意，新节点的颜色为红色，其叶节点的颜色为黑色。一旦添加新节点，可能会违反红黑树的某些性质。因此，为了恢复它们的属性，我们检查某些情况并根据插入后出现的情况恢复属性。

当我们在红黑树中插入新节点时，需要注意以下几点：

所有叶节点始终是黑色的。因此性质 3 始终成立。
属性 4（每个红色节点的两个子节点都是黑色）仅通过添加红色节点、重新绘制黑色节点红色或旋转来受到威胁。
属性 5（从任何给定节点到其叶节点的所有路径都具有相同数量的黑色节点）仅通过添加黑色节点、将红色节点重新绘制为黑色或旋转来受到威胁。

情况 1：将新节点添加到根树

在这种情况下，N 被重新漆成黑色，因为树的根始终是黑色的。由于 s 一次向每条路径添加一个黑色节点，因此不违反性质 5。

情况2：新节点的父节点（P）是黑色

在这种情况下，每个红色节点的两个子节点都是黑色的，因此属性 4 不会失效。财产 5 也没有受到威胁。这是因为新节点 S 有两个黑色叶子子节点，但由于是红色，因此通过其每个子节点的路径具有相同数量的黑色节点。

（在下面的情况下，假设有一个祖父节点（父节点的父节点）-G，因为它的父节点P是红色的，如果它是根，那么它就是黑色的。这样，N也有一个叔叔节点（父节点的兄弟节点） – U（无论 U 是叶节点还是内部节点）。）

情况 3：父节点 (P) 和叔节点 (U) 均为红色。

在这种情况下，违反了属性 5，即从任何给定节点到其叶节点的所有路径都具有相同数量的黑色节点。第三种情况的插入如下图所示。

为了恢复属性 5，两个节点（P 和 U）都被重新绘制为黑色，祖节点 G 被重新绘制为红色。现在，新的红色节点 N 有一个黑色父节点。由于任何经过父母或叔叔的路径都必须经过祖父母，因此这些路径上的黑色节点的数量没有改变。

然而，祖父母 G 现在可能违反属性 2（规定根节点始终为黑色）或属性 4（规定每个红色节点的两个子节点均为黑色）。

当 G 有红色父代时，性质 4 将被违反。为了解决这个问题，整个过程在案例 1 中的 G 上递归执行。

插入3

情况 4：父母 P 是红色，叔叔 U 是黑色，N 是 P 的右孩子，P 是 G 的左孩子

为了解决这个问题，进行左旋转以切换新节点 S 及其父节点的角色。旋转之后，请注意，我们重新标记了 N 和 P，然后调用情况 5 来处理新节点的父节点。这样做是因为仍然违反了属性 4，即每个红色节点的两个子节点都应该是黑色。下图说明了案例 4 的插入。请注意，在 N 是 G 的左孩子、P 是 G 的右孩子的情况下，我们必须执行右旋转。

插入4

情况 5：父节点 P 为红色，叔叔 U 为黑色，新节点 N 是 P 的左子节点，P 是其父节点 G 的左子节点。

为了解决这个问题，对 G（N 的祖父母）执行右旋转。经过这次旋转，前父节点 P 现在是新节点 N 和前祖节点 G 的父节点。我们知道 G 的颜色是黑色（因为否则它的前子节点不可能是红色）。现在切换 P 和 G 的颜色，以便生成的树满足属性 4，即红色节点的两个子节点都是黑色。下图说明了案例 5 的插入。

插入5

2. 删除节点

我们开始以与二叉搜索树相同的方式从红黑树中删除节点。在二叉搜索树中，当我们删除具有两个非叶子子节点的节点时，我们会找到该节点的左子树中的最大元素或右子树中的最小元素，并将其值移入节点被删除。

之后，我们删除从中复制值的节点。请注意，该节点的非叶子节点必须少于两个。因此，仅仅复制一个值并不会违反任何红黑性质，只是将删除问题简化为删除最多有一个非叶子孩子的节点问题。

在本节中，我们假设要删除一个最多具有一个非叶子节点的节点，我们将其称为其子节点。如果该节点有两个叶子子节点，则让其中一个作为其子节点。

在删除一个节点时，如果它的颜色是红色，那么我们可以简单地用它的子节点替换它，子节点必须是黑色的。通过已删除节点的所有路径将仅经过一个较少的红色节点，并且已删除节点的父节点和子节点都必须是黑色的，因此不会违反任何属性。

另一个简单的情况是当我们删除具有红色子节点的黑色节点时。在这种情况下，属性 4 和属性 5 可能会被违反，因此要恢复它们，只需将删除的节点的子节点重新绘制为黑色即可。然而，当要删除的节点及其子节点都是黑色时，就会出现复杂的情况。在这种情况下，我们首先用其子节点替换要删除的节点。

情况1：N是新节点。

在这种情况下，我们从每条路径中删除了一个黑色节点，并且新的根是黑色的，因此没有违反任何属性。

情况2：兄弟姐妹S是红色

在这种情况下，交换 P 和 S 的颜色，然后在 P 处向左旋转。在生成的树中，S 将成为 N 的祖父母。下面说明了案例 2 的删除。

删除2

案例 3：P、S 和 S 的孩子都是黑人

在这种情况下，只需将 S 重新绘制为红色即可。在生成的树中，所有经过 S 的路径都会少一个黑色节点。因此，所有经过 P 的路径现在比不经过 P 的路径少 1 个黑色节点，因此性质 5 仍然被违反。为了解决这个问题，我们从案例 1 开始对 P 执行重新平衡过程。案例 3 如下所示

删除3

情况4：S和S的孩子是黑色，但P是红色

在这种情况下，我们交换 S 和 P 的颜色。虽然这不会影响经过 S 的路径上黑色节点的数量，但它会在经过 N 的路径上添加一个黑色节点，以弥补在那些路径。下图说明了这种情况。

删除4

情况5：N是P的左孩子，S是黑色，S的左孩子是红色，S的右孩子是黑色

在这种情况下，在 S 处执行右旋转。旋转后，S 的左子节点成为 S 的父节点和 N 的新兄弟节点。另外，交换 S 及其新父代的颜色。请注意，现在所有路径仍然具有相同数量的黑色节点，但 N 有一个黑色兄弟节点，其右子节点为红色，因此我们属于情况 6。请参阅下图。

删除5

情况 6：S 是黑色，S 的右孩子是红色，N 是其父项 P 的左孩子

在这种情况下，在 p 处进行左旋转，使 s 成为 P 的父级和 S 的右子级。旋转后，P 和 S 的颜色互换，S 的右孩子被着色为黑色。执行这些步骤后，您将观察到属性 4 和属性 5 仍然有效。下图解释了案例6

删除6

用Python实现红绿树算法

import sys
 
class Node():
    def __init__(self, item):
        self.item = item
        self.parent = None  #parent node
        self.left = None   # left node
        self.right = None  # right node
        self.color = 1     #1=red , 0 = black
 
 
class RedBlackTree():
    def __init__(self):
        self.TNULL = Node(0)
        self.TNULL.color = 0
        self.TNULL.left = None
        self.TNULL.right = None
        self.root = self.TNULL
 
    # Preorder
    def pre_order_helper(self, node):
        if node != TNULL:
            sys.stdout.write(node.item + " ")
            self.pre_order_helper(node.left)
            self.pre_order_helper(node.right)
 
    # Balancing the tree after deletion
    def delete_fix(self, x):
        while x != self.root and x.color == 0:
            if x == x.parent.left:
                s = x.parent.right
                if s.color == 1:
                    s.color = 0
                    x.parent.color = 1
                    self.left_rotate(x.parent)
                    s = x.parent.right
 
                if s.left.color == 0 and s.right.color == 0:
                    s.color = 1
                    x = x.parent
                else:
                    if s.right.color == 0:
                        s.left.color = 0
                        s.color = 1
                        self.right_rotate(s)
                        s = x.parent.right
 
                    s.color = x.parent.color
                    x.parent.color = 0
                    s.right.color = 0
                    self.left_rotate(x.parent)
                    x = self.root
            else:
                s = x.parent.left
                if s.color == 1:
                    s.color = 0
                    x.parent.color = 1
                    self.right_rotate(x.parent)
                    s = x.parent.left
 
                if s.right.color == 0 and s.right.color == 0:
                    s.color = 1
                    x = x.parent
                else:
                    if s.left.color == 0:
                        s.right.color = 0
                        s.color = 1
                        self.left_rotate(s)
                        s = x.parent.left
 
                    s.color = x.parent.color
                    x.parent.color = 0
                    s.left.color = 0
                    self.right_rotate(x.parent)
                    x = self.root
        x.color = 0
 
    def __rb_transplant(self, u, v):
        if u.parent == None:
            self.root = v
        elif u == u.parent.left:
            u.parent.left = v
        else:
            u.parent.right = v
        v.parent = u.parent
 
    # Node deletion
    def delete_node_helper(self, node, key):
        z = self.TNULL
        while node != self.TNULL:
            if node.item == key:
                z = node
 
            if node.item <= key:
                node = node.right
            else:
                node = node.left
 
        if z == self.TNULL:
            print("Cannot find key in the tree")
            return
 
        y = z
        y_original_color = y.color
        if z.left == self.TNULL:
            x = z.right
            self.__rb_transplant(z, z.right)
        elif (z.right == self.TNULL):
            x = z.left
            self.__rb_transplant(z, z.left)
        else:
            y = self.minimum(z.right)
            y_original_color = y.color
            x = y.right
            if y.parent == z:
                x.parent = y
            else:
                self.__rb_transplant(y, y.right)
                y.right = z.right
                y.right.parent = y
 
            self.__rb_transplant(z, y)
            y.left = z.left
            y.left.parent = y
            y.color = z.color
        if y_original_color == 0:
            self.delete_fix(x)
 
    # Balance the tree after insertion
    def fix_insert(self, k):
        while k.parent.color == 1:
            if k.parent == k.parent.parent.right:
                u = k.parent.parent.left
                if u.color == 1:
                    u.color = 0
                    k.parent.color = 0
                    k.parent.parent.color = 1
                    k = k.parent.parent
                else:
                    if k == k.parent.left:
                        k = k.parent
                        self.right_rotate(k)
                    k.parent.color = 0
                    k.parent.parent.color = 1
                    self.left_rotate(k.parent.parent)
            else:
                u = k.parent.parent.right
 
                if u.color == 1:
                    u.color = 0
                    k.parent.color = 0
                    k.parent.parent.color = 1
                    k = k.parent.parent
                else:
                    if k == k.parent.right:
                        k = k.parent
                        self.left_rotate(k)
                    k.parent.color = 0
                    k.parent.parent.color = 1
                    self.right_rotate(k.parent.parent)
            if k == self.root:
                break
        self.root.color = 0
 
    # Print
    def __print_helper(self, node, indent, last):
        if node != self.TNULL:
            sys.stdout.write(indent)
            if last:
                sys.stdout.write("R----")
                indent += "     "
            else:
                sys.stdout.write("L----")
                indent += "|    "
 
            s_color = "RED" if node.color == 1 else "BLACK"
            print(str(node.item) + "(" + s_color + ")")
            self.__print_helper(node.left, indent, False)
            self.__print_helper(node.right, indent, True)
 
    def preorder(self):
        self.pre_order_helper(self.root)
 
    def minimum(self, node):
        while node.left != self.TNULL:
            node = node.left
        return node
 
    def maximum(self, node):
        while node.right != self.TNULL:
            node = node.right
        return node
 
    def successor(self, x):
        if x.right != self.TNULL:
            return self.minimum(x.right)
 
        y = x.parent
        while y != self.TNULL and x == y.right:
            x = y
            y = y.parent
        return y
 
    def predecessor(self,  x):
        if (x.left != self.TNULL):
            return self.maximum(x.left)
 
        y = x.parent
        while y != self.TNULL and x == y.left:
            x = y
            y = y.parent
 
        return y
 
    def left_rotate(self, x):
        y = x.right
        x.right = y.left
        if y.left != self.TNULL:
            y.left.parent = x
 
        y.parent = x.parent
        if x.parent == None:
            self.root = y
        elif x == x.parent.left:
            x.parent.left = y
        else:
            x.parent.right = y
        y.left = x
        x.parent = y
 
    def right_rotate(self, x):
        y = x.left
        x.left = y.right
        if y.right != self.TNULL:
            y.right.parent = x
 
        y.parent = x.parent
        if x.parent == None:
            self.root = y
        elif x == x.parent.right:
            x.parent.right = y
        else:
            x.parent.left = y
        y.right = x
        x.parent = y
 
    def insert(self, key):
        node = Node(key)
        node.parent = None
        node.item = key
        node.left = self.TNULL
        node.right = self.TNULL
        node.color = 1
 
        y = None
        x = self.root
 
        while x != self.TNULL:
            y = x
            if node.item < x.item:
                x = x.left
            else:
                x = x.right
 
        node.parent = y
        if y == None:
            self.root = node
        elif node.item < y.item:
            y.left = node
        else:
            y.right = node
 
        if node.parent == None:
            node.color = 0
            return
 
        if node.parent.parent == None:
            return
 
        self.fix_insert(node)
 
    def get_root(self):
        return self.root
 
    def delete_node(self, item):
        self.delete_node_helper(self.root, item)
 
    def print_tree(self):
        self.__print_helper(self.root, "", True)
 
 
if __name__ == "__main__":
    bst = RedBlackTree()
 
    bst.insert(70)
    bst.insert(60)
    bst.insert(85)
    bst.insert(80)
    bst.insert(95)
    bst.insert(65)
 
    bst.print_tree()
    print("\nAfter deleting an element")
    bst.delete_node(80)
    bst.print_tree()

输出

红黑树的应用

红黑树是高效的二叉搜索树，因为它们为插入、删除和搜索操作提供最坏情况的时间保证。

红黑树不仅在实时应用等时间敏感的应用中有价值，而且还优选用作其他数据结构中的构建块，以提供最坏情况的保证，AVL树还支持O(log n) 搜索、插入和删除操作，但它们比红黑树更加严格平衡，从而导致插入和删除速度较慢，但数据检索速度较快。

概括

在这篇文章中，我们深入研究了红黑树、它在Python中的实现以及它的应用。最后，我们可以得出结论：红黑树是一种自平衡二叉搜索树，也称为“对称二叉B树”。虽然红黑树很复杂，但它的操作在最坏情况下运行时间很好，并且使用效率很高，因为搜索、插入和删除都可以在 O(log n) 时间内完成。