算法基础 -- 红黑树原理与插入伪代码

时间：2024-11-15 09:42:06

红黑树原理与插入伪代码

红黑树的原理

红黑树是一种自平衡的二叉搜索树，通过对节点的颜色（红色或黑色）以及结构的约束条件来保持树的平衡。红黑树的原理可以通过以下五个特性描述：

  1. 节点是红色或黑色。
  2. 根节点必须是黑色。
  3. 所有叶节点（即 NULL 节点）都是黑色的。
  4. 红色节点的子节点必须是黑色，即红色节点不能有红色的父节点或子节点（无双红特性）。
  5. 从任一节点到其所有后代叶节点的所有路径上，必须包含相同数目的黑色节点。

这些特性使红黑树能够在最坏情况下保证查找、插入和删除操作的时间复杂度为 O(log n)，从而保持较好的性能。

红黑树的插入操作

红黑树的插入操作相对复杂，因为在每次插入新节点时，可能会破坏树的平衡。因此，需要进行颜色修正和旋转操作来重新平衡树。插入过程可以分为两个阶段：

  1. 插入节点：将新节点插入到树中，类似于普通的二叉搜索树插入。
  2. 修复树：修复因插入而可能破坏的红黑树特性。

插入节点的伪代码

function RB_INSERT(tree, value):
    new_node = Node(value)
    new_node.color = RED    # 新插入的节点初始为红色
    new_node.left = NULL    # 左子节点为空
    new_node.right = NULL   # 右子节点为空

    # 1. 查找插入位置
    current = tree.root
    parent = NULL

    while current is not NULL:
        parent = current
        if new_node.value < current.value:
            current = current.left
        else:
            current = current.right

    # 2. 插入节点并设置父节点
    new_node.parent = parent

    if parent is NULL:
        tree.root = new_node           # 树为空，新节点为根
    else if new_node.value < parent.value:
        parent.left = new_node         # 新节点为左子节点
    else:
        parent.right = new_node        # 新节点为右子节点

    # 3. 修复红黑树的平衡性
    RB_INSERT_FIXUP(tree, new_node)

修复树的伪代码

插入后，红黑树的性质可能被破坏，特别是双红问题（即父节点和子节点都是红色）。需要通过旋转和重新着色来修复树的平衡。

function RB_INSERT_FIXUP(tree, node):
    while node.parent is not NULL and node.parent.color == RED:
        if node.parent == node.parent.parent.left:  # 父节点是祖父的左子节点
            uncle = node.parent.parent.right        # 叔叔节点
            if uncle is not NULL and uncle.color == RED:  # 情况 1：叔叔节点是红色
                node.parent.color = BLACK           # 将父节点设为黑色
                uncle.color = BLACK                 # 将叔叔节点设为黑色
                node.parent.parent.color = RED      # 将祖父节点设为红色
                node = node.parent.parent           # 将祖父节点作为新的当前节点继续检查
            else:
                if node == node.parent.right:       # 情况 2：叔叔是黑色，且当前节点是右子节点
                    node = node.parent
                    LEFT_ROTATE(tree, node)         # 左旋父节点
                node.parent.color = BLACK           # 情况 3：叔叔是黑色，且当前节点是左子节点
                node.parent.parent.color = RED
                RIGHT_ROTATE(tree, node.parent.parent)  # 右旋祖父节点
        else:                                       # 父节点是祖父的右子节点（对称情况）
            uncle = node.parent.parent.left         # 叔叔节点
            if uncle is not NULL and uncle.color == RED:  # 情况 1：叔叔节点是红色
                node.parent.color = BLACK
                uncle.color = BLACK
                node.parent.parent.color = RED
                node = node.parent.parent
            else:
                if node == node.parent.left:        # 情况 2：叔叔是黑色，且当前节点是左子节点
                    node = node.parent
                    RIGHT_ROTATE(tree, node)        # 右旋父节点
                node.parent.color = BLACK           # 情况 3：叔叔是黑色，且当前节点是右子节点
                node.parent.parent.color = RED
                LEFT_ROTATE(tree, node.parent.parent)  # 左旋祖父节点

    # 保证根节点为黑色
    tree.root.color = BLACK

左旋和右旋的伪代码

红黑树的平衡性是通过旋转来实现的。左旋和右旋操作用于在插入或删除节点时调整树的结构。

左旋的伪代码
function LEFT_ROTATE(tree, node):
    right_child = node.right               # 当前节点的右子节点
    node.right = right_child.left          # 右子节点的左子树变为当前节点的右子树
    if right_child.left is not NULL:
        right_child.left.parent = node

    right_child.parent = node.parent       # 右子节点的父节点更新为当前节点的父节点
    if node.parent is NULL:
        tree.root = right_child            # 当前节点是根节点，更新根节点
    else if node == node.parent.left:
        node.parent.left = right_child
    else:
        node.parent.right = right_child

    right_child.left = node                # 当前节点变为右子节点的左子节点
    node.parent = right_child
右旋的伪代码
function RIGHT_ROTATE(tree, node):
    left_child = node.left                 # 当前节点的左子节点
    node.left = left_child.right           # 左子节点的右子树变为当前节点的左子树
    if left_child.right is not NULL:
        left_child.right.parent = node

    left_child.parent = node.parent        # 左子节点的父节点更新为当前节点的父节点
    if node.parent is NULL:
        tree.root = left_child             # 当前节点是根节点，更新根节点
    else if node == node.parent.left:
        node.parent.left = left_child
    else:
        node.parent.right = left_child

    left_child.right = node                # 当前节点变为左子节点的右子节点
    node.parent = left_child

总结

红黑树的插入操作通过节点插入、颜色修正以及旋转操作来保持树的平衡，确保了最坏情况下的时间复杂度为 O(log n)。插入伪代码的核心在于将新节点插入树中，然后通过颜色修正和旋转操作来保持红黑树的平衡特性。这使得红黑树能够在多次插入和删除操作后，依旧保持良好的查找性能。

相关文章