红黑树源代码（进阶与细节解释）
目录
看完前两篇的文章，相信对于红黑树有了一定的了解，知道红黑树是怎么样子进行插入的，是怎么样进行查找的，知道了底层是怎么样子的，知道了其与AVL树，二叉搜索树有什么区别了。
但是对于set，map的底层又全是红黑树，set与map的区别就是其键值对一个是k，k型，一个是k，v型的，所以就有了封装，（对于封装后面会讲解什么是封装）二者底层全是同一份的红黑树，但是前面两篇文章的红黑树要不只能使用与k，k型，要不就是k，v型，所以就要对红黑树的源代码进行修改，进行细节上的修饰与进阶。
对于结点的修改
对于此其实不需要进行特别的修改，但是要注意这里的T，如果要是对应的set，那么他就是K，如果是map那么他就是pair<k,v>。
enum Colour
{
RED,
BLACK,
};
template<class T>
struct RBTreeNode
{
RBTreeNode<T>* _left;
RBTreeNode<T>* _right;
RBTreeNode<T>* _parent;
T _data;
Colour _col;
RBTreeNode(const T& data)
: _left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _data(data)
, _col(RED)
{}
};红黑树模板参数的控制
我们都知道，set是KK模型的容器，而map是KV模型的容器，那我们如何用一棵KV模型的红黑树同时实现map和set呢？
这里我们就需要控制map和set传入底层红黑树的模板参数，为了与原红黑树的模板参数进行区分，我们将红黑树第二个模板参数的名字改为T。
template<class K, class T>
class RBTree这里的T也就是对应的结点设置的T，上面也说了，set对应的是K，map是pair<k,v>。
那么下面就看看set容器与map容器中的传的模板参数吧。
set
template<class K>
class set
{
public:
//...
private:
RBTree<K, K> _t;
};map
template<class K, class V>
class map
{
public:
//...
private:
RBTree<K, pair<K, V>> _t;
};那能不能不要红黑树的第一个模板参数，只保留第二个模板参数呢？
乍眼一看好像是可以的，因为此时红黑树的第二个模板参数当中也是有键值Key的，但实际上红黑树的第一个模板参数是不能省略的。
对于set容器来说，省略红黑树的第一个参数当然没问题，因为set传入红黑树的第二个参数与第一个参数是一样的。但是对于map容器来说就不行了，因为map容器所提供的接口当中有些是只要求给出键值Key的，比如find和erase。
红黑树结点当中存储的数据
现在红黑树的模板参数变成了K和T，那么红黑树结点当中存储的应该是什么呢？
前面说到，由于上层容器的不同，底层红黑树当中的K和T也是不同的：
- set容器：K和T都代表键值Key。
- map容器：K代表键值Key，T代表由Key和Value构成的键值对。
对于set容器来说，底层红黑树结点当中存储K和T都是一样的，但是对于map容器来说，底层红黑树就只能存储T了。由于底层红黑树并不知道上层容器到底是map还是set，因此红黑树的结点当中直接存储T就行了。
这样一来，当上层容器是set的时候，结点当中存储的是键值Key；当上层容器是map的时候，结点当中存储的就是<Key, Value>键值对。
所以说其实结点的设置其实没有太大的修改，还是与原本还差不多。
对于insert函数的细节修改
在做完上面的修改后，原本的代码如果在运行下，是会有些问题的，（问题是在封装出现）这里问题是什么就不多说了，
修改起来也是很简单
只需要把其返回值修改为如此就可以。
然后第一个参数就是结点指针，第二个是bool值，插入成功返回true，失败false。
迭代器的代码
对于解决迭代器的问题，首先就是要添加一个迭代器类，然后再解决迭代器的++/--，对于红黑树的++，--。用语言来说是很简便的。
迭代器类的添加
template<class T, class Ref, class Ptr>
struct __TreeIterator
{
typedef RBTreeNode<T> Node;
typedef __TreeIterator<T, Ref, Ptr> Self;
Node* _node;
__TreeIterator(Node* node)
:_node(node)
{}
Ref operator*()
{
return _node->_data;
}
Ptr operator->()
{
return &_node->_data;
}
};
template<class K, class T>
class RBTree
{
typedef RBTreeNode<T> Node;
public:
typedef __TreeIterator <T, T&, T*> iterator;
typedef __TreeIterator <T, const T&, const T*> const_iterator;
//......
private:
Node* _root = nullptr;
};迭代器的++
核心：中序的下一个
- it指向的节点，右子树不为空，下一个就是右子树的最左节点。
- it指向的节点，右子树为空，it所在的子树全已访问完了，那么需要往上找孩子是父亲做节点的那个祖先。
迭代器的--
- it的左子树不为空，下一个就为左子树的最有节点。
- it的左子树为空，沿着根找孩子是父亲右节点的那个祖先。
代码展示：
Self& operator--()
{
//走的是中序 左 根 右
if (_node->_left)
{
//左不为空，下一个就是左子树的最右
Node* cur = _node->_left;
while (cur->_right)
{
cur = cur->_right;
}
_node = cur;
}
else
{
//左为空，没根找孩子是父亲右的那个祖先
Node* cur = _node;
Node* parent = cur->_parent;
while (parent && cur == parent->_left)
{
cur = parent;
parent = parent->_parent;
}
_node = parent;
}
return *this;
}
Self& operator++()
{
//走的是中序 左 根 右
if (_node->_right)
{
//右子树不为空，下一个就是右子树的最左结点
Node* cur = _node->_right;
while (cur->_left)
{
cur = cur->_left;
}
_node = cur;
}
else
{
//右子树为空，it所在全已访问完，下一个就是往上找左（孩子是父亲左的那个祖先）
Node* cur = _node;
Node* parent = cur->_parent;
while (parent && cur == parent->_right)
{
cur = parent;
parent = parent->_parent;
}
_node = parent;
}
return *this;
}正向迭代器的代码
template<class T, class Ref, class Ptr>
struct __TreeIterator
{
typedef RBTreeNode<T> Node;
typedef __TreeIterator<T, Ref, Ptr> Self;
Node* _node;
__TreeIterator(Node* node)
:_node(node)
{}
Ref operator*()
{
return _node->_data;
}
Ptr operator->()
{
return &_node->_data;
}
Self& operator--()
{
//走的是中序 左 根 右
if (_node->_left)
{
//左不为空，下一个就是左子树的最右
Node* cur = _node->_left;
while (cur->_right)
{
cur = cur->_right;
}
_node = cur;
}
else
{
//左为空，没根找孩子是父亲右的那个祖先
Node* cur = _node;
Node* parent = cur->_parent;
while (parent && cur == parent->_left)
{
cur = parent;
parent = parent->_parent;
}
_node = parent;
}
return *this;
}
Self& operator++()
{
//走的是中序 左 根 右
if (_node->_right)
{
//右子树不为空，下一个就是右子树的最左结点
Node* cur = _node->_right;
while (cur->_left)
{
cur = cur->_left;
}
_node = cur;
}
else
{
//右子树为空，it所在全已访问完，下一个就是往上找左（孩子是父亲左的那个祖先）
Node* cur = _node;
Node* parent = cur->_parent;
while (parent && cur == parent->_right)
{
cur = parent;
parent = parent->_parent;
}
_node = parent;
}
return *this;
}
bool operator!=(const Self& s)
{
return _node != s._node;
}
bool operator==(const Self& s)
{
return _node == s._node;
}
};
对于迭代器的最后一步就是添加上begin（），end（）函数。
红黑树代码全部展示：
#pragma once
#include<iostream>
#include<vector>
#include<string>
using namespace std;
enum Colour
{
RED,
BLACK,
};
template<class T>
struct RBTreeNode
{
RBTreeNode<T>* _left;
RBTreeNode<T>* _right;
RBTreeNode<T>* _parent;
T _data;
Colour _col;
RBTreeNode(const T& data)
: _left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _data(data)
, _col(RED)
{}
};
template<class T, class Ref, class Ptr>
struct __TreeIterator
{
typedef RBTreeNode<T> Node;
typedef __TreeIterator<T, Ref, Ptr> Self;
Node* _node;
__TreeIterator(Node* node)
:_node(node)
{}
Ref operator*()
{
return _node->_data;
}
Ptr operator->()
{
return &_node->_data;
}
Self& operator--()
{
//走的是中序 左 根 右
if (_node->_left)
{
//左不为空，下一个就是左子树的最右
Node* cur = _node->_left;
while (cur->_right)
{
cur = cur->_right;
}
_node = cur;
}
else
{
//左为空，没根找孩子是父亲右的那个祖先
Node* cur = _node;
Node* parent = cur->_parent;
while (parent && cur == parent->_left)
{
cur = parent;
parent = parent->_parent;
}
_node = parent;
}
return *this;
}
Self& operator++()
{
//走的是中序 左 根 右
if (_node->_right)
{
//右子树不为空，下一个就是右子树的最左结点
Node* cur = _node->_right;
while (cur->_left)
{
cur = cur->_left;
}
_node = cur;
}
else
{
//右子树为空，it所在全已访问完，下一个就是往上找左（孩子是父亲左的那个祖先）
Node* cur = _node;
Node* parent = cur->_parent;
while (parent && cur == parent->_right)
{
cur = parent;
parent = parent->_parent;
}
_node = parent;
}
return *this;
}
bool operator!=(const Self& s)
{
return _node != s._node;
}
bool operator==(const Self& s)
{
return _node == s._node;
}
};
template<class K,class T, class KeyOfT>
class RBTree
{
typedef RBTreeNode<T> Node;
public:
typedef __TreeIterator <T, T&, T*> iterator;
typedef __TreeIterator <T,const T&,const T*> const_iterator;
iterator begin()
{
Node* cur = _root;
while (cur && cur->_left)
{
cur = cur->_left;
}
return iterator(cur);
}
iterator end()
{
return iterator(nullptr);
}
const_iterator begin() const
{
Node* cur = _root;
while (cur && cur->_left)
{
cur = cur->_left;
}
return const_iterator(cur);
}
const_iterator end() const
{
return const_iterator(nullptr);
}
pair<Node*, bool> Insert(const T& data)
{
if (_root == nullptr)
{
_root = new Node(data);
_root->_col = BLACK;
return make_pair(_root, true);;
}
Node* parent = nullptr;
Node* cur = _root;
KeyOfT kot;
while (cur)
{
if (kot(cur->_data) < kot(data))
{
parent = cur;
cur = cur->_right;
}
else if (kot(cur->_data) > kot(data))
{
parent = cur;
cur = cur->_left;
}
else
{
return make_pair(cur, false);;
}
}
cur = new Node(data);
Node* newnode = cur;
//默认结点颜色为红色
if (kot(parent->_data) < kot(data))
{
parent->_right = cur;
cur->_parent = parent;
}
else
{
parent->_left = cur;
cur->_parent = parent;
}
while (parent && parent->_col == RED)
{
Node* grandfather = parent->_parent;
//大前提
//parent在左
if (parent == grandfather->_left)
{
Node* uncle = grandfather->_right;
//Node* uncle = parent->_right;//错误二
if (uncle && uncle->_col == RED)
{
//情景一：cur->红，parent->红，grandfather->黑，uncle存在且为红
// g
// p u
// c
//
//解决：p，u改为黑，g改为红，最后g为红所以，要继续向上调整
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
cur = grandfather;
parent = cur->_parent;
}
else
{
if (cur == parent->_left)
{
//情景二：cur->红，parent->红，grandfather->黑，uncle不存在/为黑
// g
// p u
// c
//
// 解决：对g右单旋，p改为黑，g改为红，最后g为黑所以，直接break
RotateR(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
else
{
//情景三：cur->红，parent->红，grandfather->黑，uncle不存在/为黑
// g
// p u
// c
// 解决：对p左单旋，后变为情景二。
RotateL(parent);
RotateR(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
else//情景大概反着来
{
//1 uncle
Node* uncle = grandfather->_left;//错误一
//Node* uncle = parent->_right;//错误一
if (uncle && uncle->_col == RED)
{
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
cur = grandfather;
parent = cur->_parent;
}
else
{
if (cur == parent->_right)//2
{
RotateL(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
else//3
{
RotateR(parent);
RotateL(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
}
//最后
_root->_col = BLACK;
return make_pair(newnode, true);;
}
void RotateL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
parent->_right = subRL;
subR->_left = parent;
Node* parentParent = parent->_parent;
parent->_parent = subR;
if (subRL)
subRL->_parent = parent;
if (_root == parent)
{
_root = subR;
subR->_parent = nullptr;
}
else
{
if (parentParent->_left == parent)
{
parentParent->_left = subR;
}
else
{
parentParent->_right = subR;
}
subR->_parent = parentParent;
}
}
void RotateR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
parent->_left = subLR;
if (subLR)
subLR->_parent = parent;
Node* parentParent = parent->_parent;
subL->_right = parent;
parent->_parent = subL;
if (_root == parent)
{
_root = subL;
subL->_parent = nullptr;
}
else
{
if (parentParent->_left == parent)
{
parentParent->_left = subL;
}
else
{
parentParent->_right = subL;
}
subL->_parent = parentParent;
}
}
iterator Find(const K& key)
{
Node* cur = _root;
KeyOfT kot;
while (cur)
{
if (kot(cur->_data) < key)
{
cur = cur->_right;
}
else if (kot(cur->_data) > key)
{
cur = cur->_left;
}
else
{
return iterator(cur);
}
}
return end();
}
void InOrder()
{
_InOrder(_root);
cout << endl;
}
void _InOrder(Node* root)
{
if (root == nullptr)
return;
_InOrder(root->_left);
cout << kof(root->_data) << " ";
_InOrder(root->_right);
}
bool Check(Node* root, int blacknum, const int refVal)
{
if (root == nullptr)
{
if (refVal != blacknum)
{
cout << "存在黑色节点数量不相等的路径" << endl;
return false;
}
return true;
}
if (root->_col == RED)
{
if (root->_parent->_col == RED)
{
cout << "有连续的红色节点" << endl;
return false;
}
}
if (root->_col == BLACK)
{
++blacknum;
}
return Check(root->_left, blacknum, refVal)
&& Check(root->_right, blacknum, refVal);
}
bool IsBalance()
{
//1:是否存在 红-红
//每条路径黑色结点是否相同个数
//最长的不超过最短的二倍
//根，叶子为黑
if (_root == nullptr)
return true;
if (_root->_col == RED)
return false;
int refVal = 0;
Node* cur = _root;
while (cur)
{
if (cur->_col == BLACK)
{
++refVal;
}
cur = cur->_left;
}
int blacknum = 0;
return Check(_root, blacknum, refVal);
}
private:
Node* _root = nullptr;
};下一篇文章就开始进行封装的解释。
原文地址：https://blog.csdn.net/2301_81265915/article/details/142764353
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！