算法基础 -- 红黑树原理与插入伪代码
红黑树原理与插入伪代码
红黑树的原理
红黑树是一种自平衡的二叉搜索树，通过对节点的颜色（红色或黑色）以及结构的约束条件来保持树的平衡。红黑树的原理可以通过以下五个特性描述：
- 节点是红色或黑色。
- 根节点必须是黑色。
- 所有叶节点（即
NULL节点）都是黑色的。 - 红色节点的子节点必须是黑色，即红色节点不能有红色的父节点或子节点（无双红特性）。
- 从任一节点到其所有后代叶节点的所有路径上，必须包含相同数目的黑色节点。
这些特性使红黑树能够在最坏情况下保证查找、插入和删除操作的时间复杂度为 O(log n)，从而保持较好的性能。
红黑树的插入操作
红黑树的插入操作相对复杂，因为在每次插入新节点时，可能会破坏树的平衡。因此，需要进行颜色修正和旋转操作来重新平衡树。插入过程可以分为两个阶段：
- 插入节点：将新节点插入到树中，类似于普通的二叉搜索树插入。
- 修复树：修复因插入而可能破坏的红黑树特性。
插入节点的伪代码
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)。插入伪代码的核心在于将新节点插入树中，然后通过颜色修正和旋转操作来保持红黑树的平衡特性。这使得红黑树能够在多次插入和删除操作后，依旧保持良好的查找性能。