实现红黑树
- 一.基本概念：
- 1.红黑树的概念：
- 2.红黑树的性质：
- 二.实现红黑树：
- 1.基本结构：
- 2.插入节点的多种情况：
- 1.叔叔存在且为红：
- 2.叔叔不存在/存在且为黑(单旋+变色)
- 3.叔叔不存在/存在且为黑(多旋（不是一个单一方向比较长）+变色)
- 4.总体插入代码：
- 3.红黑树的验证：
- 1.验证搜索树：
- 2.验证性质：
- 1.根节点是黑色
- 2. 没有连续的红色节点出现
- 3.每一条路径的黑色节点个数相同
- 4.红黑树和AVL树的比较：
- 1. 随机值判断:
- 1.100
- 2.10000
- 3.1000000
- 4.10000000
- 2.有序值判断:
- 1.100
- 2.10000
- 3.1000000
- 4.10000000
- 三.map和set的封装：
- 1.概念：
- 1.set
- 2.map
- 2.基本结构：
- 1.set
- 2.map
- 3.插入
- 1.set
- 2.map
- 3.总结：
- 4.迭代器实现：
- 1.set
- 2.map
- 3.红黑树部分中实现迭代器的++ -- != *
- 1.实现operator++
- 2.实现operator--
- 5.查找：
- 1.map
- 6.operator[]的重载
- 1.map特有：
- 2.operator[]重载
- 3.insert的优化
一.基本概念：
1.红黑树的概念：
红黑树是一种二叉搜索树，但是在每一个存储节点上面增加了一个成员变量用来记录当前节点的颜色，可以是RED 或者 BLACK 。 通过从根节点到任意一个叶子节点的着色限制，红黑树可以确保没有任何一条路径会比最短路径的两倍还要长，因此红黑树是接近平衡的。
2.红黑树的性质：
1.每一个节点不是红色就是黑色。
2.根节点必须是黑色。
3.如果一个节点是红色它的两个孩子节点是黑色---->不存在连续的红节点。
4.一个根节点出去的所有路径，路径的黑色节点个树必须相同。
5.每一个叶子节点都是黑色的，这个叶子是nullptr不是实际已经开辟好的节点。
二.实现红黑树：
1.基本结构：
2.插入节点的多种情况：
1.叔叔存在且为红：
2.叔叔不存在/存在且为黑(单旋+变色)
1.新增节点是父亲的左边，并且父亲是爷爷的左边。
进行右旋+变色处理
2.新增节点是父亲的右边，并且父亲是爷爷的右边。
进行右旋+变色处理
3.叔叔不存在/存在且为黑(多旋（不是一个单一方向比较长）+变色)
1.新增节点是父亲的右边，并且父亲是爷爷的左边。
进行左旋+右旋+变色处理
2.新增节点是父亲的左边，并且父亲是爷爷的右边。
进行右旋+左旋+变色处理
4.总体插入代码：
template<class T>
class RBTree {
typedef RBTreeNode<T> Node;
public:
//1.插入：
bool insert(pair<T, T> x)
{
Node* newnode = new Node(x);
//1.开始_root == nullptr：
if (_root == nullptr)
{
_root = newnode;
_root->c = BLACK;
return true;
}
//2.有节点的情况下进行插入：
else
{
//2_1:向下找插入位置：
Node* cur = _root;
Node* parent = nullptr;
while (cur)
{
if (x.first > cur->_date.first)
{
parent = cur;
cur = cur->_right;
}
else if (x.first < cur->_date.first)
{
parent = cur;
cur = cur->_left;
}
else
{
return false;
}
}
//2_2:新增节点：
if (x.first > parent->_date.first)
{
parent->_right = newnode;
newnode->_parent = parent;
}
else if (x.first < parent->_date.first)
{
parent->_left = newnode;
newnode->_parent = parent;
}
//确定一下新增节点：
cur = newnode;
//2_3:向上进行调整：
while (parent && parent->c == RED)
{
Node* grandfather = parent->_parent;
if (parent == grandfather->_left)
{
Node* uncle = grandfather->_right;
//1.叔叔存在且为红：
if (uncle && uncle->c == RED)
{
//1-1:变色：
parent->c = BLACK;
uncle->c = BLACK;
grandfather->c = RED;
//1-2：数据更新
cur = grandfather;
parent = cur->_parent;
}
//2.叔叔不存在/存在且为黑：
else
{
//右旋+变色
if (cur == parent->_left)
{
right_turn(grandfather);
grandfather->c = RED;
parent->c = BLACK;
}
//左旋+右旋+变色
else
{
left_turn(parent);
right_turn(grandfather);
grandfather->c = RED;
cur->c = BLACK;
}
break;
}
}
else if (parent == grandfather->_right)
{
Node* uncle = grandfather->_left;
//1.叔叔存在且为红：
if (uncle && uncle->c == RED)
{
//1-1:变色：
parent->c = BLACK;
uncle->c = BLACK;
grandfather->c = RED;
//1-2：数据更新
cur = grandfather;
parent = cur->_parent;
}
//2.叔叔不存在/存在且为黑：
else
{
else
{
//左旋+变色
if (cur == parent->_right)
{
left_turn(grandfather);
grandfather->c = RED;
parent->c = BLACK;
}
//右旋+左旋+变色
else
{
right_turn(parent);
left_turn(grandfather);
grandfather->c = RED;
cur->c = BLACK;
}
break;
}
}
}
}
//处理根节点的特殊情况：
_root->c = BLACK;
return true;
}
}
//左旋：
void left_turn(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
parent->_right = subRL;
//特殊情况的判断：
if (subRL != nullptr)
subRL->_parent = parent;
Node* ppNode = parent->_parent;
subR->_left = parent;
parent->_parent = subR;
//当前的parent是子树还是根
//1.作为根：
if (ppNode == nullptr)
_root = subR;
//2.作为子树考虑左右
else
{
if (ppNode->_left == parent)
ppNode->_left = subR;
else if (ppNode->_right == parent)
ppNode->_right = subR;
subR->_parent = ppNode;
}
}
//右旋：
void right_turn(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
parent->_left = subLR;
//特殊情况的判断：
if (subLR != nullptr)
subLR->_parent = parent;
Node* ppNode = parent->_parent;
subL->_right = parent;
parent->_parent = subL;
//当前的parent是子树还是根
//1.作为根：
if (ppNode == nullptr)
_root = subL;
//2.作为子树考虑左右
else
{
if (ppNode->_left == parent)
ppNode->_left = subL;
else if (ppNode->_right == parent)
ppNode->_right = subL;
subL->_parent = ppNode;
}
}
//中序遍历：
void _Inorder(Node* cur)
{
if (cur == nullptr)
return;
_Inorder(cur->_left);
//cout << "date:" << cur->_date << "平衡因子:" << cur->_bf << endl;
cout << (cur->_date).first << endl;
_Inorder(cur->_right);
}
void Inorder()
{
if (_root == nullptr)
return;
_Inorder(_root);
}
private:
Node* _root=nullptr;
};
3.红黑树的验证：
1.验证搜索树：
1.遍历一个vector进行数据插入
2.打印中序遍历二叉树的结果。
3.观察结果是否有序就可以确定是否是一个搜索树。
void text_1()
{
RBTree<int> T;
vector<int> num = { 8,6,7,11,5,10,13,12,15 };
for (auto e : num)
{
T.insert(make_pair(e,e));
}
T.Inorder();
}
2.验证性质：
1.每一个节点不是红色就是黑色。
2.根节点必须是黑色。
3.如果一个节点是红色它的两个孩子节点是黑色---->不存在连续的红节点。
4.一个根节点出去的所有路径，路径的黑色节点个树必须相同。
5.每一个叶子节点都是黑色的，这个叶子是nullptr不是实际已经开辟好的节点。
1.验证红黑树需要注意不要去验证结论，应该验证控制条件的存在。
2.结论:任意一条路径长度都不会大于最短路径的二倍.
控制条件：
1.根节点是黑色.
2.没有连续的红色节点出现。
3.每一条路径的黑色节点个数相同。
1.根节点是黑色
1.直接去判断根节点的颜色是不是黑色.
2. 没有连续的红色节点出现
1.当前节点的颜色是红节点,父亲是红节点就出现了连续的红节点.
2.出现了连续的红节点就返回false.
3.每一条路径的黑色节点个数相同
1.先去计算出来最左或者最右路径的黑色节点的个数.
2.进行传参在递归过程到叶子节点去判断计算路径和递归路径的黑色节点的个数是否相同.
bool _IsRBTree(Node* cur , int count , int& refnumber)
{
if (cur == nullptr)
{
//记录数据的判断：
if (count == refnumber)
return true;
cout << "当前黑色节点的路径长度不匹配" << endl;
return false;
}
//判断没有连续的红色节点出现：如果当前子节点为红，父节点就不可以是红。
if (cur->c == RED && cur->_parent->c == RED)
{
cout<< "存在连续的红色节点出现问题" << endl;
return false;
}
//记录长度：
if (cur->c == BLACK)
count++;
return _IsRBTree(cur->_left,count,refnumber);
return _IsRBTree(cur->_right, count, refnumber);
}
bool IsRBTree()
{
//1.根节点不是黑色判断：
if (_root->c == RED)
{
cout << "根节点不是黑色" << endl;
return false;
}
//2.计算最左或者最右路径的黑节点个数：
Node* cur = _root;
while (cur)
{
if (cur->c == BLACK)
black++;
cur = cur->_left;
}
int count = 0;
return _IsRBTree(_root,count,black);
}
4.红黑树和AVL树的比较：
1.插入相同的数据比较红黑树和AVL树.
2.比较插入数据的总时间
3.比较插入数据的高度
4.比较插入数据的旋转次数
1. 随机值判断:
void text_4()
{
AVL_Tree<int> T1;
RBTree<int> T2;
vector<int> num;
//生成随机值：
int count = 100;
srand(time(nullptr));
for (int i = 0; i < count; i++)
{
num.push_back(i+rand());
}
int b1 = clock();
for (auto e : num)
{
//cout << "e:" << e << endl;
T1.Insert(make_pair(e, e));
}
int e1 = clock();
for (auto e : num)
{
//cout << "e:" << e << endl;
T2.insert(make_pair(e, e));
}
int e2 = clock();
//插入时间：
cout << "AVLinserttime :" << e1 - b1 << endl;
cout << "RBinserttime :" << e2 - e1 << endl;
//高度：
cout << "AVLhight: " << T1.hight() << endl;
cout << "RBhight: " << T2.hight() << endl;
//旋转次数：
cout << "AVLspin:" << T1.spin() << endl;
cout << "RBspin:" << T2.spin() << endl;
}
1.100
2.10000
3.1000000
4.10000000
2.有序值判断:
void text_4()
{
AVL_Tree<int> T1;
RBTree<int> T2;
vector<int> num;
//生成随机值：
int count = 10000000;
//srand(time(nullptr));
for (int i = 0; i < count; i++)
{
num.push_back(i);
}
int b1 = clock();
for (auto e : num)
{
//cout << "e:" << e << endl;
T1.Insert(make_pair(e, e));
}
int e1 = clock();
for (auto e : num)
{
//cout << "e:" << e << endl;
T2.insert(make_pair(e, e));
}
int e2 = clock();
//插入时间：
cout << "AVLinserttime :" << e1 - b1 << endl;
cout << "RBinserttime :" << e2 - e1 << endl;
//高度：
cout << "AVLhight: " << T1.hight() << endl;
cout << "RBhight: " << T2.hight() << endl;
//旋转次数：
cout << "AVLspin:" << T1.spin() << endl;
cout << "RBspin:" << T2.spin() << endl;
}
1.100
2.10000
3.1000000
4.10000000
三.map和set的封装：
1.概念：
1.set
1.set底层使用红黑树进行数据的存储。
2.进一步的封装是因为BRTree的结构并不适合关联式容器set。
3.set同时需要实现多种容器的方法所以进行进一步的封装BRTree是非常有必要的。
4.进一步的封装有利于控制模板参数类型。
2.map
1.map底层使用红黑树进行数据的存储。
2.进一步的封装是因为BRTree的结构并不适合关联式容器map。
3.map同时需要实现多种容器的方法所以进行进一步的封装BRTree是非常有必要的。
4.进一步的封装有利于控制模板参数类型。
2.基本结构：
1.set
#include"RBTree.h"
namespace sfpy {
template<class T>
class myset {
public:
private:
RBTree<T,T> _t;
};
}
2.map
#include"RBTree.h"
namespace sfpy {
template<class T , class V >
class mymap {
public:
private:
RBTree<T, pair<T, V>> _t;
};
}
3.插入
1.set
如何统一数据大小的比较？
1.在set中实现一个仿函数并且重载operator()提取可以进行比较的数值。
2.直接实现一个内部类并且重载operator()方法并且考虑返回的类型值。
2.map
如何统一数据大小的比较？
1.在set中实现一个仿函数并且重载operator()提取可以进行比较的数值。
2.map中的问题：pair这个数据类型进行大小的比较是first大就大，在first相同的情况下，second大就大，类型本身进行大小的比较是不符合我们当前的要求的，进行仿函数重载提取数据直接进行比较。
3.直接实现一个内部类并且重载operator()方法并且考虑返回的类型值。
3.总结：
1.分别在myset和mymap中去实现两个类并且重载operator()进行比较数据值的提取。
2.在operator(）定义的时候要考虑返回值的类型是否是可以进行比较的数值。
3.优点：通过一个模板参数可以实例化两份不同的树，不需要自己手写。
4.迭代器实现：
1.迭代器本质就是对指针的二次封装，并且重载适合的方法，为什么需要进行二次封装？
2.因为：本身的结构并不可以满足++ – * 等需求！
2.对于链表，顺序表结构，指针和迭代器进行++ – * 操作效果相同不需要非常复杂的进行封装。
3.对于set和map这样的结构底层是通过红黑树进行实现的，就红黑树来说没有好的方法提供给我们去实现++ – * 等操作。
1.set
namespace sfpy {
template<class T>
class myset {
public:
struct bitter {
const T& operator()(const T& x)
{
return x;
}
};
//1.插入：
bool _insert(T x)
{
return _t.insert(x);
}
//2.迭代器：
typedef typename RBTree<T, T, bitter>::_iterator iterator;
iterator begin()
{
return _t.look_left();
}
iterator end()
{
return nullptr;
}
private:
RBTree<T,T, bitter> _t;
};
}
2.map
namespace sfpy {
template<class T , class V >
class mymap {
public:
struct bitter {
const T operator()(const pair<T,V>& x)
{
return x.first;
}
};
//1.插入：
bool _insert(pair<T, V> x)
{
return _t.insert(x);
}
//2.迭代器：
typedef typename RBTree<T, pair<T, V>, bitter>::_iterator iterator;
iterator begin()
{
return _t.look_left();
}
iterator end()
{
return nullptr;
}
private:
RBTree<T, pair<T, V>, bitter> _t;
};
}
3.红黑树部分中实现迭代器的++ – != *
1.实现operator++
实现operator++
1.中序遍历：左子树 根节点 右子树
2.假设：当前节点是8说明左树已经遍历完了
–>判断当前右子树为不为空
---->右子树不是空找右子树的最左节点。
3.假设：当前节点是11，11(cur)是父亲(parent)的右
可以正常回去—>进行cur和parent的更新向上找下一个节点
—>直到parent->left == cur 说明当前的parent节点还没有遍历到。
2.实现operator–
实现operator–
1.++ 找右数的最左节点 ，–找左数的最右节点。
2.其他内容保持和++相反。
template<class T , class ret , class ptr>
struct RBT_Iterator {
typedef RBTreeNode<T> Node;
//返回一个迭代器类型
typedef RBT_Iterator<T,ret,ptr> self;
Node* node;
RBT_Iterator(Node* x = nullptr)
:node(x)
{}
self& operator++()
{
//左 中 右
if (node->_right)
{
Node* cur = node->_right;
//Node* cur = node;
//找当前节点的最左节点：
while (cur->_left)
{
cur = cur->_left;
}
node = cur;
}
//cur->right 没有的！
else
{
Node* cur = node;
Node* parent = cur->_parent;
while (parent && cur == parent->_right)
{
cur = parent;
parent = cur->_parent;
}
node = parent;
}
return *this;
}
self& operator--()
{
//右 中 左
if (node->_left)
{
Node* cur = node->_left;
//找当前节点的最右节点：
while (cur->_right)
{
cur = cur->_right;
}
node = cur;
}
//cur->right 没有的！
else
{
Node* cur = node;
Node* parent = cur->_parent;
while (parent && cur == parent->_left)
{
cur = parent;
parent = cur->_parent;
}
node = parent;
}
return *this;
}
ret operator*()
{
return node->_date;
}
ptr operator->()
{
return &(node->_date);
}
bool operator!=(const self& x)
{
return node != x.node;
}
};
template<class K , class V , class Bitter>
class RBTree {
typedef RBTreeNode<V> Node;
public:
typedef RBT_Iterator<V, const V& ,const V*> _iterator;
//1.插入：
5.查找：
1.我们的set和map在封装红黑树的时候对当前封装的红黑树的类模板进行重新的规划。
2.对于set ：RBTree<T,T, bitter> _t; ，set不需要实现find set存数据所决定。
3. 对于map ==RBTree<T, pair<T, V>, bitter> _t;==主要是为了方便实现find的查找功能。
1.map
//3.查找：
V find(T x)
{
pair<T, V> ret = _t._find(make_pair(x, V()));
return ret.second;
}
//找数据：
V _find(V x)
{
Bitter kot;
Node* cur = _root;
Node* parent = nullptr;
while (cur)
{
if (kot(x) > kot(cur->_date))
{
parent = cur;
cur = cur->_right;
}
else if (kot(x) < kot(cur->_date))
{
parent = cur;
cur = cur->_left;
}
else
{
return cur->_date;
}
}
return V();
}
6.operator[]的重载
1.map特有：
1.operator[]是通过修改insert返回值类型为pair<iterator,bool>类型进行的一个实现：
2.返回值ret接受到返回值，访问迭代器中并且因为迭代器重载了operator->拿到对应的数据。
3.注意：新增节点和查询节点的一个区别，通过新增一个pair类型的数据去进行查询，查询到就就返回查询到的节点的迭代器，查询不到就返回新增。
2.operator[]重载
//4.重载operator[]--->insert进行重写
V& operator[](T x)
{
pair<iterator,bool> ret = _t.insert(make_pair(x,V()));
return ret.first->second;
}
3.insert的优化
//1.插入：
pair<_iterator,bool> insert(V x)
{
Node* newnode = new Node(x);
Bitter kot;
//1.开始_root == nullptr：
if (_root == nullptr)
{
_root = newnode;
_root->c = BLACK;
return make_pair(_iterator(newnode), true);
}
//2.有节点的情况下进行插入：
else
{
//2_1:向下找插入位置：
Node* cur = _root;
Node* parent = nullptr;
while (cur)
{
if (kot(x) > kot(cur->_date))
{
parent = cur;
cur = cur->_right;
}
else if (kot(x) < kot(cur->_date))
{
parent = cur;
cur = cur->_left;
}
else
{
return make_pair(_iterator(cur), false);
}
}
//2_2:新增节点：
if (kot(x) > kot(parent->_date))
{
parent->_right = newnode;
newnode->_parent = parent;
}
else if (kot(x) < kot(parent->_date))
{
parent->_left = newnode;
newnode->_parent = parent;
}
//确定一下新增节点：
cur = newnode;
//2_3:向上进行调整：
while (parent && parent->c == RED)
{
Node* grandfather = parent->_parent;
if (parent == grandfather->_left)
{
Node* uncle = grandfather->_right;
//1.叔叔存在且为红：
if (uncle && uncle->c == RED)
{
//1-1:变色：
parent->c = BLACK;
uncle->c = BLACK;
grandfather->c = RED;
//1-2：数据更新
cur = grandfather;
parent = cur->_parent;
}
//2.叔叔不存在/存在且为黑：
else
{
//右旋+变色
if (cur == parent->_left)
{
right_turn(grandfather);
grandfather->c = RED;
parent->c = BLACK;
}
//左旋+右旋+变色
else
{
left_turn(parent);
right_turn(grandfather);
grandfather->c = RED;
cur->c = BLACK;
}
break;
}
}
else if (parent == grandfather->_right)
{
Node* uncle = grandfather->_left;
//1.叔叔存在且为红：
if (uncle && uncle->c == RED)
{
//1-1:变色：
parent->c = BLACK;
uncle->c = BLACK;
grandfather->c = RED;
//1-2：数据更新
cur = grandfather;
parent = cur->_parent;
}
//2.叔叔不存在/存在且为黑：
else
{
//左旋+变色
if (cur == parent->_right)
{
left_turn(grandfather);
grandfather->c = RED;
parent->c = BLACK;
}
//右旋+左旋+变色
else
{
right_turn(parent);
left_turn(grandfather);
grandfather->c = RED;
cur->c = BLACK;
}
break;
}
}
}
//处理根节点的特殊情况：
_root->c = BLACK;
return make_pair(_iterator(newnode), true);
}
}
