红黑树¶

背一遍忘记一遍，不想背了，好记性不如烂笔头，直接开写！！！红黑树【性质、动图左旋右旋、插入、删除、应用】_红黑树左旋动图-CSDN博客

红黑枚举¶

不会哥们你真要写个字符串表示吧

enum class Color { RED, BLACK };

红黑树节点数据和初始化¶

从这里开始写内部实现，我们把节点单独定义一个，并具有如下的值 * key * value * color：颜色 * Node left； * * right * * parent 很明显节点之间有双向指针 然后我们再初始化一些参数比如根节点、大小、以及空节点*吧

template < typename Key, typename Value > class RBTree {

    //红黑树节点定义

    class Node {
    public:
        Key key;
        Value value;
        Color color;
        Node* left;
        Node* right;
        Node* parent;


    Node(const Key& k, const Value& v, Color c, Node* p = nullptr)
        :key(k), value(v), color(c), left(nullptr), right(nullptr), parent(p) {
    }
    Node()
        :color(Color::BLACK), left(nullptr), right(nullptr), parent(nullptr) {}
    };
};



private: 
    Node *root; 
    size_t size; 
    Node *Nil;

······
}

红黑树查询¶

这个很简单，就是普通的二叉搜索树查询逻辑

    // 查询某节点
    Node* lookUp(Key key) {
        Node* comNode = root;

        while (cmpNode) {
            if (key < comNode->key) {
                comNode = comNode->left;  //  <  左子树  >  右子树  ==  本节点 
            }
            else if (key > comNode->key) {
                comNode = comNode->right;  //  <  左子树  >  右子树  ==  本节点 
            }
            else {
                return cmpNode;
            }
        }
        return cmpNode;
    }

红黑树操作¶

嘻嘻，大头来了

No.1 右旋¶

图文结合，文体两开花

旋转前：

旋转后：

    // 右旋函数
    void rightRotate(Node* node) {
        Node* l_son = node->left; //获取当前节点的左子节点
        // 当前节点的左子树变成左子节点的右子树
        node->left = l_son->right;
        // 如果左子节点的右子树非空，更新其父指针
        if (l_son->right)
            lson->right->parent = node;
        // 左子节点升为当前节点位置，并处理父节点关系
        l_son->parent = node->parent;

        if (!node->parent)
        {
            root = l_son;   //如果当前节点是根节点，更新根节点为左子节点
        }
        else if (node == node->parent->left) {
            node->parent->left = l_son; // 如果当前节点是其父节点的左子节点，更新父节点的左子节点为左子节点
        }
        else {
            node->parent->right = l_son;// 如果当前节点是其父节点的右子节点，更新父节点的右子节点为左子节点
        }

        //node用完了就给放到右子树去
        l_son->right = node;
        node->parent = l_son;
    }

No.2 左旋¶

讲了右旋还不会左旋？

    //左旋函数
    void leftRotate(Node* node) {
        Node* r_son = node->right;
        node->right = r_son->left;
        //维护双向
        if (r_son->left)
        {
            r_son->left->parent = node;
        }
        r_son->parent = node->parent;

        //根节点特判
        if (!node->parent)
        {
            root = l_son;
        }
        else if (node == node->parent->right) {
            node->parent->right = r_son;
        }
        else {
            node->parent->left = r_son;
        }

        //node用完了就给放到右子树去
        l_son->right = node;
        node->parent = l_son;

    }

红黑树的应用¶

Linux内核进程调度由红黑树管理进程控制块。
nginx服务器用红黑树管理定时器。
C++ STL中的map和set的底层实现为红黑树。
.Java8开始，HashMap中，当一个桶的链表长度超过8，则会改用红黑树。