手撕红黑树 - 聊聊这个基本却又重要的数据结构

原创

Jerry Wang

发布于 2024-03-05 15:33:40

1380

发布于 2024-03-05 15:33:40

我记得本人在大学学习专业课《数据结构》时，虽然学习过二叉搜索树，但是对于是否学习过红黑树的记忆，已经很模糊了。今天正好借这个机会来重温这个基础知识点。

红黑树是一种自平衡的二叉搜索树，它在计算机科学中被广泛用于各种数据结构的实现中，例如在高级语言的库中，如 Java 的 TreeMap 和 TreeSet，以及 C++ 的 std::map 和 std::set。

因此，我们有必要现简单回顾二叉搜索树的概念。

二叉搜索树（BST，Binary Search Tree）是一种在计算机科学中广泛使用的数据结构，特别是在数据存储、检索以及排序领域。它是一种特殊的二叉树，具有一些独特的性质，使得数据的存取效率较高。

在定义上，二叉搜索树是具有以下性质的二叉树：

对于树中的任意一个节点，其左子树中的所有节点的值都小于这个节点的值，而其右子树中的所有节点的值都大于这个节点的值。

这个性质对于所有的节点都成立，从而使得二叉搜索树能够高效地支持诸如查找、插入和删除等操作。

了解二叉搜索树的基本概念之后，我们可以通过一个简单的例子来更直观地理解它的结构和工作原理。假设我们需要构建一个二叉搜索树来存储这些数字序列：30, 20, 40, 10, 25, 35, 50。

构建的过程是这样的：

从序列的第一个数字开始，30 成为树的根节点。
接下来，20 小于 30，所以 20 成为 30 的左子节点。
40 大于 30，因此 40 成为 30 的右子节点。
10 小于 30 且小于 20，于是它成为 20 的左子节点。
25 小于 30 但大于 20，所以它成为 20 的右子节点。
35 大于 30 且小于 40，因此它成为 40 的左子节点。
最后，50 大于 30 也大于 40，所以它成为 40 的右子节点。

通过上述步骤，我们构建了一个二叉搜索树。这棵树完全遵循二叉搜索树的定义：每个节点的左子树只包含小于该节点的值，每个节点的右子树只包含大于该节点的值。这种结构使得查找效率非常高，因为在每个节点处，我们都可以根据查找的值与当前节点值的比较结果决定是向左子树查找还是向右子树查找，从而大大减少了查找所需的比较次数。

我们可以编写一段 Python 代码，输入是一个正整数序列，通过空格键分隔，输出效果是将其构造成二叉搜索树，并打印出来。

完整代码如下：

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def insert_into_bst(root, val):
    if root is None:
        return TreeNode(val)
    if val < root.val:
        root.left = insert_into_bst(root.left, val)
    else:
        root.right = insert_into_bst(root.right, val)
    return root

def print_tree(root, level=0, prefix='H:'):
    if root is not None:
        print_tree(root.right, level + 1, '\')
        print(' ' * 4 * level + prefix + str(root.val))
        print_tree(root.left, level + 1, '/')

# 示例输入，实际输入将根据用户的需求动态读取
input_nums = list(map(int, input("请输入七个正整数，用空格分隔：").split()))
if len(input_nums) != 7:
    print("请输入七个正整数。")
else:
    root = None
    for num in input_nums:
        root = insert_into_bst(root, num)
    
    print_tree(root)

执行上述代码，输出如下：

二叉搜索树支持的操作主要包括：

查找：查找操作是通过比较目标值与节点值来进行的，每一步都可以排除树的一半，因此查找效率很高。
插入：插入新节点时，从根节点开始，根据新节点与当前节点值的比较结果决定向左子树还是右子树移动，直到找到一个叶子节点的位置，然后将新节点插入到这个位置上。
删除：删除操作稍微复杂，因为需要考虑多种情况，如删除的节点是叶子节点、只有一个子节点或者两个子节点。对于最复杂的情况——删除有两个子节点的节点，一般的做法是用其右子树中的最小节点（或左子树中的最大节点）来代替它，然后删除那个最小（或最大）节点。
遍历：二叉搜索树支持多种遍历方式，包括前序遍历、中序遍历和后序遍历。其中，中序遍历二叉搜索树可以按照从小到大的顺序访问树中的每一个节点，这是因为中序遍历首先访问左子树，然后访问根节点，最后访问右子树。

二叉搜索树的效率在很大程度上依赖于树的形状，也就是说，依赖于数据插入的顺序。在最理想的情况下，树是完全平衡的，每个节点的左右子树高度差不超过 1，这样的树被称为平衡二叉搜索树。平衡二叉搜索树能够确保操作的最坏情况时间复杂度为 O(log n)，其中 n 是树中节点的数量。但是，如果插入的数据是有序的，那么构建出来的二叉搜索树将会是一个链状结构，其操作效率将大幅下降，时间复杂度退化为 O(n)。

通过这个例子和相关的解释，我们可以看到二叉搜索树是如何在数据存储和检索中发挥作用的。它通过简单而有效的方式，利用了二叉树结构的特点，以及左小右大的性质，实现了高效的数据操作。不过，要维持二叉搜索树的高效性，还需要通过平衡操作来保证树的形状接近理想状态。这就引出了许多高级的二叉搜索树变种，比如本文要介绍的红黑树。这些变种，通过在树的修改操作中加入平衡机制，确保了操作的高效性，即使在最坏的情况下也能保持较好的性能。

红黑树通过每个节点上的颜色标记（红色或黑色）和对树结构进行特定的旋转操作，保持树的平衡，从而达到提高数据操作效率的目的。

在红黑树中，节点包含的属性有颜色、键值、左子节点、右子节点和父节点指针。红黑树的基本思想是：通过每个节点的颜色来限制从根到叶子的最长路径不会超过最短路径的两倍，因此保证了树的大致平衡。

红黑树遵循五条重要的性质来保持其平衡状态：

每个节点或是红色的，或是黑色的。
根节点是黑色的。
所有叶子节点（NIL 节点，空节点）都是黑色的。
如果一个节点是红色的，则它的两个子节点都是黑色的（从而保证在任何路径上不会出现两个连续的红色节点）。
从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。

下面是一棵红黑树的例子：

这些性质确保了红黑树的关键优势：保持树的平衡，从而在插入、删除和查找操作上提供接近 O(log n) 的时间复杂度，其中 n 是树中节点的数量。

插入操作

插入操作是红黑树中最复杂的部分之一，因为插入新节点后可能会违反红黑树的性质。插入新节点的基本步骤是将新节点着色为红色，并按照二叉搜索树的规则插入树中。插入后，可能需要通过一系列的旋转和重新着色来修正树，以保持红黑树的性质。

插入操作可以分为几种情况处理：

情况 1：新插入的节点是树的根节点。此时，只需要将节点颜色改为黑色即可满足红黑树的所有性质。
情况 2：新插入的节点的父节点是黑色。由于不会引入新的红色节点导致红色节点连续，也不会改变任何路径上的黑色节点数目，因此红黑树的性质依然得到满足，无需任何额外操作。
情况 3：新插入的节点的父节点是红色。这种情况较为复杂，需要根据父节点和叔叔节点的颜色，以及节点的排列位置来进行不同的处理，可能包括重新着色和旋转。

删除操作

删除操作也需要考虑如何在移除节点后保持红黑树的性质。删除节点可能会导致删除路径上黑色节点的数量减少，从而违反红黑树的性质。处理删除操作通常需要通过旋转和重新着色来调整树的结构。

应用实例

考虑一个实际的应用场景：数据库索引。在数据库管理系统中，索引的实现往往依赖于高效的数据结构来优化查询速度。红黑树，凭借其良好的平衡性质和较低的维护成本，在构建索引时提供了一种有效的选择。例如，当数据库需要存储大量数据记录并频繁进行插入、删除和查找操作时，使用红黑树作为索引结构可以显著提高操作的效率，确保了即使在数据量大幅增加时，数据库的性能也不会显著下降。

下面我们来动手编码实战。

我们将构建一个简单的红黑树，并使用它来模拟对数据库记录的索引和查询操作。

首先，我们将实现一个基础版本的红黑树，然后展示如何用它来索引简单的数据项（例如，模拟数据库中的记录ID）。

class Node:
    def __init__(self, data, color="red"):
        self.data = data
        self.color = color
        self.parent = None
        self.left = None
        self.right = None

class RedBlackTree:
    def __init__(self):
        self.TNULL = Node(data=0, color="black")  # 特殊的叶子节点
        self.root = self.TNULL

    def insert(self, data):
        # 创建新节点，初始颜色设置为红色
        new_node = Node(data)
        new_node.left = self.TNULL
        new_node.right = self.TNULL

        # 插入新节点
        parent = None
        current = self.root
        while current != self.TNULL:
            parent = current
            if new_node.data < current.data:
                current = current.left
            else:
                current = current.right
        new_node.parent = parent

        if parent is None:  # 树为空
            self.root = new_node
        elif new_node.data < parent.data:
            parent.left = new_node
        else:
            parent.right = new_node

        new_node.color = "red"
        self.fix_insert(new_node)

    def fix_insert(self, node):
        # 这里简化处理，不包含复杂的旋转和重新着色逻辑
        pass

    def inorder_traverse(self, node, result=None):
        if result is None:
            result = []
        if node != self.TNULL:
            self.inorder_traverse(node.left, result)
            result.append(node.data)
            self.inorder_traverse(node.right, result)
        return result

# 模拟数据库索引操作
def simulate_database_index():
    # 创建红黑树实例
    rb_tree = RedBlackTree()

    # 模拟插入数据库记录的ID
    records = [20, 15, 25, 10, 18, 30]
    for record in records:
        rb_tree.insert(record)

    # 以中序遍历的方式查看索引的排序结果
    sorted_index = rb_tree.inorder_traverse(rb_tree.root)
    print("数据库索引排序结果:", sorted_index)

    # 模拟查询操作（简化演示，实际应用中查询会更复杂）
    # 假设我们要查找ID为18的记录
    print("查询ID为18的记录:", "找到记录" if 18 in sorted_index else "记录不存在")

simulate_database_index()

以上这段代码提供了一个非常基础的红黑树实现框架和它在模拟数据库索引中的简单应用。在实际的数据库系统中，红黑树的插入和删除操作会涉及到更复杂的节点颜色调整和树的旋转，以保持树的平衡性。这里出于简化目的，我们没有实现红黑树的全部功能，特别是fix_insert方法中的调整逻辑是空的。在实际应用中，这部分是确保红黑树保持平衡的关键。