内容大纲

红黑树

huan_kong

202字小于1分钟

2023-12-31

规则

image-20240102101002793

  • 节点上红色或黑色
  • 根节点上黑色
  • 每个叶子节点都上黑色的空节点(NIL节点)
  • 每个红色节点的两个子节点都是黑色
  • 从每个叶子到根的所有路径上不能有两个连续的红色节点
  • 从任一节点到其每个叶子的所有路径都包含相同数目都黑色节点

变色

在插入一个新节点时 可能会导致树不再平衡

可以通过三种方式 让树保持平衡

换色

把红色节点变成黑色 把黑色节点变成红色

左旋转

1

右旋转

1

插入

插入时通常采用 红色