数据结构进阶—红黑树

文章目录

1、R-B Tree的概念

红黑树(R-B Tree)，是一种

二叉搜索树

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

接近平衡的。AVL树是高度平衡的

。C++ STL中，很多部分(包括set, multiset, map, multimap)的底层都是红黑树。对于任意一棵红黑树，它可以在O(

    l
   
   
    o
   
   
    
     g
    
    
     2
    
   
   
    N
   
  
  
   log_2N
  
 
log2​N)时间内做查找，插入和删除，这里的N是树中元素的数目。

2、红黑树的性质

红黑树是每个节点都带有颜色属性的二叉查找树，颜色或红色或黑色。在二叉查找树强制一般要求以外，对于任何有效的红黑树还增加了如下的额外要求：

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

2.1 红黑树性质分析

性质1和性质2：这个很好理解，红黑树嘛，结点不是红色就是黑色，至于为什么根结点是黑色的，因为这也是规定。
性质3：这里的叶子结点不是我们平常认知的叶子结点(没有子结点的结点)，而是NIL(可以认为是nullptr)
性质4：在一棵红黑树中，不可能存在连续的两个红结点(就是父结点是红色的并且子结点也是红色的)
性质5：在上图中，例如黑结点13到黑结点1左边的NUL，有2个黑结点，到黑结点11的左右两边也有2个黑结点。对于红结点17到红结点22左右两边和到27的左右两边的黑结点数也是相同的，都为2。

因为上图满足这5点性质，所以该树是一棵红黑树

在R-B Tree的概念中提到红黑树是接近平衡的，因为红黑树确保没有一条路径会比其他路径长出俩倍。为什么是这样呢？
由于每个结点非红即黑(性质1)，加上不存在两个连续的红结点(性质4)，那么红黑树的最长路径一定是红黑交替的，而最短路径一定全都是黑结点。而任意结点其所有后代叶结点的简单路径上，均包含相同数目的黑色结点，则说明最长路径和最短路径中的黑色结点数目一定相等。最后加上根节点为黑(性质2)和叶子结点为黑(性质3)，那么一定可以得到一个结论：

最长路径<=2*最短路径

最长路径 = 最短路径

最长路径 = 2*最短路径

3、红黑树的插入

当我们在对红黑树进行插入操作时，对树做了修改，那么可能会违背红黑树的性质。为了保持红黑树的性质，我们可以通过对树进行旋转，即修改树种某些结点的颜色及指针结构，以达到对红黑树进行插入、删除结点等操作时，红黑树依然能保持它特有的性质(五点性质)。
红黑树的插入分为5种情况，在了解之前，我们还要必须知道插入的结点是红色的，如果插入结点为黑色，总是会破坏性质5，而插入红结点不一定会破坏性质5。

因为在插入之前，该树已经是红黑树，插入了黑结点肯定会影响该结点到根结点的这条路径

。比如：在上图中黑结点11的左边插入黑结点，除了这条路径的黑结点数为4之外，其他的都为3。那为什么插入红色结点不一定会破坏性质5呢？假如还是在上图中黑结点11的左边插入红结点，在插入之后，每条路径的黑结点还是3。
除此之外，我们将需要插入的结点标为N，父结点为P，祖父结点为G，叔结点为U(父亲的亲兄弟)。下面将逐一介绍这5种情况：

3.1 情况1

该树为空树，直接插入根结点的位置，违反性质1，把节点颜色有红改为黑即可

3.2 情况2

插入节点N的父节点P为黑色，不违反任何性质，无需做任何修改 

3.3 情况3

N为红，P为红，（祖节点一定存在，且为黑，下边同理）U也为红，这里不论P是G的左孩子，还是右孩子；不论N是P的左孩子，还是右孩子

为什么在这个情况下，祖父结点一定存在？因为P结点为红，假设祖父结点不存在，那么P将成为整颗树的根，但P为红色，已经违反了性质2(根结点为黑色)

在此情况下，只需要将P和U变色即可

3.4 情况4

N为红，P为红，U为黑(存在为黑或者不存在)，P为G的左孩子，N为P的左孩子(或者P为G的右孩子，N为P的左孩子；反正就是同向的)

在此情况下，需要将P、G变色，P、G变换即左单旋(或者右单旋)

此处为左单旋，右单旋为相反操作

3.5 情况5

N为红，P为红，U为黑(存在为黑或者不存在)，P为G的左孩子，N为P的右孩子(或者P为G的右孩子，N为P的左孩子；反正两方向相反)

在此情况下，需要进行两次旋旋转，P、N右单旋，G、N左单旋
此处为右左单旋，左右单旋为相反操作

4、树的旋转

红黑树的旋转和AVL树的旋转一样，只是红黑树没有平衡因子，不需要控制平衡因子

4.1 左单旋

voidRotateL(Node* parent){
    Node* subR = parent->_right;//parent的的右边一定不为nullptr
    Node* subRL = subR->_left;//subR的左边可能为nullptr
    Node* pparent = parent->_parent;//保存parent的根(父节点)//将subRL链接到parent的右侧
    parent->_right = subRL;if(subRL !=nullptr)
        subRL->_parent = parent;//将parent链接到subR左侧
    subR->_left = parent;
    parent->_parent = subR;//将subR和pparent链接起来//pparent为nullptr，subR要成为新的根if(pparent ==nullptr)//_parent == _root{
        subR->_parent = pparent;
        _root = subR;}//pparent不为nullptr，就链接pparent和subRelse{if(pparent->_right == parent)
            pparent->_right = subR;else
            pparent->_left = subR;
        subR->_parent = pparent;}}

4.2 右单旋

voidRotateR(Node* parent){
    Node* subL = parent->_left;//parent的的左边一定不为nullptr
    Node* subLR = subL->_right;//subL的右边可能为nullptr
    Node* pparent = parent->_parent;//保存parent的根(父节点)//将subLR链接到parent的左侧
    parent->_left = subLR;if(subLR !=nullptr)
        subLR->_parent = parent;//将parent链接到subL右侧
    subL->_right = parent;
    parent->_parent = subL;//将subL和pparent链接起来//pparent为nullptr，subL要成为新的根if(pparent ==nullptr){
        subL->_parent = pparent;
        _root = subL;}//pparent不为nullptr，就链接pparent和subLelse{if(pparent->_left == parent)
            pparent->_left = subL;else
            pparent->_right = subL;
        subL->_parent = pparent;}}

4.3 左右单旋和右左单旋

//右旋左旋voidRotateRL(Node* parent){RotateR(parent->_right);RotateL(parent);}//左旋右旋voidRotateLR(Node* parent){RotateL(parent->_left);RotateR(parent);}

5、旋转总结

1. 父亲节点是·黑色，插入的节点为红色，不需要进行操作。
2. 父亲节点和叔叔节点是红色，插入一个红色的节点后，父亲节点和叔叔节点变为黑色，祖父节点变为红色
3. 父亲节点是红色、叔叔节点不存在或者存在且为黑色： 1.parent在grandfather左侧： cur在parent左侧 -> 以祖父为中心，进行右旋，并且祖父变为红色，父亲变为黑色 (右旋) cur在parent右侧 -> 先以父亲为中心进行左旋，再以祖父为中心进行右旋 (左右双旋) 2.parent在grandfather右侧： cur在parent右侧 -> 以祖父为中心，进行左旋,并且祖父变为红色，父亲变为黑色 (左旋) cur在parent左侧 -> 先以父亲为中心进行右旋，再以祖父为中心进行左旋 (右左双旋)

6、整体代码

#pragmaonce#include<iostream>usingnamespace std;enumColor{
    RED,
    BLACK
};template<classK,classV>structRBTreeNode{
    RBTreeNode<K, V>* _parent;
    RBTreeNode<K, V>* _left;
    RBTreeNode<K, V>* _right;

    pair<K, V> _kv;
    Color _cor;RBTreeNode(const pair<K, V>& kv):_parent(nullptr),_left(nullptr),_right(nullptr),_kv(kv),_cor(RED){}};template<classK,classV>classRBTree{typedef RBTreeNode<K, V> Node;public:RBTree():_root(nullptr){}boolInsert(const pair<K, V>& kv){//_root为nullptr，说明是插入的第一个值if(_root ==nullptr){
            _root =newNode(kv);
            _root->_cor = BLACK;returntrue;}

        Node* parent =nullptr;
        Node* cur = _root;while(cur){//插入的值比cur大，说明要在右边插入if(kv.first > cur->_kv.first){
                parent = cur;
                cur = cur->_right;}//插入的值比cur小，说明要在左边插入elseif(kv.first < cur->_kv.first){
                parent = cur;
                cur = cur->_left;}elsereturnfalse;}//链接父子结点
        cur =newNode(kv);if(kv.first > parent->_kv.first){
            parent->_right = cur;
            cur->_parent = parent;}else{
            parent->_left = cur;
            cur->_parent = parent;}//控制平衡while(parent !=nullptr&& parent->_cor == RED){//不需要判断grandfather是否为nullptr，因为parent如果是红色，不可能是根
            Node* grandfather = parent->_parent;if(parent == grandfather->_left){
                Node* uncle = grandfather->_right;//情况1、uncle存在且为红，不需要旋转处理if(uncle !=nullptr&& uncle->_cor == RED){//变色+向上继续调整
                    parent->_cor = uncle->_cor = BLACK;
                    grandfather->_cor = RED;

                    cur = grandfather;
                    parent = cur->_parent;}//情况2、uncle存在且为黑/不存在else{//cur为parent的左孩子，需要进右单旋//       g      p(黑)//     p     c    g(红)//   cif(cur == parent->_left){RotateR(grandfather);
                        parent->_cor = BLACK;
                        grandfather->_cor = RED;}//cur为parent的右孩子，需要左右双旋(先左旋，再右旋)//      g            c(黑)//   p(红)         p   g(红)//      c(红)else{RotateLR(grandfather);//RorateL(parent);//RorateR(grandfather);
                        cur->_cor = BLACK;
                        grandfather->_cor = RED;}break;}}//parent为grandfather的右孩子，和parent为grandfather的左孩子的情况一样，只是方向不同else{
                Node* uncle = grandfather->_left;//情况1、uncle存在且为红，不需要旋转处理if(uncle !=nullptr&& uncle->_cor == RED){//变色+向上继续调整
                    parent->_cor = uncle->_cor = BLACK;
                    grandfather->_cor = RED;

                    cur = grandfather;
                    parent = cur->_parent;}//情况2、uncle存在且为黑/不存在else{//cur为parent的右孩子，需要进左单旋if(cur == parent->_right){RotateL(grandfather);
                        parent->_cor = BLACK;
                        grandfather->_cor = RED;}//cur为parent的左孩子，需要进右左单旋else{RotateRL(grandfather);//RorateR(parent);//RorateL(grandfather);
                        cur->_cor = BLACK;
                        grandfather->_cor = RED;}break;}}}//让根变黑
        _root->_cor = BLACK;returntrue;}private:
    Node* _root;//右单旋voidRotateR(Node* parent){
        Node* subL = parent->_left;//parent的的左边一定不为nullptr
        Node* subLR = subL->_right;//subL的右边可能为nullptr
        Node* pparent = parent->_parent;//保存parent的根(父节点)//将subLR链接到parent的左侧
        parent->_left = subLR;if(subLR !=nullptr)
            subLR->_parent = parent;//将parent链接到subL右侧
        subL->_right = parent;
        parent->_parent = subL;//将subL和pparent链接起来//pparent为nullptr，subL要成为新的根if(pparent ==nullptr){
            subL->_parent = pparent;
            _root = subL;}//pparent不为nullptr，就链接pparent和subLelse{if(pparent->_left == parent)
                pparent->_left = subL;else
                pparent->_right = subL;
            subL->_parent = pparent;}}//左单旋voidRotateL(Node* parent){
        Node* subR = parent->_right;//parent的的右边一定不为nullptr
        Node* subRL = subR->_left;//subR的左边可能为nullptr
        Node* pparent = parent->_parent;//保存parent的根(父节点)//将subRL链接到parent的右侧
        parent->_right = subRL;if(subRL !=nullptr)
            subRL->_parent = parent;//将parent链接到subR左侧
        subR->_left = parent;
        parent->_parent = subR;//将subR和pparent链接起来//pparent为nullptr，subR要成为新的根if(pparent ==nullptr)//_parent == _root{
            subR->_parent = pparent;
            _root = subR;}//pparent不为nullptr，就链接pparent和subRelse{if(pparent->_right == parent)
                pparent->_right = subR;else
                pparent->_left = subR;
            subR->_parent = pparent;}}//右旋左旋voidRotateRL(Node* parent){RotateR(parent->_right);RotateL(parent);}//左旋右旋voidRotateLR(Node* parent){RotateL(parent->_left);RotateR(parent);}};