27红黑树

红黑树

二叉树->二叉排序树->二叉平衡树->红黑树（自平衡的二叉排序树）

由B树转化而来。

特点

1.节点是红色或黑色

2.根节点是黑色

3.所有的叶子节点是黑色（所说的叶子节点是NULL的逻辑模型）

4.每一个红节点的子节点是黑色（即不存在两个连续的红色）

5.从任意节点到每个叶子的所有路径都包含相同的黑色节点（又称黑高）。

红黑树的状态有左倾和右倾

根据红色节点个数判断状态

操作

插入（从B树演化而来）

插入的节点必须是红色。

具体的步骤只有：

1.重新着色

2.旋转

如果叔叔节点是红色，重新着色。

如果叔叔节点是黑色，旋转/重新着色/都有

1.按照标准的二叉排序树进行插入，新插入的节点设置为红色

2.如果待插入的节点是根节点，转换为黑色

3.如果插入节点的父节点是黑色，则直接插入

4.如果插入节点的父节点不是黑色，则看叔叔节点

​ 4.1如果叔叔节点是红色，将父亲节点和叔叔节点都设置为黑色，将爷爷节点设置为红色，同样模式以爷爷节点继续向上探索，直到根节点（这种情况只着色，不需旋转）

​ 4.2如果叔叔节点是黑色

删除

概念：双黑节点：如果删除的是一个黑色节点，并且被其它黑色子节点替换。（即待删除节点和替换它的孩子都是黑色）

定义：待删除结点内部值value，u为替换它的叶子节点

1.先执行标准排序树的删除

2.如果u或v是红色，替换之后直接删除（简单情况）

3.u和v都是黑色

​ 3.1u是双黑结点

​ 3.1.1当前节点u是双黑节点，但不是根节点

1.待删除结点的兄弟节点是黑色，且兄弟节点的孩子节点至少有一个红色

2.待删除结点的兄弟节点是黑色，且没有红色孩子

3.待删除结点的兄弟节点是红色

​ 3.1.2当前节点u是双黑节点，并且是根节点

整棵树的黑高减1