【C++】用红黑树封装map、set

🕗 发布于 2024-07-14 04:17 c++ java 开发语言 学习方法 数据结构

1. 红黑树

set是K模型，map是KV模型，二者底层都是使用红黑树来实现的，所以我们可以将红黑树设置为模板，即：set、map复用同一个类模板的红黑树。

1.1 模板参数的控制

1.1.1 Value

Value决定你是k模型的set、还是KV模型的map。

map、set的模板参数value.png

enum Color {  //枚举，一一列举出事物具有的所有可能
Red,  //枚举常量，给枚举变量进行赋值
Black,
};

template<class T>//红黑树的节点
struct RBTreeNode {
typedef RBTreeNode<T> Node;

//三叉链-》优点：便于查找孩子、父亲节点
Node* _left;      //该节点的左孩子
Node* _right;    //该节点的右孩子
Node* _parent;  //该节点的父亲，便于向上更新
T _data;
Color _col;

RBTreeNode(const T& data, Color col = Red)  //构造函数
:_data(data)
, _left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _col(col)  //默认新插入节点的颜色为红色
{ }
};

//Value决定你是k模型的set、还是KV模型的map
template<class K, class T, class KeyOfT> 
class RBTree {  
public:
typedef RBTreeNode<T> Node;
};

template<class K>
class set{   //K模型
public:   
       
private:  //set中的key不允许被修改
RBTree<K, const K, SetKeyOfT> _t;  //红黑树对象
};
}

template<class K, class V>
class map {   //KV模型  
public:

private:   //map中的key不允许被修改
RBTree<K, pair<const K, V>, MapKeyOfT> _t;  //红黑树对象
};

};

1.1.2 KeyOfValue

KeyOfT : 取出Value对象中的key。

// KeyOfT : 取出Value对象中的key
template<class K, class T, class KeyOfT> 
class RBTree {  };

struct SetKeyOfT{   
const K& operator()(const K& key)
{
return key;  //key
}
};

struct MapKeyOfT {
const K& operator()(const pair<K, V>& kv)
{
return kv.first;  //pair中的key
}
};

1.2 正向迭代器

1.2.1 构造函数

💡RBTreeIterator(Node* node) ；

RBTreeIterator(Node* node) //构造函数，单参数构造函数支持隐式类型转化
:_node(node)
{ }

Tips : 单参数构造函数支持隐式类型转换 Node*->iterator 。

1.2.2 begin()+end()

💡iterator begin( ) ；

功能：返回红黑树中最左节点(左孩子必为空)的迭代器。
Tips：set、map对象为非const对象，就调用begin()、end()。

iterator begin()  //红黑树最左节点
{ 
Node* subLeft = _root;   
while (subLeft && subLeft->_left)
subLeft = subLeft->_left;

return iterator(subLeft);
}

💡iterator end( ) ；

功能：返回最后一个元素的下一个的迭代器(空指针)。

iterator end()  //空指针 左闭右开[begin,end)
{
return iterator(nullptr);
}

1.2.3 operator++()

/*1.右不为空，下一个为该节点右子树的最左节点 ;
* 2.右为空，说明该节点所在的子树已经访问完了，若该节点为父亲的右，说明该父亲所在的子树也访问完了，继续往上找，
* 直到该节点为父亲的左，则要访问的下一个节点是它的父亲，即：找祖先里面的孩纸 = 父亲左*/
Self& operator++()  //中序 左、根、右
{
if (_node->_right)  //1
{
Node* subLeft = _node->_right;
while (subLeft->_left)
subLeft = subLeft->_left;

_node = subLeft;
}
else  //2
{
Node* cur = _node;
Node* parent = cur->_parent;
while (parent && parent->_left != cur)
{
cur = parent;
parent = cur->_parent;
}
_node = parent;
}
return *this;
}

中序遍历，左、根、右。
情况一：右不为空，下一个为该节点右子树的最左节点 ;
情况二：右为空，说明该节点所在的子树已经访问完了，若该节点为父亲的右，说明该父亲所在的子树也访问完了，继续往上找，直到该节点为父亲的左，则要访问的下一个节点是它的父亲，即：找祖先里面的孩纸 = 父亲左。

1.2.4 operator–()

/*1.左不为空，下一个为该节点左子树的最右节点 ;
* 2.左为空，说明该节点所在的子树已经访问完了，若该节点为父亲的左，说明该父亲所在的子树也访问完了，继续往上找，
* 直到该节点为父亲的右，则要访问的下一个节点是它的父亲，即：找祖先里面的孩纸 = 父亲右*/
Self& operator--() //中序 左、根、右  --与++逻辑相反
{
if (_node->_left)  //1
{
Node* subRight = _node->_left;
while (subRight->_right)
subRight = subRight->_right;

_node = subRight;
}
else  //2
{
Node* cur = _node;
Node* parent = cur->_parent;
while (parent && parent->_right != cur)
{
cur = parent;
parent = cur->_parent;
}
_node = parent;
}
return *this;
}

1.2.5 operator*()

Ref operator*()
{
return _node->_data;
}

1.2.6 operator->()

Ptr operator->() //结构体指针，data为结构体
{
return &_node->_data;
}

1.2.7 operator==()

bool operator==(const Self& rb)
{
return _node == rb._node;
}

1.2.8 operator!=()

bool operator!=(const Self& rb)
{
return _node != rb._node;
}

1.2.9 总代码

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->() //结构体指针，data为结构体
{
return &_node->_data;
}

/*1.右不为空，下一个为该节点右子树的最左节点 ;
* 2.右为空，说明该节点所在的子树已经访问完了，若该节点为父亲的右，说明该父亲所在的子树也访问完了，继续往上找，
* 直到该节点为父亲的左，则要访问的下一个节点是它的父亲，即：找祖先里面的孩纸 = 父亲左*/
Self& operator++()  //中序 左、根、右
{
if (_node->_right)  //1
{
Node* subLeft = _node->_right;
while (subLeft->_left)
subLeft = subLeft->_left;

_node = subLeft;
}
else  //2
{
Node* cur = _node;
Node* parent = cur->_parent;
while (parent && parent->_left != cur)
{
cur = parent;
parent = cur->_parent;
}
_node = parent;
}
return *this;
}

/*1.左不为空，下一个为该节点左子树的最右节点 ;
* 2.左为空，说明该节点所在的子树已经访问完了，若该节点为父亲的左，说明该父亲所在的子树也访问完了，继续往上找，
* 直到该节点为父亲的右，则要访问的下一个节点是它的父亲，即：找祖先里面的孩纸 = 父亲右*/
Self& operator--() //中序 左、根、右  --与++逻辑相反
{
if (_node->_left)  //1
{
Node* subRight = _node->_left;
while (subRight->_right)
subRight = subRight->_right;

_node = subRight;
}
else  //2
{
Node* cur = _node;
Node* parent = cur->_parent;
while (parent && parent->_right != cur)
{
cur = parent;
parent = cur->_parent;
}
_node = parent;
}
return *this;
}

bool operator!=(const Self& rb)
{
return _node != rb._node;
}

bool operator==(const Self& rb)
{
return _node == rb._node;
}
};

1.3 反向迭代器

1.3.1 rbegin()+rend()

💡reverse_iterator rbegin( ) ；

功能：返回红黑树中最右节点(右孩子必为空)的迭代器。

reverse_iterator rbegin()  //红黑树最右节点，因为此处反向迭代器*，是直接调用正向迭代器* [rbegin,erend)
{
Node* subRight = _root;
while (subRight && subRight->_right)
subRight = subRight->_right;

return reverse_iterator(subRight);
}

💡reverse_iterator rend( ) ；

功能：返回第一个元素的前一个的迭代器(空指针)。

reverse_iterator rend()  
{
return reverse_iterator(nullptr);
}

1.3.2 总代码

template<class iterator, class Ref, class Ptr>
struct ReverseIterator  //红黑树的反向迭代器——适配器 begin = rend、end = rbegin
{
typedef ReverseIterator<iterator, Ref, Ptr> Self;  
iterator _it;   //适配器

ReverseIterator(iterator it)
:_it(it)
{ }

Ref operator*()
{
return *_it;
}

Ptr operator->()
{
return &(operator*());  //
}

Self& operator++()
{
--_it;
return *this;
}

Self& operator--()
{
++_it;
return *this;
}

bool operator==(const Self& rb)
{
return _it == rb._it;
}

bool operator!=(const Self& rb)
{
return _it != rb._it;
}
};

1.4 find()

💡iterator find(const K& key) ;

功能：查找。
若key在红黑树中，则返回树中与key值相等元素的迭代器，否则，就返回end( )。

iterator find(const K& key)  //查找  模板参数K的作用
{
KeyOfT kot;

Node* cur = _root;
while (cur)  //先按照二叉搜索树的方式插入
{
if (kot(cur->_data) < key)  //通仿函数对象调用operator()来获取T中的key
cur = cur->_right;
else if (kot(cur->_data) > key)
cur = cur->_left;
else
return iterator(cur);  //找到了
}
return end();  //找不到
}

1.5 insert()

💡pair<iterator，bool> insert(const T& data) ;

功能：向红黑树中插入data。

insert返回值为pair<iterator, bool>,若key(set的key、map的pair的first)在树中存在，因为搜索树中不能出现重复的键值key，所以pair::first指向在树中与key值相等的迭代器，pair::second为false。若key在树中不存在，pair::first指向在树中新插入元素的迭代器，pair::second为true。insert相当于查找。

pair<iterator, bool> insert(const T& data)  //插入  
{   //不能使用引用放回，因为返回值作用域为栈区，传值返回
KeyOfT kot;  //仿函数类创建的对象，对象去调用operator()

Node* parent = nullptr;
Node* cur = _root;
while (cur)  //先按照二叉搜索树的方式插入
    {
    if (kot(cur->_data) < kot(data))  //通仿函数对象调用operator()来获取T中的key值
    {
    parent = cur;
    cur = cur->_right;
    }
    else if (kot(cur->_data) > kot(data))
    {
    parent = cur;
    cur = cur->_left;
    }
    else
    {
    return make_pair(iterator(cur), false);  //插入节点已存在，插入失败，返回在树中与该节点值相同的迭代器
    }
    }

    cur = new Node(data);  //注意 insert

Node* newnode = cur;  //非空树，插入成功，因为要做旋转处理，会导致cur值发生改变，需提前将新节点的位置存储起来

if (parent == nullptr) //空树
{
_root = cur;
_root->_col = Black;  //跟节点为黑
return make_pair(iterator(_root), true);  //空树，插入成功，返回新插入节点在树中的迭代器
}

if (kot(parent->_data) < kot(cur->_data))
{
parent->_right = cur;
}
else
{
parent->_left = cur;
}
cur->_parent = parent;  //记录当前节点的父亲

//更新颜色
//插入结束：1.插入节点的父亲是黑色，因为插入前该树就为红黑树 2.情况一处理完后，cur为根节点，且为黑色
while (parent && parent->_col == Red)
{ //爷爷一定存在，因为c为红，p为红，所以p一定不是根节点，且一定有父节点
Node* grandfather = parent->_parent;
if (parent == grandfather->_left)  //旋转需要确定方向
{
Node* uncle = grandfather->_right;
if (uncle && uncle->_col == Red) //情况一：叔叔存在且为红->无方向(p、u为g的任意边，c为p的任一边)
{  //cur可能为新增节点，也可能一开始为黑色，cur的子树(下一层为红，下一层为新插入节点)在调整过程中将cur由黑变为红
parent->_col = uncle->_col = Black; //p、u变为黑，g变为红
grandfather->_col = Red;

//g可能为根节点(更新结束)，也可能为子树(继续向上更新)
cur = grandfather;
parent = cur->_parent;
}
else  //情况二：叔叔不存在 或者 叔叔存在且为黑
{  //叔叔不存在，cur为新增节点 或 cur原来为黑，经子树调整由黑变红
if (parent->_left == cur)  //左左——右单旋
{
RotateR(grandfather);
parent->_col = Black; //p变为黑，g变为红
grandfather->_col = Red;
}
else    //左右——左右单旋 
{
RotateL(parent);
RotateR(grandfather);
cur->_col = Black;  //c变黑，g变红
grandfather->_col = Red;
}
break;  //更新结束：3.旋转+颜色处理后就是红黑树了
}
}
else
{
Node* uncle = grandfather->_left;
if (uncle && uncle->_col == Red)
{
parent->_col = uncle->_col = Black;
grandfather->_col = Red;

cur = grandfather;
parent = cur->_parent;
}
else
{
if (parent->_right == cur)  //右右——左单旋
{
RotateL(grandfather);
parent->_col = Black;
grandfather->_col = Red;
}
else   //右左——右左单旋
{
RotateR(parent);
RotateL(grandfather);
cur->_col = Black;
grandfather->_col = Red;
}
break;
}
}
}
_root->_col = Black;  //g为根，颜色变为黑，更新结束
return make_pair(iterator(newnode), true);  //情况一，插入节点的父亲为黑，插入结束
}

2. Map

2.1 operator[]

💡V& operator[ ](const K& key) ;

功能：访问与key相对应的value值。即可读又可写。
原理：operator[ ]底层是通过调用insert( )将键值队插入到map中。如果key存在，插入失败，insert返回与map中key值相同元素的迭代器。如果key不存在，插入成功，insert返回在map中新插入元素的迭代器。operator[ ]最后返回与key值相对应的value值的引用。
operator[ ] 具有插入、查找、插入+修改、查找+修改功能。

V& operator[](const K& key) //功能:查找+修改、插入+修改
{
pair<iterator, bool> ret = _t.insert(make_pair(key, V()));
return ret.first->second;
}

3. typename作用

使用域作用限定符(: : )的两种情况：静态变量、类中typedef的类型。
使用typename表示: :后面为类型，不是静态成员

//使用::两种情况：静态变量、类中typedef的类型  typename表示::前面为类型，不是静态成员
typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::iterator iterator;

4. 完整代码

4.1 Map.h

#pragma once
#define _CRT_SECURE_NO_WARNINGS 1

#include"RBTree.h"
#include<string>

namespace zzx {
template<class K, class V>
class map {   //KV模型  
public:

struct MapKeyOfT {
const K& operator()(const pair<K, V>& kv)
{
return kv.first;  //pair中的key
}
};

//使用::两种情况：静态变量、类中typedef的类型  typename表示::前面为类型，不是静态成员
typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::iterator iterator;   //正向迭代器
typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::reverse_iterator reverse_iterator;  //反向迭代器

iterator begin()  
{
return _t.begin();
}

iterator end()  
{
return _t.end();
}

reverse_iterator rbegin()
{
return _t.rbegin();
}

reverse_iterator rend()
{
return _t.rend();
}

iterator find(const K& key)  //查找
{
return _t.find(key);
}

pair<iterator, bool> insert(pair<const K, V>& kv)  //插入
{
return _t.insert(kv);
}

V& operator[](const K& key) //功能:查找+修改、插入+修改
{
pair<iterator, bool> ret = _t.insert(make_pair(key, V()));
return ret.first->second;
}

private:   //map中的key不允许被修改
RBTree<K, pair<const K, V>, MapKeyOfT> _t;  //红黑树对象
};

};

4.2 Set.h

#pragma once
#define _CRT_SECURE_NO_WARNINGS 1

#include"RBTree.h"

namespace zzx{
template<class K>
class set{   //K模型
public:   //仿函数类:比较对象大小，获取对象中的元素—自己手动传递比较逻辑
struct SetKeyOfT{   
const K& operator()(const K& key)
{
return key;  //key
}
};

//使用::两种情况：静态变量、类中typedef的类型  typename表示::后面为类型，不是静态成员
typedef typename RBTree<K, const K, SetKeyOfT>::iterator iterator;   //正向迭代器
typedef typename RBTree<K, const K, SetKeyOfT>::reverse_iterator reverse_iterator;  //反向迭代器

iterator begin()
{
return _t.begin();
}

iterator end()
{
return _t.end();
}

reverse_iterator rbegin()
{
return _t.rbegin();
}

reverse_iterator rend()
{
return _t.rend();
}

iterator find(const K& key)  //查找
{
return _t.find(key);
}

pair<iterator, bool> insert(const K& key)  //插入
{
return _t.insert(key);
}

private:  //set中的key不允许被修改
RBTree<K, const K, SetKeyOfT> _t;  //红黑树对象
};
}

4.3 RBTree.h

#pragma once
#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>

using namespace std;

enum Color {  //枚举，一一列举出事物具有的所有可能
Red,  //枚举常量，给枚举变量进行赋值
Black,
};

template<class T>//红黑树的节点
struct RBTreeNode {
typedef RBTreeNode<T> Node;

//三叉链-》优点：便于查找孩子、父亲节点
Node* _left;      //该节点的左孩子
Node* _right;    //该节点的右孩子
Node* _parent;  //该节点的父亲，便于向上更新
T _data;
Color _col;

RBTreeNode(const T& data, Color col = Red)  //构造函数
:_data(data)
, _left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _col(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->() //结构体指针，data为结构体
{
return &_node->_data;
}

/*1.右不为空，下一个为该节点右子树的最左节点 ;
* 2.右为空，说明该节点所在的子树已经访问完了，若该节点为父亲的右，说明该父亲所在的子树也访问完了，继续往上找，
* 直到该节点为父亲的左，则要访问的下一个节点是它的父亲，即：找祖先里面的孩纸 = 父亲左*/
Self& operator++()  //中序 左、根、右
{
if (_node->_right)  //1
{
Node* subLeft = _node->_right;
while (subLeft->_left)
subLeft = subLeft->_left;

_node = subLeft;
}
else  //2
{
Node* cur = _node;
Node* parent = cur->_parent;
while (parent && parent->_left != cur)
{
cur = parent;
parent = cur->_parent;
}
_node = parent;
}
return *this;
}

/*1.左不为空，下一个为该节点左子树的最右节点 ;
* 2.左为空，说明该节点所在的子树已经访问完了，若该节点为父亲的左，说明该父亲所在的子树也访问完了，继续往上找，
* 直到该节点为父亲的右，则要访问的下一个节点是它的父亲，即：找祖先里面的孩纸 = 父亲右*/
Self& operator--() //中序 左、根、右  --与++逻辑相反
{
if (_node->_left)  //1
{
Node* subRight = _node->_left;
while (subRight->_right)
subRight = subRight->_right;

_node = subRight;
}
else  //2
{
Node* cur = _node;
Node* parent = cur->_parent;
while (parent && parent->_right != cur)
{
cur = parent;
parent = cur->_parent;
}
_node = parent;
}
return *this;
}

bool operator!=(const Self& rb)
{
return _node != rb._node;
}

bool operator==(const Self& rb)
{
return _node == rb._node;
}
};

template<class iterator, class Ref, class Ptr>
struct ReverseIterator  //红黑树的反向迭代器——适配器 begin = rend、end = rbegin
{
typedef ReverseIterator<iterator, Ref, Ptr> Self;  
iterator _it;   //适配器

ReverseIterator(iterator it)
:_it(it)
{ }

Ref operator*()
{
return *_it;
}

Ptr operator->()
{
return &(operator*());  //
}

Self& operator++()
{
--_it;
return *this;
}

Self& operator--()
{
++_it;
return *this;
}

bool operator==(const Self& rb)
{
return _it == rb._it;
}

bool operator!=(const Self& rb)
{
return _it != rb._it;
}
};

//红黑树的模板参数:T决定你是k模型的set、还是KV模型的map ; KeyOfT:取出T对象中的key ; pair比较:先比较first,在比较second
template<class K, class T, class KeyOfT> 
class RBTree {  
public:
typedef RBTreeNode<T> Node;

//正向迭代器
typedef RBTreeIterator<T, T&, T*> iterator;  //普通迭代器
typedef RBTreeIterator<T,const T&, const T*> const_iterator; //const迭代器

//反向迭代器
typedef ReverseIterator<iterator, T&, T*> reverse_iterator;
typedef ReverseIterator<const_iterator, const T&, const T*> const_reverse_iterator;

iterator begin()  //红黑树最左节点
{ 
Node* subLeft = _root;   
while (subLeft && subLeft->_left)
subLeft = subLeft->_left;

return iterator(subLeft);
}

iterator end()  //空指针 左闭右开[begin,end)
{
return iterator(nullptr);
}

const_iterator begin()const  
{
Node* subLeft = _root;
while (subLeft && subLeft->_left)
subLeft = subLeft->_left;

return const_iterator(subLeft);
}

const_iterator end()const
{
return const_iterator(nullptr);
}

reverse_iterator rbegin()  //红黑树最右节点，因为此处反向迭代器*，是直接调用正向迭代器* [rbegin,erend)
{
Node* subRight = _root;
while (subRight && subRight->_right)
subRight = subRight->_right;

return reverse_iterator(subRight);
}

reverse_iterator rend()  
{
return reverse_iterator(nullptr);
}

const_reverse_iterator rbegin()const
{
Node* subRight = _root;
while (subRight && subRight->_right)
subRight = subRight->_right;

return const_reverse_iterator(subRight);
}

const_reverse_iterator rend()const
{
return const_reverse_iterator(nullptr);
}

iterator find(const K& key)  //查找  模板参数K的作用
{
KeyOfT kot;

Node* cur = _root;
while (cur)  //先按照二叉搜索树的方式插入
{
if (kot(cur->_data) < key)  //通仿函数对象调用operator()来获取T中的key
cur = cur->_right;
else if (kot(cur->_data) > key)
cur = cur->_left;
else
return iterator(cur);  //找到了
}

return end();  //找不到
}

void RotateL(Node* parent)  //右右—左单旋
{
Node* subR = parent->_right;
Node* subRL = subR->_left;

Node* pphead = parent->_parent;

parent->_right = subRL;
if (subRL)
subRL->_parent = parent;
subR->_left = parent;
parent->_parent = subR;


if (parent == _root)
{
_root = subR;
subR->_parent = nullptr;
}
else
{
if (pphead->_left == parent)
pphead->_left = subR;
else
pphead->_right = subR;

subR->_parent = pphead;
}
}

void RotateR(Node* parent)  //左左—右单旋
{
Node* subL = parent->_left;
Node* subLR = subL->_right;

Node* pphead = parent->_parent;

parent->_left = subLR;
if (subLR)
subLR->_parent = parent;
subL->_right = parent;
parent->_parent = subL;

if (parent == _root)
{
_root = subL;
subL->_parent = nullptr;
}
else
{
if (pphead->_left == parent)
pphead->_left = subL;
else
pphead->_right = subL;

subL->_parent = pphead;
}
}

void RotateRL(Node* parent)  //右左—先右旋再左旋
{
Node* subR = parent->_right;
Node* subRL = subR->_left;

RotateR(subR);
RotateL(parent);
}

void RotateLR(Node* parent)  //左右—先左旋再右旋
{
Node* subL = parent->_left;
Node* subLR = subL->_right;

RotateL(subL);
RotateR(parent);
}

pair<iterator, bool> insert(const T& data)  //插入  
{   //不能使用引用放回，因为返回值作用域为栈区，传值返回
KeyOfT kot;  //仿函数类创建的对象，对象去调用operator()

Node* parent = nullptr;
Node* cur = _root;
while (cur)  //先按照二叉搜索树的方式插入
{
if (kot(cur->_data) < kot(data))  //通仿函数对象调用operator()来获取T中的key值
{
parent = cur;
cur = cur->_right;
}
else if (kot(cur->_data) > kot(data))
{
parent = cur;
cur = cur->_left;
}
else
{
return make_pair(iterator(cur), false);  //插入节点已存在，插入失败，返回在树中与该节点值相同的迭代器
}
}

cur = new Node(data);  //注意 insert

Node* newnode = cur;  //非空树，插入成功，因为要做旋转处理，会导致cur值发生改变，需提前将新节点的位置存储起来

if (parent == nullptr) //空树
{
_root = cur;
_root->_col = Black;  //跟节点为黑
return make_pair(iterator(_root), true);  //空树，插入成功，返回新插入节点在树中的迭代器
}

if (kot(parent->_data) < kot(cur->_data))
{
parent->_right = cur;
}
else
{
parent->_left = cur;
}
cur->_parent = parent;  //记录当前节点的父亲

//更新颜色
//插入结束：1.插入节点的父亲是黑色，因为插入前该树就为红黑树 2.情况一处理完后，cur为根节点，且为黑色
while (parent && parent->_col == Red)
{ //爷爷一定存在，因为c为红，p为红，所以p一定不是根节点，且一定有父节点
Node* grandfather = parent->_parent;
if (parent == grandfather->_left)  //旋转需要确定方向
{
Node* uncle = grandfather->_right;
if (uncle && uncle->_col == Red) //情况一：叔叔存在且为红->无方向(p、u为g的任意边，c为p的任一边)
{  //cur可能为新增节点，也可能一开始为黑色，cur的子树(下一层为红，下一层为新插入节点)在调整过程中将cur由黑变为红
parent->_col = uncle->_col = Black; //p、u变为黑，g变为红
grandfather->_col = Red;

//g可能为根节点(更新结束)，也可能为子树(继续向上更新)
cur = grandfather;
parent = cur->_parent;
}
else  //情况二：叔叔不存在 或者 叔叔存在且为黑
{  //叔叔不存在，cur为新增节点 或 cur原来为黑，经子树调整由黑变红
if (parent->_left == cur)  //左左——右单旋
{
RotateR(grandfather);
parent->_col = Black; //p变为黑，g变为红
grandfather->_col = Red;
}
else    //左右——左右单旋 
{
RotateL(parent);
RotateR(grandfather);
cur->_col = Black;  //c变黑，g变红
grandfather->_col = Red;
}
break;  //更新结束：3.旋转+颜色处理后就是红黑树了
}
}
else
{
Node* uncle = grandfather->_left;
if (uncle && uncle->_col == Red)
{
parent->_col = uncle->_col = Black;
grandfather->_col = Red;

cur = grandfather;
parent = cur->_parent;
}
else
{
if (parent->_right == cur)  //右右——左单旋
{
RotateL(grandfather);
parent->_col = Black;
grandfather->_col = Red;
}
else   //右左——右左单旋
{
RotateR(parent);
RotateL(grandfather);
cur->_col = Black;
grandfather->_col = Red;
}
break;
}
}
}
_root->_col = Black;  //g为根，颜色变为黑，更新结束
return make_pair(iterator(newnode), true);  //情况一，插入节点的父亲为黑，插入结束
}

private:
Node* _root = nullptr;
};

原文地址：https://blog.csdn.net/m0_74808907/article/details/139543148

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：云端日历同步大师：iCloud让工作与生活井井有条
下一篇：【Rust】——【面向对象语言的特征】

leetcode289:生命游戏
根据，简称为，是英国数学家约翰·何顿·康威在 1970 年发明的细胞自动机。给定一个包含m × n个格子的面板，每一个格子都可以看成是一个细胞。每个细胞都具有一个初始状态：1即为（live），或0即为
阅读更多2024-10-20
MongoDB数据恢复
注意：两个MongoDB的版本要一致，本文使用的是mongo:4.2.24。先把K8S上面的MongoDB 容器停止（可以把副本改成0）。1、将容器挂载MongoDB的数据目录备份到本地。经常是数据文
阅读更多2024-10-20
C#中实现事务
C#中实现事务
阅读更多2024-10-20
【LeetCode每日一题】——560.和为 K 的子数组
给你一个整数数组 nums 和一个整数 k ，请你统计并返回该数组中和为 k 的子数组的个数。子数组是数组中元素的连续非空序列。
阅读更多2024-10-20
「漏洞复现」满客宝智慧食堂系统 selectUserByOrgId 未授权访问漏洞
请勿利用文章内的相关技术从事非法测试，由于传播、利用此文所提供的信息而造成的任何直接或者间接的后果及损失，均由使用者本人负责，作者不为此承担任何责任。工具来自网络，安全性自测，如有侵权请联系删除。本次
阅读更多2024-10-20
React面试题目（从基本到高级）
React前端面试常见题目涵盖了React的基础概念、组件、状态管理、生命周期、性能优化等多个方面。
阅读更多2024-10-20
12.个人博客系统（Java项目基于spring和vue）
1 在校学习的学生，可用于日常学习使用或是毕业设计使用 2 毕业一到两年的开发人员，用于锻炼自己的独立功能模块设计能力，增强代码编写能力。 3 亦可以部署为商化项目使用。 4 需要完整资料及源码
阅读更多2024-10-20
YoloV8改进策略：注意力改进|DeBiFormer，可变形双级路由注意力|引入DeBiLevelRoutingAttention注意力模块（全网首发）
本次改进的核心在于将DeBiLevelRoutingAttention模块嵌入到YoloV8的主干网络中，具体位置是在SPPF（Spatial Pyramid Pooling Fast）模块之后。这一
阅读更多2024-10-20
word取消自动单词首字母大写
情况说明：在word输入单词后首字母会自动变成大写取消单词首字母大写步骤：（1）点击菜单栏文件（2）点击“更多”——>“选项”（3）点击“校对”——>“自动更正选项”（4）取消“句首字母大
阅读更多2024-10-20
web前端网页用户注册页面
【代码】web前端网页用户注册页面。
阅读更多2024-10-20