数据结构之红黑树

前提

红黑树首先是二叉搜索树，需要满足以下要求：

  • 根和叶子都是黑色。
  • 不存在连续的两个红色结点。
  • 任一结点到叶所有路径黑结点数量都相同
image-20241011201621078

性质

最长路径不超过最短路径的两倍。

image-20241011201859516

红黑树查询略逊于AVL树。

红黑树的删除插入上更加高效。(map和set基于此实现)

插入

插入结点默认为红色。（因为一般不会破坏任何一个性质，一旦破坏只可能违反根叶黑，不红红的性质）

如果性质被破坏了，就需要进行调整。

如果插入的是根节点

直接变黑即可

如果插入结点的叔叔是红色

image-20241011202239956

上图省略空结点。

步骤是：叔父爷一起变色，爷爷变成插入结点，向上继续判定调整。

如果插入结点的叔叔是黑色

需要根据LL，RR，LR，RL形态进行旋转。

LL

image-20241011202457610

上面为LL型，对爷爷进行右旋操作，旋转完成后对刚刚的旋转点和被旋转的点进行变色。

image-20241011202611650

RR

image-20241011202637194
image-20241011202652296

LR

image-20241011202714557
image-20241011202840993

RL

image-20241011202934825
image-20241011203005651