当前位置: 首页 > news >正文

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

红黑树原理与插入伪代码

红黑树的原理

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

  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)。插入伪代码的核心在于将新节点插入树中,然后通过颜色修正和旋转操作来保持红黑树的平衡特性。这使得红黑树能够在多次插入和删除操作后,依旧保持良好的查找性能。


http://www.mrgr.cn/news/75138.html

相关文章:

  • 30 秒!用通义灵码画 SpaceX 星链发射流程图
  • golang使用etcd版本问题
  • Android setContentView执行流程(一)-生成DecorView
  • 浅谈C#之内存管理
  • POI实现根据PPTX模板渲染PPT
  • 网络安全-Linux基础(bash脚本)
  • SpringCloud框架学习(第三部分:Resilience4j 与 Micrometer)
  • 关于我重生到21世纪学C语言这件事——指针详解(1)
  • 【计算机网络】Socket编程接口
  • 【MinIO】Python 运用 MinIO 实现简易文件系统
  • WLAN消失或者已连接但是访问不了互联网
  • SpringSecurity+jwt+captcha登录认证授权总结
  • 程序员的数学之进制与零
  • Flink1.19编译并Standalone模式本地运行
  • 保姆级教程,免费短链平台
  • cache缺失和关联度
  • sqlmap使用教程
  • Python 异常处理试卷
  • 【HarmonyOS】鸿蒙系统在租房项目中的项目实战(一)
  • 大语言模型LLM综述
  • GRU(门控循环单元)详解
  • Siggraph Asia 2024 | Adobe发布MagicClay:可通过文字引导去对3D模型中的特定部分进行雕刻
  • 【今天的乐子】你真懂代码吗?挑战这10个笑话,程序员专属梗了解一下
  • C++《继承》
  • 企业运营的智能化升级:AI助理与SOP的融合之道
  • java八股-jvm入门-程序计数器,堆,元空间,虚拟机栈,本地方法栈,类加载器,双亲委派,类加载执行过程