[数据结构与算法]数据结构-左倾红黑树

数据结构-左倾红黑树

注：更多文章，可以进入我的博客：筱白博客

五大特性：

1.结点是红色或黑色。

2.根结点是黑色。

3.每个叶子结点都是黑色的空结点（NIL结点）。

4 每个红色结点的两个子结点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色结点)

5.从任一结点到其每个叶子的所有路径都包含相同数目的黑色结点。

左旋

右旋

插入节点的五种情况

总结：

根节点为黑色

路径中不能连续出现两个红色节点

若路径中连续两个红色节点且右倾，则先左旋（针对于左倾红黑树）

若叔叔节点为红色，则变色

若叔叔节点为黑色，则旋转

插入一个节点例子