【C++进阶篇】map和set的底层实现：红黑树
·
一：红黑树的概论
1.1：红黑树的概念
红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出俩倍，因而是接近平衡的。
严格平衡VS近似平衡
- 严格平衡：左右高度差不超过1
- 近似平衡：最长路径不超过最短路径的2倍
1.2：红黑树的性质
红黑树性质如下：
- 每个结点不是红色就是黑色
- 根节点是黑色的
- 如果一个节点是红色的，则它的两个孩子结点是黑色的。【不能出现连续的红色结点，即父子结点颜色：黑+黑、黑+红、红+黑】
- 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点。【每条路径都包含相同数量的黑色节点】
- 每个叶子结点都是黑色的(此处的叶子结点指的是空结点)
- 路径：从根节点走到nullptr。
- 最短路径：全黑结点
- 最长路径：一红一黑间隔
即假设每条路径都有N个黑色结点，那么每条路径的结点数量[N, 2*N]之间，最长路径和最短路径使不一定总是存在的。【属于近似平衡】
二：红黑树的模拟
2.1：红黑树的结构
根据红黑树的结构验证其性质：
- 每个结点不是红色就是黑色。
- 根节点是黑色的（13）。
- 一个结点是红色的，那么它的两个孩子结点必定是黑色的。
- 每条路径上的黑色节点数量都是3
- 每个叶子节点（nullptr）都是黑色的。
2.2：红黑树结点的定义与实现
enum Colour
{
red,
black
};
template<class K, class V>
struct RBTreeNode
{
RBTreeNode<K, V>* _left; // 指向左孩子结点
RBTreeNode<K, V>* _right; // 指向右孩子结点
RBTreeNode<K, V>* _parent; // 指向父亲结点
pair<K, V> _kv; // 存储数据的pair的kv模型
Colour _col; // 用来查看该节点的颜色
RBTreeNode(const pair<K, V>& kv)
:_left(nullptr)
,_right(nullptr)
,_parent(nullptr)
,_kv(kv)
,_col(red)
{}
};2.3：红黑树插入操作
红黑树的插入操作：
- 新增插入结点是黑色的，会影响所有的路径，使得该操作变复杂【不可用】
- 新增插入结点是红色的，只会影响父亲。【父亲是黑色的，不需要处理；父亲是红色的，需要处理】
若父亲是红色结点，需要处理【（变色）or（变色 + 旋转）】，关键看“叔叔”
处理时一共有两种情况来调整：
情况一：cur，parent为红，grandfather为黑，uncle存在且为红；
情况二：cur,parent为红，grandfather为黑，uncle不存在/uncle存在且为黑。
template<class K, class V>
class RBTree
{
typedef RBTreeNode<K, V> Node;
public:
bool insert(const pair<K, V>& kv)
{
if (_root == nullptr)
{
_root = new Node(kv);
_root->_col = black;
return true;
}
// 找要插入的位置
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
if (cur->_kv.first < kv.first)
{
// 比根大往右走
parent = cur;
cur = cur->_right;
}
else if (cur->_kv.first > kv.first)
{
parent = cur;
// 比根小往左走
cur = cur->_left;
}
else
{
// 相同退出
return false;
}
}
// 找到要插入的位置了
cur = new Node(kv);
cur->_col = red;
if (parent->_kv.first < kv.first)
{
// 插入parent的右边
parent->_right = cur;
cur->_parent = parent;
}
else
{
// 插入parent的左边
parent->_left = cur;
cur->_parent = parent;
}
// 插入之后开始调整
while (parent && parent->_col == black)
{
Node* grandfather = parent->_parent;
if (grandfather->_left == parent) // uncle在grandparent的右
{
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不存在或者颜色为黑，开始旋转调整
{
if (cur == parent->_left) // 右单旋
{
RotateR(grandfather);
parent->_col = black;
grandfather->_col = red;
}
else // 左右双旋
{
RotateLR(grandfather);
cur->_col = black;
grandfather->_col = red;
}
break;
}
}
else // uncle在grandparent的左
{
Node* uncle = grandfather->_left;
if (uncle && uncle->_col == red)
{
uncle->_col = parent->_col = black;
grandfather->_col = red;
// 向上调整
cur = grandfather;
parent = cur->_parent;
}
else // uncle不存在或者存在且为黑，开始旋转调整
{
if (cur == parent->_right)
{
// 左单旋
RotateL(grandfather);
parent->_col = black;
grandfather->_col = red;
}
else
{
//右左双旋
RotateRL(grandfather);
cur->_col = black;
grandfather->_col = red;
}
break;
}
}
}
_root->_col = black;
return true;
}
private:
// 左单旋
void RotateL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
parent->_right = subRL;
if (subRL)
subRL->_parent = parent;
Node* grandparent = parent->_parent;
parent->_parent = subR;
subR->_left = parent;
if (_root == parent)
{
_root = subR;
subR->_parent = nullptr;
}
else
{
if (grandparent->_left == parent)
grandparent->_left = subR;
else
grandparent->_right = subR;
subR->_parent = grandparent;
}
parent->_bf = subR->_bf = 0;
}
// 右单旋
void RotateR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
parent->_left = subLR;
if (subLR)
subLR->_parent = parent;
Node* grandparent = parent->_parent;
subL->_right = parent;
parent->_parent = subL;
if (_root == parent)
{
_root = subL;
subL->_parent = nullptr;
}
else
{
if (grandparent->_left == parent)
grandparent->_left = subL;
else
grandparent->_right = subL;
subL->_parent = grandparent;
}
parent->_bf = subL->_bf = 0;
}
// 左右单旋
void RotateLR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
int bf = subLR->_bf;
RotateL(parent->_left);
RotateR(parent);
if (bf == 0)
{
parent->_bf = 0;
subLR->_bf = 0;
subL->_bf = 0;
}
else if (bf == 1)
{
parent->_bf = 0;
subLR->_bf = 0;
subL->_bf = -1;
}
else if (bf == -1)
{
subL->_bf = 0;
subLR->_bf = 0;
parent->_bf = 1;
}
else
{
assert(false);
}
}
// 右左单旋
void RotateRL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
int bf = subRL->_bf;
RotateR(parent->_right);
RotateL(parent);
if (bf == 0)
{
// subRL自己就是新增
parent->_bf = subR->_bf = subRL->_bf = 0;
}
else if (bf == -1)
{
// subRL的左子树新增
parent->_bf = 0;
subRL->_bf = 0;
subR->_bf = 1;
}
else if (bf == 1)
{
// subRL的右子树新增
parent->_bf = -1;
subRL->_bf = 0;
subR->_bf = 0;
}
else
{
assert(false);
}
}
private:
Node* _root = nullptr;
};2.4：红黑树其他接口操作
2.4.1：中序遍历
void _inorder(Node* root)
{
if (root == nullptr)
{
return;
}
_inorder(root->_left);
cout << root->_kv.first << " ";
_inorder(root->_right);
}
void inorder()
{
_inorder(_root);
cout << endl;
}2.4.2：红黑树是否平衡
bool Chack(Node* root, int blacknum, int refval)
{
if (root == nullptr)
{
if (blacknum != refval)
{
cout << "存在黑色节点不相等的路径" << endl;
return false;
}
return true;
}
if (root->_col == red && root->_parent->_col == red)
{
cout << "存在右连续的红色结点" << endl;
return false;
}
if (root->_col == black)
++blacknum;
return Chack(root->_left, blacknum, refval)
&& Chack(root->_right, blacknum, refval);
}
bool isbalance()
{
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 Chack(_root, blacknum, refval);
}2.4.3：高度
int _Height(Node* root)
{
if (root == nullptr)
return 0;
int leftHeight = _Height(root->_left);
int rightHeight = _Height(root->_right);
return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}
int Height()
{
return _Height(_root);
}2.4.4：结点个数
size_t _size(Node* root)
{
if (root == nullptr)
return 0;
return _size(root->_left) + _size(root->_right) + 1;
}
size_t size()
{
return _size(_root);
}2.4.5：查找
Node* find(const K& key)
{
Node* cur = _root;
while (cur)
{
if (cur->_kv.first < key)
{
cur = cur->_right;
}
else if (cur->_kv.first > key)
{
cur = cur->_left;
}
else
{
return cur;
}
}
return nullptr;
}三：红黑树与AVL树的比较
红黑树和AVL树都是高效的平衡二叉树，增删改查的时间复杂度都是O(log_2 N)，红黑树不追求绝对平衡，其只需保证最长路径不超过最短路径的2倍，相对而言，降低了插入和旋转的次数，所以在经常进行增删的结构中性能比AVL树更优，而且红黑树实现比较简单，所以实际运用中红黑树更多。
四：红黑树模拟实现STL中的map和set
4.1：模拟map和set时RBTree的变化
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>
struct Tree_Iterator
{
typedef RBTreeNode<T> Node;
typedef Tree_Iterator<T> Self;
Node* _node;
Tree_Iterator(Node* node)
:_node(node)
{}
T& operator*()
{
return _node->_data;
}
T* operator->()
{
return &_node->_data;
}
Self& operator++() // 前置++
{
if (_node->_right)
{
// 下一个就是右子树的最左节点
Node* cur = _node->_right;
while (cur->_left)
{
cur = cur->_left;
}
_node = cur;
}
else
{
// 左子树 根 右子树
// 右为空，往上找孩子是父亲左的那个祖先
Node* cur = _node;
Node* parent = cur->_parent;
while (parent && cur == parent->_right)
{
cur = parent;
parent = cur->_parent;
}
//找到啦
_node = parent;
}
return *this;
}
bool operator!=(const Self& s)
{
return s._node != _node;
}
bool operator==(const Self& s)
{
return _node == s._node;
}
};
// set->RBTree<K, K, SetKeyOfT> _t;
// map->RBTree<K, pair<K, T>, MapKeyOfT> _t;
template<class K, class T, class KeyOfT>
class RBTree
{
typedef RBTreeNode<T> Node;
public:
typedef Tree_Iterator<T> iterator;
iterator beign()
{
Node* cur = _root;
while (cur && cur->_left)
{
cur = cur->_left;
}
return iterator(cur);
}
iterator end()
{
return iterator(nullptr);
}
// 返回的是一个pair
pair<iterator,bool> insert(const T& data)
{
if (_root == nullptr)
{
_root = new Node(data);
_root->_col = black;
return make_pair(iterator(_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(iterator(cur), false);
}
}
// 找到要插入的位置了
cur = new Node(data);
Node* newnode = cur;
cur->_col = red;
if (kot(parent->_data) < kot(data))
{
// 插入parent的右边
parent->_right = cur;
cur->_parent = parent;
}
else
{
// 插入parent的左边
parent->_left = cur;
cur->_parent = parent;
}
// 插入之后开始调整
while (parent && parent->_col == red)
{
Node* grandfather = parent->_parent;
if (grandfather->_left == parent) // uncle在grandparent的右
{
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不存在或者颜色为黑，开始旋转调整
{
if (cur == parent->_left) // 右单旋
{
RotateR(grandfather);
parent->_col = black;
grandfather->_col = red;
}
else // 左右双旋
{
RotateLR(grandfather);
cur->_col = black;
grandfather->_col = red;
}
break;
}
}
else // uncle在grandparent的左
{
Node* uncle = grandfather->_left;
if (uncle && uncle->_col == red)
{
uncle->_col = parent->_col = black;
grandfather->_col = red;
// 向上调整
cur = grandfather;
parent = cur->_parent;
}
else // uncle不存在或者存在且为黑，开始旋转调整
{
if (cur == parent->_right)
{
// 左单旋
RotateL(grandfather);
parent->_col = black;
grandfather->_col = red;
}
else
{
//右左双旋
RotateRL(grandfather);
cur->_col = black;
grandfather->_col = red;
}
break;
}
}
}
_root->_col = black;
return make_pair(iterator(newnode), true);
}
void inorder()
{
_inorder(_root);
cout << endl;
}
bool isbalance()
{
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 Chack(_root, blacknum, refval);
}
int Height()
{
return _Height(_root);
}
size_t size()
{
return _size(_root);
}
Node* find(const K& key)
{
Node* cur = _root;
while (cur)
{
if (cur->_kv.first < key)
{
cur = cur->_right;
}
else if (cur->_kv.first > key)
{
cur = cur->_left;
}
else
{
return cur;
}
}
return nullptr;
}
private:
size_t _size(Node* root)
{
if (root == nullptr)
return 0;
return _size(root->_left) + _size(root->_right) + 1;
}
int _Height(Node* root)
{
if (root == nullptr)
return 0;
int leftHeight = _Height(root->_left);
int rightHeight = _Height(root->_right);
return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}
bool Chack(Node* root, int blacknum, int refval)
{
if (root == nullptr)
{
if (blacknum != refval)
{
cout << "存在黑色节点不相等的路径" << endl;
return false;
}
return true;
}
if (root->_col == red && root->_parent->_col == red)
{
cout << "存在右连续的红色结点" << endl;
return false;
}
if (root->_col == black)
++blacknum;
return Chack(root->_left, blacknum, refval)
&& Chack(root->_right, blacknum, refval);
}
void _inorder(Node* root)
{
if (root == nullptr)
{
return;
}
_inorder(root->_left);
cout << root->_kv.first << " ";
_inorder(root->_right);
}
// 左单旋
void RotateL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
parent->_right = subRL;
if (subRL)
subRL->_parent = parent;
Node* grandparent = parent->_parent;
parent->_parent = subR;
subR->_left = parent;
if (_root == parent)
{
_root = subR;
subR->_parent = nullptr;
}
else
{
if (grandparent->_left == parent)
grandparent->_left = subR;
else
grandparent->_right = subR;
subR->_parent = grandparent;
}
}
// 右单旋
void RotateR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
parent->_left = subLR;
if (subLR)
subLR->_parent = parent;
Node* grandparent = parent->_parent;
subL->_right = parent;
parent->_parent = subL;
if (_root == parent)
{
_root = subL;
subL->_parent = nullptr;
}
else
{
if (grandparent->_left == parent)
grandparent->_left = subL;
else
grandparent->_right = subL;
subL->_parent = grandparent;
}
}
// 左右单旋
void RotateLR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
RotateL(parent->_left);
RotateR(parent);
}
// 右左单旋
void RotateRL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
RotateR(parent->_right);
RotateL(parent);
}
private:
Node* _root = nullptr;
};4.2：红黑树模拟实现STL中的map
#pragma once
#include"RBTree.h"
// map
namespace alin
{
template<class K, class V>
class map
{
public:
struct MapKeyOfT // 获取key数据
{
const K& operator()(const pair<K, V>& kv)
{
return kv.first;
}
};
// 迭代器 + 其他接口函数
typedef typename RBTree_set_map::RBTree<K, pair<K, V>, MapKeyOfT>::iterator iterator;
iterator begin()
{
return _t.beign();
}
iterator end()
{
return _t.end();
}
pair<iterator, bool> insert(const pair<K, V>& kv)
{
return _t.insert(kv);
}
V& operator[](const K& key)
{
pair<iterator, bool> ret = insert(make_pair(key, V()));
return ret.first->second;
}
private:
RBTree_set_map::RBTree<K, pair<K, V>, MapKeyOfT> _t;
};
}
4.3：红黑树模拟实现STL中的set
#include"RBTree.h"
// set
namespace alin
{
template<class K>
class set
{
public:
struct SetKeyOfT // 获取key数据
{
const K& operator()(const K& key)
{
return key;
}
};
// 迭代器 + 其他接口函数
typedef typename RBTree_set_map::RBTree<K, K, SetKeyOfT>::iterator iterator;
iterator begin()
{
return _t.beign();
}
iterator end()
{
return _t.end();
}
pair<iterator, bool> insert(const K& key)
{
return _t.insert(key);
}
private:
RBTree_set_map::RBTree<K, K, SetKeyOfT> _t;
};
}
4.4：测试手搓的map和set
#include"mymap.h"
#include"myset.h"
void test_set()
{
alin::set<int> s;
s.insert(4);
s.insert(1);
s.insert(2);
s.insert(3);
s.insert(2);
s.insert(8);
s.insert(0);
s.insert(12);
s.insert(7);
alin::set<int>::iterator it = s.begin();
while (it != s.end())
{
*it += 1;
cout << *it << " ";
++it;
}
cout << endl;
}
void test_map()
{
alin::map<string, string> dict;
dict.insert(make_pair("sort", "排序"));
dict.insert(make_pair("left", "左边"));
dict.insert(make_pair("right", "右边"));
dict.insert(make_pair("good", "好的"));
dict.insert(make_pair("num", "数字"));
alin::map<string, string>::iterator it = dict.begin();
while (it != dict.end())
{
cout << it->first << ":" << it->second << endl;
++it;
}
cout << endl;
string arr[] = { "苹果","香蕉","苹果","香蕉", "草莓","草莓", "苹果","甜瓜", "苹果","梨子" };
alin::map<string, int> countMap;
for (auto& e : arr)
{
countMap[e]++;
}
for (auto& kv : countMap)
{
cout << kv.first << ":" << kv.second << endl;
}
cout << endl;
alin::map<int,string> countR;
for (auto& e : countMap)
{
countR.insert(make_pair(e.second, e.first));
}
for (auto& kv : countR)
{
cout << kv.first << ":" << kv.second << endl;
}
cout << endl;
}
int main()
{
test_set();
cout << "-------------------------------------" << endl;
test_map();
return 0;
}
// 运行结果：
1 2 3 4 5 8 9 13
-------------------------------------
good:好的
left:左边
num:数字
right:右边
sort:排序
草莓:2
梨子:1
苹果:4
甜瓜:1
香蕉:2
1:梨子
2:草莓
4:苹果上述所有代码均在Gitee网站：CSDN博客汇总/CSDN_红黑树 · 阿林/C++代码仓 - 码云 - 开源中国 (gitee.com)
北京人形旗下天工造物具身智能开源社区，聚焦具身天工与慧思开物两大平台
更多推荐
25
0- 0
已为社区贡献2条内容
所有评论(0)