教程目录

想要实际看看算法是如何工作的吗?

通过交互式可视化深入理解算法运行过程

查看算法可视化

红黑树(Red-Black Tree)

介绍

红黑树是一种自平衡二叉搜索树,最初被称为"对称二叉B树",后来改名为红黑树。因为在每个节点上都增加了一个表示颜色的属性,可以是红色或黑色。红黑树通过着色规则和特定的重新平衡操作(旋转和重新着色)来保持树的平衡。

红黑树中的几个关键概念:

  • 节点(Node):包含数据、左右子节点指针、父节点指针及颜色标记(红/黑)
  • 着色规则:每个节点被标记为红色或黑色,以满足特定的平衡条件
  • 黑高(Black Height):从任一节点到其后代叶节点的路径上黑色节点的数量
  • 旋转(Rotation):与AVL树类似的结构调整操作
  • 重新着色(Recoloring):改变节点颜色,配合旋转实现平衡

核心特性

红黑树必须满足以下五个性质:

  1. 每个节点或是红色,或是黑色
  2. 根节点必须是黑色
  3. 所有叶子节点(NIL节点)都是黑色
  4. 如果一个节点是红色,则其两个子节点都是黑色(不能有连续的红色节点)
  5. 对于每个节点,从该节点到其所有后代叶子节点的路径上,包含相同数量的黑色节点

...

目录