【喵的算法课】红黑树 插入【11期】

一、红黑树概念

1. 红黑树定义

为什么引入平衡树或红黑树

2.红黑树前身 234树

234树只能有2结点，3结点，4结点3类

234树插入操作

3.红黑树性质

注意红黑树底层有空的叶结点

4.红黑树和234树等价

二、红黑树插入操作

1.

路径若是黑色结点会很麻烦

2.

情况1

父结点黑色4种

情况2

其他8种情况。(之后对图尝试操作

3.操作

①

LL:染色+左旋 RR:染色+右旋

②

RL:变色，父结点右旋，祖父结点左旋

LR:变色，父结点左旋，祖父节点右旋

变色注意往想要方向对应。

③

最好选择插入结点的祖父结点，也就是黑色结点进行上溢。

实际在234树提到上一层，在红黑树中无变化。

1.父结点，叔父结点变黑

2.祖父结点变红

3.上溢进行递归