三、红黑树插入

1.插入节点

插入节点分为2步：

（1） 先查找，如果树中已存在该节点，则插入失败

（2）树中不存在该节点，插入

1. //插入
2.  pair<Node*, bool> Insert(const pair<K, V>& kv)
3.  {
4.    if (_root == nullptr)
5.    {
6.      _root = new Node(kv);
7.      _root->_col = BLACK;
8.      return make_pair(_root, true);
9.    }
10. 
11.     //1.先看树中，kv是否存在
12.     Node* parent = nullptr;
13.     Node* cur = _root;
14.     while (cur)
15.     {
16.       if (cur->_kv.first < kv.first)
17.       {
18.         //kv比当前节点值大，向右走
19.         parent = cur;
20.         cur = cur->_right;
21.       }
22.       else if (cur->_kv.first > kv.first)
23.       {
24.         //kv比当前节点值小，向左走
25.         parent = cur;
26.         cur = cur->_left;
27.       }
28.       else
29.       {
30.         //kv和当前节点值相等，已存在，插入失败
31.         return make_pair(cur, false);
32.       }
33.     }
34. 
35.     //2.走到这里，说明kv在树中不存在，需要插入kv，并且cur已经为空，parent已经是叶子节点了
36.     Node* newNode = new Node(kv);
37.     newNode->_col = RED;
38.     if (parent->_kv.first < kv.first)
39.     {
40.       //kv比parent值大，插入到parent的右边
41.       parent->_right = newNode;
42.       cur->_parent = parent;
43.     }
44.     else
45.     {
46.       //kv比parent值小，插入到parent的左边
47.       parent->_left = newNode;
48.       cur->_parent = parent;
49.     }
50.     cur = newNode;
51. 
52.     return make_pair(cur, true);
53.   }

2.控制颜色

所以在插入节点之后，为了满足红黑树的性质，还需要调整节点颜色：

（1）父亲为黑色

如果父亲是黑色，那么不需要调整，4个规则都满足，插入已完成

（2）父亲是红色

如果父亲是红色，违反了规则（3），需要调整颜色

这时就需要对树中的节点进行颜色处理了。

四、红黑树颜色处理

所有插入的新节点颜色都是红色，当父亲是红色时，需要进行颜色处理，分3种情况进行处理。在这3种情况中，cur为新插入节点，p为父亲节点，u为叔叔节点，g为祖父节点。下面的树都可能是一棵完整的树，也有可能是一棵子树。

1.cur红，p红，g黑，u存在且为红

当cur为红，p为红，g为黑，u存在且为红时，为了满足红黑树的性质，处理方法：将p和u变黑，g变红

（1）抽象图

如下a、b、c、d、e都是子树：

（1）假如g是根节点，根据红黑树性质，根节点必须是黑色，那就把g再变黑就好了

（2）假如g不是根节点，g是子树，那么g还有parent节点。

①如果g的parent是黑色，满足红黑树性质，那么停止调整。

②如果g的parent是红色，就破坏了规则（3），那么还需要继续向上调整。

调整方法为：把g当作cur，继续向上调整，直到p不存在，或p存在且为黑停止。

（2）具象图

①g是根节点，直接把p和u变黑，g变红

②g不是根节点，g是子树，把p和u变黑，g变红之后，还要继续向上调整，直到p不存在，或p存在且为黑停止

2. cur为红，p为红，g为黑，u为黑或u不存在（单旋）

这种情况下，g、p、cur形成直线，先看cur为红，p为红，g为黑，u为黑的情况

这是由情况一cur红，p红，g黑，u存在且为红处理以后变换而来，比如以下情况：

在这种情况下，cur原来的颜色一定是黑色，只不过在处理的过程当中，将cur的颜色变成了红色，所以cur不是新增节点，而是新增节点的祖先节点。

（1）抽象图

如下a、b、c、d、e都是子树，由于要旋转，所以要分为两种情况：当p是g的左子树，cur是p的左子树时，g右单旋，p变黑，g变红：

当p是g的右子树，cur是p的右子树时，g左单旋，p变黑，g变红：

（2）具象图

cur是新增节点的祖先节点，那么a、b一定不为空，由于从g到u的路径上有2个黑色节点，那么a和b都存在一个黑色节点，因此，c中也有一个黑色节点，才能满足每条路径上有相同数目的黑色节点。因此d、e要么同时不存在，要么同时为空。

当p是g的左子树，cur是p的左子树时，将节点g右单旋，p变黑，g变红：

当p是g的右子树，cur是p的右子树时，将节点g左单旋，p变黑，g变红：

再看cur为红，p为红，g为黑，u不存在的情况：

u不存在的情况更为简单，假如p是g的左子树，cur是p的左子树，将节点g右单旋，p变黑，g变红即可

假如p是g的右子树，cur是p的右子树，将节点g左单旋，p变黑，g变红即可

3.cur为红，p为红，g为黑，u不存在或u为黑（双旋）

这种情况下g、p、cur形成折线，先看cur为红，p为红，g为黑，u为黑的情况：

（1）抽象图

当p是g的左子树，cur是p的右子树时，处理方法：p左单旋，g右单旋，cur变黑，g变红：

当p是g的右子树，cur是p的左子树时，处理方法：p右单旋，就变成了情况二

（2）具象图

当p是g的左子树，cur是p的右子树时，将p左单旋，g右单旋，cur变黑，g变红

当p是g的右子树，cur是p的左子树，p右单旋，g左单旋，p变黑，g变红

再看cur为红，p为红，g为黑，u不存在的情况，u不存在的情况更为简单：

当p是g的左子树，cur是p的右子树时，将p左单旋，g右单旋，cur变黑，g变红

当p是g的右子树，cur是p的左子树，p右单旋就变成了情况二：