云端浮梦

large picture of the cover

红黑树 （C++）

概念:

红黑树 是一种二叉搜索树 每个节点上增加一个存储位置代表节点颜色 可以是 红 / 黑

通过对任何一条从根到叶子路径各个节点 进行限制,确保任何一条路径比最短路径长两倍

故接近平衡

性质| 左根右，根叶黑，不红红，黑路同

  • 每个节点不是红就是黑

  • 根节点是黑色

  • 如果一个节点是 红色的 则两孩子 是 黑色的

  • 对于每个节点到后代节点的 简单路径下 都包含相同数目的黑色节点

  • 每个叶子空节点为黑色

红黑树平衡的原理是什么 ?

它通过每个节点上的颜色属性（红色或黑色）来确保树在插入和删除操作后仍然保持大致平衡。

当进行插入和删除操作时，红黑树会通过重新着色和旋转节点来调整树的结构，以保持上述性质

性质3保证了防止出现连续的红色节点会使路径差距太大

性质4保证了保任何一条路径比最短路径长两倍

红黑树能够在插入和删除操作后快速重新平衡，保持其搜索效率。红黑树的搜索、插入和删除操作的时间复杂度都是O(log n)

红黑树的插入操作

  1. 按照二叉搜索树的顺序进行插入数据

  2. 新节点插入后 查看红黑树的性质是否遭到破坏

    • 插入新节点后 颜色默认为红色 ,如果双亲的节点的颜色是黑色 没有违反红黑树任何的性质 故不需要调整

    • 如果插入后节点的颜色为红 双亲节点也是红色 就违反了第三条性质 需要分情况讨论

      情况1. cur 为🔴 p 为🔴 g为⚫ u存在且为 🔴

      解决方法 将 p,u 改为⚫ g 改为🔴 如果 g为根节点 将g改回⚫ 否则 将g 当作Cur 继续网上调整

      情况2. cur 为🔴 p为🔴 g为 ⚫ u不存在/ u存在且为⚫

      2.1 如果u 节点 不存在 则 Cur 一定是新插入的节点 如果 Cur 不是新插入节点则Cur 和p一定有一个节点的颜色是黑色 则不满足路径的黑色节点树相同

      2.2 如果u 节点存在 则其 一定是黑色那么 Cur 原来的颜色一定是黑色的

      3 cur 为红 p为红 g 为黑 u不存在/u存在且为黑

      红黑树的调节关键看叔叔节点

代码参考

#pragma once
​
#include <iostream>
#include <algorithm>
​
using namespace  std;
namespace  chen{
​
    enum Color {
        BLACK,
        RED
    };
​
    template <class K,class V>
    class   RBTreeNode {
    public:
        RBTreeNode(const pair<K, V>& _val)
            : _left(nullptr), _right(nullptr), _parent(nullptr), _kv(_val), _col(RED) // 初始化新节点为红色
        {}
        RBTreeNode<K, V>* _left;   // 左子节点
        RBTreeNode<K, V>* _right;  // 右子节点
        RBTreeNode<K, V>* _parent; // 父节点
        pair<K, V> _kv;            // 键值对
        Color _col;                // 节点颜色
    };
    template <class K,class V>
    class   RBTree {
        typedef RBTreeNode<K,V> Node;
    public:
​
        bool insert(const pair<K,V> & val) {
            // 按照搜索树的顺序进行插入
            if(_root == nullptr) {
                _root = new Node(val);
                _root->_col = BLACK;
                return true;
            }
            Node * Cur = _root;
            Node * parent = nullptr;
            while(Cur) {
                if(Cur->_kv.first < val.first) {
                    parent = Cur;
                    Cur = Cur->_right;
                }else if(Cur->_kv.first > val.first) {
                    parent = Cur;
                    Cur = Cur->_left;
                }else {
                    return false;
                    // 有相同的 K
                }
            }
            Cur = new Node(val);
            Cur->_col = RED; // 新增节点 颜色是RED
            Cur->_parent = parent;
            if(parent->_kv.first < val.first) {
                parent->_right = Cur;
            }else {
                parent->_left = Cur;
            }
​
            while(parent && parent->_col == RED) {
                Node * grandfather = parent->_parent;
                if(grandfather->_left == parent) {
                    Node * uncle = grandfather->_right;
                    if(uncle && uncle->_col == RED) {
                        // 情况一  uncle 存在且为红
                        parent->_col = uncle->_col = BLACK;
                        grandfather->_col = RED;
                        // 继续处理
                        Cur = grandfather;
                        parent = Cur->_parent;
                    }
                    else {
                        //情况三  uncle 存在 且为黑
                        //情况二  uncle 不存在
                        if(Cur == parent->_right) {
                            rotateL(parent);
                            swap(parent , Cur);
                        }
                        // 第三种情况 有可能是 第二种变回来的
                        rotateR(grandfather);
                        grandfather->_col = RED;
                        parent->_col = BLACK;
                        break;
                    }
                }else {
​
                    Node * uncle = grandfather->_left;
                    if(uncle && uncle->_col == RED) {
                        // 情况1
                        parent->_col = uncle->_col = RED;
                        grandfather->_col = RED;
​
                        // 继续处理
                        Cur = grandfather;
                        parent = Cur->_parent;
                    }else {
​
                        if(Cur == parent->_left) {
                            rotateR(parent);
                            swap(parent,grandfather);
                        }
                        rotateL(grandfather);
                        grandfather->_col = RED;
                        parent->_col = BLACK;
                        break;
                    }
                }
​
            }
​
            _root->_col = BLACK;  // 最后根都是黑色
​
            return true;
        }
​
        void InOrder()
        {
            _InOrder(_root);
        }
    private:
        Node * _root = nullptr;
​
        void rotateL(Node * parent) {
​
            Node * New_parent = parent->_right;
            parent->_right = New_parent->_left;
            if(New_parent->_left) {
                New_parent->_left->_parent = parent;
            }
​
            New_parent->_left = parent;
            New_parent->_parent = parent->_parent;
​
            if(parent->_parent == nullptr) {
                _root = New_parent;
            }else if(New_parent->_parent->_left == parent) {
                parent->_parent->_left = New_parent;
            }else {
                parent->_parent->_right = New_parent;
            }
​
            parent->_parent = New_parent;
​
        }
        void rotateR(Node * parent) {
​
            Node * New_parent = parent -> _left;
            parent->_left = New_parent->_right;
​
            New_parent->_left = parent;
            New_parent->_parent = parent->_parent;
​
            if(parent->_parent == nullptr) {
                _root = New_parent;
            }else if(parent->_parent->_left == parent) {
                parent->_parent->_left = New_parent;
            }else {
                parent->_parent->_right = New_parent;
            }
            parent->_parent = New_parent;
        }
​
​
        void _InOrder(Node * root)
        {
            if(!root)return ;
            _InOrder(root->_left);
            cout << root->_kv.first <<" : " << root->_kv.second << " Color:" <<root->_col <<endl;
            _InOrder(root->_right);
        }
    };
​
​
    void testRBTree() {
​
        RBTree<int,int>  RBT;
        RBT.insert({1,1});
        RBT.insert({2,2});
        RBT.insert({3,3});
        RBT.insert({4,4});
        RBT.insert({5,5});
        RBT.insert({6,6});
        RBT.insert({7,7});
        RBT.insert({8,8});
        RBT.insert({9,9});
​
        RBT.InOrder();
    }
​
}

红黑树的删除

红黑树的删除 分为四种情况

  • 删除节点为叶子节点

  • 删除节点只有左孩子,没有右孩子

  • 删除节点只有右孩子,没有左孩子

  • 删除节点 既有右孩子 又有左孩子

删除节点为叶子节点

  • 如果删除节点叶子节点D为红节点 则直接删除红节点

  • 如果删除节点叶子节点D为黑节点

    • 要删除节点的叶子节点为黑色,D的兄弟节点也为黑色,没有侄子节点.

      删除D节点 将P节点变为黑色 将B节点变为白色

    • 要删除节点D为黑色 D的兄弟节点B也为黑色 ,D的左侄子为红色

      删除 D 节点 将B左侄子进行右旋 ,将左侄子变为P的颜色将P变为黑色,再 按照 P 进行左旋

    • 要删除节点D为黑色 D的兄弟节点B也为黑色 ,D的右侄子为红色

      删除D节点 B 变成P 的颜色 P和右侄子的颜色变成黑色 再按照左旋操作

    • 要删除节点D为黑色 D的兄弟节点B也为黑色 ,D的右侄子和左侄子为红色

      先删除D节点 按着P 进行左旋操作 将B变成P 的颜色将P和右侄子变成黑色

    • 要删除的叶子节点D为黑色,D的兄弟节点B为红色 D的左侄子和右侄子为黑色

      先将D节点删除 按照P 节点左旋 将B 变成黑色 将左侄子变成红色

删除节点只有左孩子,没有右孩子

将D的值 变成 左侄子的值 删除左侄子

删除节点D只有右孩子 ,没有左孩子,和情况而一样

将D的值变成 右侄子的值 删除右侄子

删除节点D 既有右孩子也有左孩子

将D节点的值 转换成 D节点前驱节点的值

删除前驱节点 传换成前三种情况

暂未实现😭

搞太久了

模拟实现map|set

在stl中的map 源码 和 set 的源码框架中 为了防止代码冗余其中 Map 和 set 都是使用的同一棵红黑树

如何使用一棵红黑树实现出Map和set？

Map.h

#pragma once
#include "RBTree.h"
namespace chen
{
    template<class K, class V>
    class map
    {
        struct KOV
        {
            const K& operator()(const pair<const K, V>& kv)
            {
                return kv.first;
            }
        };
    public:
        typedef typename RBTree<K, pair<K, V>, KOV>::iterator iterator;
​
        bool insert(const pair<const K, V>& kv)
        {
            return _t.insert(kv);
        }
        iterator begin() {
            return  iterator(_t.begin());
        }
​
        iterator end() {
            return  iterator(_t.end());
        }
    private:
        RBTree<K, pair<K, V>, KOV> _t;
    };
    void test_map1()
    {
        map<int, int> m;
        m.insert(make_pair(1, 10));
        m.insert(make_pair(3, 30));
        m.insert(make_pair(2, 20));
        for(auto &i:m){
            cout << i.first <<":" << i.second << endl;
        }
    }
}
​

Set.h

#pragma once
#include "RBTree.h"
namespace chen {
    template<class K>
    class set {
        struct KOV {
            const K& operator()(const K& key) {
                return key;
            }
        };
    public:
        typedef typename RBTree<K, K, KOV>::iterator iterator;
        // begin和end明确指定typename
        iterator begin() {
            return  iterator(_t.begin());
        }
        iterator end() {
            return  iterator(_t.end());
        }
        bool insert(const K& key) {
            return _t.insert(key);
        }
    private:
        RBTree<K, K, KOV> _t;
    };
    void test_set1() {
        set<int> s;
        s.insert(3);
        s.insert(1);
        s.insert(2);
        set<int>::iterator it = s.begin();
        while (it != s.end()) {
            cout << *it << " ";
            ++it;
        }
        cout << endl;
    }
}
​

RBTree.h

#pragma once
​
#include <iostream>
#include <algorithm>
​
using namespace  std;
namespace  chen{
​
    enum Color {
        BLACK,
        RED
    };
​
    template <class T>
    struct  RBTreeNode {
        RBTreeNode(const T& data)
            : _left(nullptr), _right(nullptr), _parent(nullptr), _data(data), _col(RED) // 初始化新节点为红色
        {}
        RBTreeNode<T>* _left;   // 左子节点
        RBTreeNode<T>* _right;  // 右子节点
        RBTreeNode<T>* _parent; // 父节点
        T _data;                // data Key
        Color _col;                // 节点颜色
    };
​
    template<class T,class Ref,class Ptr>
    struct __RBTreeIterator
    {
        typedef RBTreeNode<T> Node;
        typedef __RBTreeIterator<T,Ref,Ptr> Self;
        Node * _node;
        __RBTreeIterator(Node * node)
            :_node(node)
        {}
​
        Ref operator*(){
            return _node->_data;
        }
        Ptr operator->() {
            return &_node->_data; // 返回数据的指针
        }
        bool operator!=(const Self & s){
            return _node!=s._node;
        }
​
        Self& operator++() {
            if (_node->_right) {
                // 右子树存在，找到右子树中的最左节点
                Node *subLeft = _node->_right;
                while (subLeft->_left) {
                    subLeft = subLeft->_left;
                }
                _node = subLeft; // 更新当前节点
            } else {
                // 无右子树，向上找到第一个不为右子节点的父节点
                Node *parent = _node->_parent;
                while (parent && _node == parent->_right) {
                    _node = parent;
                    parent = parent->_parent;
                }
                _node = parent; // 更新当前节点为其父节点
            }
            return *this;
        }
​
    };
​
    // template <class K,class V>
    template <class K,class T,class KeyOfvalue>
    class  RBTree {
        // typedef RBTreeNode<K,V> Node;
       
        // typedef __RBTreeIterator<T,const T&,const T*> const_iterator
    public:
        typedef __RBTreeIterator<T,T&,T*> iterator;
        typedef RBTreeNode<T> Node;
        iterator begin(){
            Node * cur = _root;
            while(cur && cur->_left){
                cur = cur->_left;
            }
            return iterator(cur);
        }
​
        iterator end(){
            return iterator(nullptr);
        }
        ////////////////////////////////////////////////////////////////////////////
        bool insert(const T& val) {
            // 按照搜索树的顺序进行插入
            if(_root == nullptr) {
                _root = new Node(val);
                _root->_col = BLACK;
                return true;
            }
            KeyOfvalue KOV;
            Node * Cur = _root;
            Node * parent = nullptr;
            while(Cur) {
                if(KOV(Cur->_data) < KOV(val)) {
                    parent = Cur;
                    Cur = Cur->_right;
                }else if(KOV(Cur->_data) > KOV(val)) {
                    parent = Cur;
                    Cur = Cur->_left;
                }else {
                    return false;
                    // 有相同的 K
                }
            }
            Cur = new Node(val);
            Cur->_col = RED; // 新增节点 颜色是RED
            Cur->_parent = parent;
            if(KOV(parent->_data) < KOV(val)) {
                parent->_right = Cur;
            }else {
                parent->_left = Cur;
            }
​
            while(parent && parent->_col == RED) {
                Node * grandfather = parent->_parent;
                if(grandfather->_left == parent) {
                    Node * uncle = grandfather->_right;
                    if(uncle && uncle->_col == RED) {
                        // 情况一  uncle 存在且为红
                        parent->_col = uncle->_col = BLACK;
                        grandfather->_col = RED;
                        // 继续处理
                        Cur = grandfather;
                        parent = Cur->_parent;
                    }
                    else {
                        //情况三  uncle 存在 且为黑
                        //情况二  uncle 不存在
                        if(Cur == parent->_right) {
                            rotateL(parent);
                            swap(parent , Cur);
                        }
                        // 第三种情况 有可能是 第二种变回来的
                        rotateR(grandfather);
                        grandfather->_col = RED;
                        parent->_col = BLACK;
                        break;
                    }
                }else {
​
                    Node * uncle = grandfather->_left;
                    if(uncle && uncle->_col == RED) {
                        // 情况1
                        parent->_col = uncle->_col = RED;
                        grandfather->_col = RED;
​
                        // 继续处理
                        Cur = grandfather;
                        parent = Cur->_parent;
                    }else {
​
                        if(Cur == parent->_left) {
                            rotateR(parent);
                            swap(parent,grandfather);
                        }
                        rotateL(grandfather);
                        grandfather->_col = RED;
                        parent->_col = BLACK;
                        break;
                    }
                }
​
            }
​
            _root->_col = BLACK;  // 最后根都是黑色
​
            return true;
        }
​
        void InOrder()
        {
            _InOrder(_root);
        }
    private:
        Node * _root = nullptr;
​
        void rotateL(Node* parent) {
            Node* newParent = parent->_right;
            if(!newParent)return ;
            parent->_right = newParent->_left;
            if (newParent->_left) {
                newParent->_left->_parent = parent;
            }
​
            newParent->_parent = parent->_parent;
            if (parent->_parent == nullptr) {
                _root = newParent; // 更新根节点
            } else if (parent == parent->_parent->_left) {
                parent->_parent->_left = newParent;
            } else {
                parent->_parent->_right = newParent;
            }
​
            newParent->_left = parent;
            parent->_parent = newParent;
        }
​
       
        void rotateR(Node* parent) {
            Node* newParent = parent->_left;
            parent->_left = newParent->_right;
            if (newParent->_right) {
                newParent->_right->_parent = parent;
            }
​
            newParent->_parent = parent->_parent;
            if (parent->_parent == nullptr) {
                _root = newParent; // 更新根节点
            } else if (parent == parent->_parent->_left) {
                parent->_parent->_left = newParent;
            } else {
                parent->_parent->_right = newParent;
            }
​
            newParent->_right = parent;
            parent->_parent = newParent;
        }
​
    };
​

site logo

Welcome to my blog.

© 2025 云端浮梦