Red-Black Tree

Red-Black Tree is a self-balancing Binary Search Tree (BST) where every node follows following rules.
红黑树是一个自平衡的二叉搜索树

红黑树特征

1. 每一个节点不是黑就是红
2. 根节点是黑色的
3. 每个叶子节点(NIL节点，空节点)是黑色的
4. 红色节点的子节点不能是红色（不能连续两个红色）
5. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点
   

红黑树实现

节点插入

插入规则：每个新插入的节点默认是红色节点，因为如果是黑色则会直接违背红黑树第五个特征，少违背一条特性，就意味着我们需要处理的情况越少（节点插入主要是违反了规则4）

Let x be the newly inserted node

1- 如果插入的是根节点 （x = root）

将节点颜色变为黑色

2- 如果插入节点的父节点是黑色（ x.parent is BLACK）

直接插入，不做改变

3- 如果插入节点的父节点是红色（ x.parent is RED）

• 3.1如果uncle节点是黑色(包括NIL和黑叶子节点两种)

第一种 g绕p右旋 g和p变色（g-p-x 直线型，即g p x三个节点在一条直线）
第二种 g绕p左旋 g和p变色（g-p-x 直线型）
第三种 p绕x左旋变为直线型再按照直线型处理 （g-p-x 三角型，即g p x三个节点构成三角形）
第四种 p绕x左旋变为直线型再按照直线型处理 （g-p-x 三角型）

• 3.2如果uncle节点是红色

改变 g p u的颜色 将g作为新插入的节点 按照 1 2 3 三种情况进行递归

节点删除

删除节点主要分为两个步骤：①对待删除节点实行 standard BST delete (二叉搜索树删除节点) ② 进行颜色变换和旋转以符合红黑树规则

一、Standard BST delete

standard BST delete最终会变成删除一个叶子节点或者删除只有一个子节点的节点。令v为要删除的节点，让u为替换v的子节点。（当u为叶子节点时，u为NIL，u为黑色；当v为有一个子节点的节点时，u为其子节点，u颜色未知）
1） 待删除节点v是叶子节点，直接删除它

2） 待删除节点v有一个子节点u，将子节点u的值赋给v节点，并删除子节点u

3） 待删除节点有两个子节点，找到待删除节点的后继节点，将后继节点的值赋给待删除节点，然后转变成删除后继节点（此时可能递归，直到要删除的节点为叶子节点或仅有一个子节点）

二、变色和旋转

• 1 不存在u和v都是红色,
• 2 如果u或v其中一个为红色，就直接把要替换的子节点变成黑色
  
• 3 如果u和v都是黑色,u必定为NIL
  

1）在当前节点u为双黑色(double black)且不是根节点时，设兄弟节点为s

..a）当兄弟节点是黑色而且兄弟节点至少有一个红色子节点，令该红色子节点为r,可分为四种情况。可参考插入操作3.1，分为直线型和三角形进行操作
....i)Left Left Case (s is left child of its parent and r is left child of s or both children of s are red). This is mirror of right right case shown in below diagram.
....ii)Left Right Case (s is left child of its parent and r is right child). This is mirror of right left case shown in below diagram.
....iii)Right Right Case (s is right child of its parent and r is right child of s or both children of s are red)此时p可能为红也可能为黑，
直线型，p可能为红也可能为黑，p绕s左旋，p变成黑色，s变成p原来的颜色.png
....iiii)Right Left Case (s is right child of its parent and r is left child of s)
三角型，p可能为红也可能为黑，s先绕其红色子节点旋转成直线型，再按直线型处理.png
..(b): 如果兄弟节点是黑色，且其没有子节点（也可说有两个NIL子节点）, perform recoloring, and recur for the parent if parent is black.
image.png
…(i) 如果p是红色，直接把p变黑，把s变红
…(ii) 如果p是黑色，把s变红，把p当作双黑点u，返回1）进行迭代

..(c): 如果兄弟节点是红色，则兄弟节点必有两个黑色子节点（不是NIL子节点），p绕s旋转，根据p绕s左旋还是右旋的情况对s的某一个子节点变成红色

p绕s左旋
…(i) Left Case (s is left child of its parent). This is mirror of right right case shown in below diagram. We right rotate the parent p.
…(ii) Right Case (s is right child of its parent). We left rotate the parent p.

2）在当前节点u为双黑色(double black)且是根节点时，其实意味着该树只有一个根黑色节点，直接删除它就行了