红黑树是一棵自平衡二叉搜索树，所以查找和二叉搜索树的时间复杂度相同。插入和删除操作稍微复杂一点，颜色变更很迅速，需要少量O(logN)的时间，旋转不会超过三次，插入操作只需要两次旋转。因此，红黑树结点的插入和删除只需要O(logN)的时间复杂度，即可恢复红黑树的性质。

01

插入

如何将结点插入红黑树？三步骤：

1、将红黑树当成一棵二叉搜索树，插入；

2、将新插入的结点着成红色；

3、通过旋转和重新着色，使其满足红黑树的性质。

这棵树本身是一棵自平衡二叉搜索树，插入结点后不改变二叉搜索树的事实，不论是左旋、右旋还是着色，也不改变这个事实；

将新结点着成红色，不会违背“从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点”的性质，只会违背“如果一个节点是红色的，则它的子节点必须是黑色的”这一条性质，使违背的性质最少化，减少了我们处理的工作量；

最后，通过一系列的旋转和重新着色，使新树满足红黑树的所有性质，重新成为一棵红黑树。

根据父结点的颜色，分为三种情况：

1）插入结点为根结点，将结点着成黑色，完成；

2）插入结点的父结点为黑色，无须处理；

3）插入结点的父结点为红色，则插入结点一定存在祖父结点和叔叔结点（即使叔叔结点为空，也是一个黑色结点），我们根据叔叔结点的颜色，再分成三种情况。

1

当前结点的父结点为红色，叔叔结点也为红色

1) 将“父节点”设为黑色。
2) 将“叔叔节点”设为黑色。
3) 将“祖父节点”设为“红色”。
4) 将“祖父节点”设为“当前节点”(红色节点)；即，之后继续对“当前节点”进行操作。

2

当前结点的父结点为红色，叔叔结点为黑色，且当前结点为其父结点的右孩子

1) 将“父节点”作为“新的当前节点”。
2) 以“新的当前节点”为支点进行左旋。

3

当前结点的父结点为红色，叔叔结点为黑色，且当前结点为其父结点的左孩子

1) 将“父节点”设为“黑色”。
2) 将“祖父节点”设为“红色”。
3) 以“祖父节点”为支点进行右旋。

注：凡属于本公众号内容，未经允许不得私自转载，否则将依法追究侵权责任。