红黑树

1.定义：

红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出两倍倍，因而是接近平衡的。

什么是二叉搜索树：

二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树: 1.若它的左子树不为空，则左子树上所有节点的值都小于根节点的值 2.若它的右子树不为空，则右子树上所有节点的值都大于根节点的值 3.它的左右子树也分别为二叉搜索树

2.红黑树性质：

1.每个结点不是红色就是黑色； 2.根结点是黑色； 3.如果一个节点是红色的，则它的两个孩子结点是黑色的 ，即不可能存在两个连在一起的红色节点； 4.对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点 ，即每条路径中黑色节点个数相同； 5. 每个叶子结点都是黑色的(此处的叶子结点指的是空节点）。

3.为什么最长路径节点个数不会超过最短路径的两倍？

上面这副图没有违反任何红黑树的性质，然后插入红色节点 可以看出最长路径是最短路径的两倍，但此情况为极端情况，刚好最长路径是最短路径的两倍，但此全为黑色节点的红黑树是不存在的，当插入第二个黑色节点时，违反了红黑树中每条路径中黑色节点个数相同这个性质，此极限情况下，刚好节点个数为两倍，所以可以看出最长路径节点个数不会超过最短路径节点个数的两倍。

4.红黑树的插入

步骤一：将新节点插入到红黑树中

红黑树本身就是一颗二叉搜索树，将节点插入后，该树仍然是一颗二叉查找树。也就意味着，树的键值仍然是有序的。此外，无论是左旋还是右旋，若旋转之前这棵树是二叉搜索树，旋转之后它一定还是二叉查找树。这也就意味着，任何的旋转和重新着色操作，都不会改变它仍然是一颗二叉搜索树的事实。 接下来我们只需考虑给节点着色问题，满足红黑树的性质即可。因为我们默认设置的节点颜色为红色（因为加入红色节点后，不会违反性质四：每条路径中黑色节点个数相同，然后我们只需考虑让他们满足其他性质就行）。

bool Insert(const T& data) { Node* pRoot = _pRoot; //按照二叉搜索树的方式插入新节点 if (nullptr == pRoot) { pRoot = new Node(data, BLACK); pRoot->_pParent = _pHead; return true; } else { // 找待插入节点在二叉搜索树中的位置 // 并保存其双亲节点 Node* pCur = pRoot; Node* pParent = nullptr; while (pCur) { pParent = pCur; if (data < pCur->_data) pCur = pCur->_pLeft; else if (data > pCur->_data) pCur = pCur->_pRight; else return false; } // 插入新节点 pCur = new Node(data); if (data < pParent->_data) pParent->_pLeft = pCur; else pParent->_pRight = pCur; pCur->_pParent = pParent; // 2. 检测新节点插入后，红黑树的性质是否造到破坏， // 若满足直接退出，否则对红黑树进行旋转着色处理 //... } // 根节点的颜色可能被修改，将其改回黑色 pRoot->_color = BLACK; _pHead->_pLeft = LeftMost();//指向最左边（最左边为最小数） _pHead->_pRight = RightMost();//指向最右边（最右边为最大树） return true; }

步骤二：通过一系列的旋转或着色等操作，使之重新成为一颗红黑树。

因为新节点的默认颜色是红色，因此：如果其双亲节点的颜色是黑色，没有违反红黑树任何性质，则不需要调整；但当新插入节点的双亲节点颜色为红色时，就违反了性质三不能有连在一起的红色节点，此时需要对红黑树分情况来讨论： 约定:cur为当前节点，p为父节点，g为祖父节点，u为叔叔节点 情况一： cur为红，p为红，g为黑，u存在且为红。 解决方式：将p,u改为黑，g改为红，然后把g当成cur，继续向上调整 如上图。 情况二：cur为红，p为红，g为黑，u不存在或u存在且为黑。

解决方式：将p，g的颜色改变，p变为黑色，g变为红色，然后进行右单旋。 情况三：cur为红，p为红，g为黑，u不存在或u存在且为黑。 解决方式：针对p做左单旋 可以看出，将情况三现在与情况二类似，我们只需改变cur和p的指向，就可以变为情况二，根据情况二的处理方式进行处理即可。 上面三种情况可以看成为p在g的左边，即父亲节点在祖父节点的左边 同样的，右边也有三种情况： 反向情况一：.cur为红，p为红，g为黑，u存在且为红。 解决方式：与情况一相同，将p,u的颜色换为黑色，g的颜色换成红色，然后把g当成cur，继续向上调整。 反向情况二： cur为红，p为红，g为黑，u不存在或u存在且为黑。 解决方法：与情况二相同，交换p,g的颜色，p换为黑，g换为红色，但这次进行左单旋。 反情况三：cur为红，p为红，g为黑，u不存在或u存在且为黑。 解决方式：针对p进行右单旋。 可以看出，只需在改变怕p,和cur的指向，就可以变为反情况二，再根据处理反情况二的方式进行处理即可。

bool Insert(const T& data) { // 按照二叉搜索树的性质插入新节点 Node* & pRoot = GetRoot(); if (nullptr == pRoot) { pRoot = new Node(data, BLACK); pRoot->_pParent = _pHead; return true; } else { // 找待插入节点在二叉搜索树中的位置 // 并保存其双亲节点 Node* pCur = pRoot; Node* pParent = nullptr; while (pCur) { pParent = pCur; if (data < pCur->_data) pCur = pCur->_pLeft; else if (data > pCur->_data) pCur = pCur->_pRight; else return false; } // 插入新节点 pCur = new Node(data); if (data < pParent->_data) pParent->_pLeft = pCur; else pParent->_pRight = pCur; pCur->_pParent = pParent; // pCur新节点默认颜色：红色 // 如果pParent的颜色是黑色的， //满足红黑树性质（不需要做任何处理） // 如果pParent的颜色是红色的， //违反了性质三--不能有连在一起的红色节点 while (pParent != _pHead && pParent->_color == RED) { Node* grandFather = pParent->_pParent; //父亲节点在祖父节点左侧 if (pParent == grandFather->_pLeft) { Node* uncle = grandFather->_pRight; // 叔叔节点存在且为红 if (uncle && RED == uncle->_color) { // 情况一 pParent->_color = BLACK; uncle->_color = BLACK; grandFather->_color = RED; pCur = grandFather; pParent = pCur->_pParent; } else { //叔叔节点不存在 || 叔叔节点存在 && 为黑色 if (pCur == pParent->_pRight) { // 情况三 RotateL(pParent);//左单旋 swap(pCur, pParent);//交换节点指向， //转变为情况二 } // 情况二： pParent->_color = BLACK; grandFather->_color = RED; RotateR(grandFather);//右单旋 } } else { // 一二三的反情况 Node* uncle = grandFather->_pLeft; if (uncle && RED == uncle->_color) {//反情况一 pParent->_color = BLACK; uncle->_color = BLACK; grandFather->_color = RED; pCur = grandFather; pParent = pCur->_pParent; } else { // 叔叔节点不存在 || 存在且为黑 if (pCur == pParent->_pLeft) { // 情况三反情况 RotateR(pParent);//右单旋 swap(pCur, pParent);//交换节点指向， //转变为反情况二 } // 情况二的反情况 pParent->_color = BLACK; grandFather->_color = RED; RotateL(grandFather); } } } } pRoot->_color = BLACK; _pHead->_pLeft = LeftMost(); _pHead->_pRight = RightMost(); return true; }