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

红黑树原理与插入伪代码

红黑树的原理

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

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.rootparent = NULLwhile current is not NULL:parent = currentif new_node.value < current.value:current = current.leftelse:current = current.right# 2. 插入节点并设置父节点new_node.parent = parentif 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.parentLEFT_ROTATE(tree, node)         # 左旋父节点node.parent.color = BLACK           # 情况 3：叔叔是黑色，且当前节点是左子节点node.parent.parent.color = REDRIGHT_ROTATE(tree, node.parent.parent)  # 右旋祖父节点else:                                       # 父节点是祖父的右子节点（对称情况）uncle = node.parent.parent.left         # 叔叔节点if uncle is not NULL and uncle.color == RED:  # 情况 1：叔叔节点是红色node.parent.color = BLACKuncle.color = BLACKnode.parent.parent.color = REDnode = node.parent.parentelse:if node == node.parent.left:        # 情况 2：叔叔是黑色，且当前节点是左子节点node = node.parentRIGHT_ROTATE(tree, node)        # 右旋父节点node.parent.color = BLACK           # 情况 3：叔叔是黑色，且当前节点是右子节点node.parent.parent.color = REDLEFT_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 = noderight_child.parent = node.parent       # 右子节点的父节点更新为当前节点的父节点if node.parent is NULL:tree.root = right_child            # 当前节点是根节点，更新根节点else if node == node.parent.left:node.parent.left = right_childelse:node.parent.right = right_childright_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 = nodeleft_child.parent = node.parent        # 左子节点的父节点更新为当前节点的父节点if node.parent is NULL:tree.root = left_child             # 当前节点是根节点，更新根节点else if node == node.parent.left:node.parent.left = left_childelse:node.parent.right = left_childleft_child.right = node                # 当前节点变为左子节点的右子节点node.parent = left_child

总结

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