一.RBTree(红黑树)前言
创新互联-专业网站定制、快速模板网站建设、高性价比大悟网站开发、企业建站全套包干低至880元,成熟完善的模板库,直接使用。一站式大悟网站制作公司更省心,省钱,快速模板网站建设找我们，业务覆盖大悟地区。费用合理售后完善，10余年实体公司更值得信赖。
map和set容器的底层使用的红黑树, set只存储值, map存储键值对
为了体现复用思想, 红黑树存储类型统一为K/T模型, 如果是set实现T则传K, map实现T则传pair
再通过仿函数KeyOfT来取到T中的K类型对象key
注: 以下只是模拟实现的迭代器/插入功能
#define _CRT_SECURE_NO_WARNINGS 1
#pragma once
enum Color
{
RED,
BLACK
};
templatestruct RBTreeNode
{
RBTreeNode* _left;
RBTreeNode* _right;
RBTreeNode* _parent;
Color _col;
T _val;
//构造
RBTreeNode(const T& val)
:_left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _col(RED)//默认添加的新节点为红色
, _val(val)
{}
};
templatestruct Iterator
{
typedef RBTreeNodeNode;
typedef IteratorSelf;
Iterator(Node* node)
:_node(node)
{}
Ref operator*()
{
return _node->_val;
}
Ptr operator->()
{
//return &(_node->_val);
return &(*Iterator(_node));
}
bool operator==(const Self& val)const
{
return _node == val._node;
}
bool operator!=(const Self& val)const
{
return _node != val._node;
}
//前置++
Self& operator++()
{
if (_node->_right != nullptr)
{
//找右节点为根节点的最左节点
Node* left = _node->_right;
while (left->_left != nullptr)
{
left = left->_left;
}
_node = left;
}
else
{
Node* parent = _node->_parent;
Node* cur = _node;
//如果当前是父的左,说明还没走过,下一步要走到父;
//如果当前是父的右,说明已经走过了,下一步循环判断父是爷的左还是右,重复这个过程
while (parent && parent->_right == cur)
{
cur = parent;
parent = parent->_parent;
}
//出循环说明1.parent为nullptr说明到了end()2.当前是父的左
//结论:下一步都要走到parent
_node = parent;
}
return *this;
}
//前置--
//与前置++逻辑逆置
Self& operator--()
{
if (_node->_left != nullptr)
{
Node* right = _node->_left;
while (right->_right != nullptr)
{
right = right->_right;
}
_node = right;
}
else
{
Node* parent = _node->_parent;
Node* cur = _node;
while (parent && cur == parent->_left)
{
cur = parent;
parent = parent->_parent;
}
_node = parent;
}
return *this;
}
Node* _node;
};
templateclass RBTree
{
public:
typedef RBTreeNodeNode;
typedef Iteratoriterator;
iterator begin()
{
Node* cur = root;
while (cur && cur->_left != nullptr)
{
cur = cur->_left;
}
return iterator(cur);
}
iterator end()
{
return iterator(nullptr);
}
pairinsert(const T& val)
{
KeyOfT key;
if (root == nullptr)
{
//如果此时为空树
root = new Node(val);
//将根节点修正为黑色
root->_col = BLACK;
return make_pair(iterator(root), true);
}
Node* cur = root;
Node* parent = nullptr;//cur的父节点
while (cur)
{
if (key(cur->_val) >key(val))
{
parent = cur;
cur = cur->_left;
}
else if (key(cur->_val)< key(val))
{
parent = cur;
cur = cur->_right;
}
else
{
//如果插入的节点是重复值, 则插入失败
return make_pair(iterator(cur), false);
}
}
cur = new Node(val);
if (key(parent->_val) >key(cur->_val))
{
parent->_left = cur;
}
else if (key(parent->_val)< key(cur->_val))
{
parent->_right = cur;
}
cur->_parent = parent;
//以上为插入节点
//-------------------------------------------------------
//以下为调整为红黑树
//因为默认插入的节点为红色,所以如果出现了两个连续为红的节点就需要处理
while (parent && parent->_col == RED)
{
Node* grandfather = parent->_parent;
Node* uncle = nullptr;
//确定叔叔节点的位置
if (grandfather->_left == parent)
{
uncle = grandfather->_right;
}
else//grandfather->_right == parent
{
uncle = grandfather->_left;
}
//将分为三种情况
//1.父节点为红,叔叔节点存在且为红(变色 + 向上迭代)
//2/3.父节点为红,叔叔节点不存在或者存在且为黑(旋转 + 变色)
if (uncle && uncle->_col == RED)//情况一
{
//父变黑,叔叔变黑,祖父变红->向上迭代
parent->_col = BLACK;
uncle->_col = BLACK;
grandfather->_col = RED;
cur = grandfather;
parent = cur->_parent;
}
else//情况二/三
{
//情况二
// g
// p u
// c
if (uncle == grandfather->_right && cur == parent->_left)
{
//右单旋
RotateR(grandfather);
//
parent->_col = BLACK;
grandfather->_col = RED;
break;
}
// g
// u p
// c
else if (uncle == grandfather->_left && cur == parent->_right)
{
//左单旋
RotateL(grandfather);
//
parent->_col = BLACK;
grandfather->_col = RED;
break;
}
//情况三
// g
// u p
// c
else if (uncle == grandfather->_left && cur == parent->_left)
{
//左双旋
RotateRL(grandfather);
//
grandfather->_col = RED;
cur->_col = BLACK;
break;
}
// g
// p u
// c
else if (uncle == grandfather->_right && cur == parent->_right)
{
//右双旋
RotateLR(grandfather);
//
grandfather->_col = RED;
cur->_col = BLACK;
break;
}
else
{
cout<< "不存在这种情况"<< endl;
exit(-1);
}
}
}
root->_col = BLACK;
return make_pair(iterator(cur), true);
}
void inorder()
{
_inorder(root);
}
bool isRBTree()
{
if (root->_col == RED)
{
cout<< "出错: 根节点为红"<< endl;
return false;
}
//判断是否有连续红节点,且每条路径的黑节点是否相等
int benchmark = 0;//算出最左路径的黑节点个数
Node* cur = root;
while (cur)
{
if (cur->_col == BLACK)
{
++benchmark;
}
cur = cur->_left;
}
return _isRBTree(root, 0, benchmark);
}
private:
//四种旋转
void RotateL(Node* prev)
{
Node* subR = prev->_right;
Node* subRL = subR->_left;
Node* ppNode = prev->_parent;
prev->_right = subRL;
if (subRL)
{
subRL->_parent = prev;
}
subR->_left = prev;
prev->_parent = subR;
if (root == prev)
{
root = subR;
}
else
{
if (ppNode->_left == prev)
{
ppNode->_left = subR;
}
else
{
ppNode->_right = subR;
}
}
subR->_parent = ppNode;
}
void RotateR(Node* prev)
{
Node* subL = prev->_left;
Node* subLR = subL->_right;
Node* ppNode = prev->_parent;
subL->_right = prev;
prev->_parent = subL;
prev->_left = subLR;
if (subLR)
{
subLR->_parent = prev;
}
if (root == prev)
{
root = subL;
}
else
{
if (ppNode->_left == prev)
{
ppNode->_left = subL;
}
else
{
ppNode->_right = subL;
}
}
subL->_parent = ppNode;
}
void RotateRL(Node* prev)
{
//先右旋, 再左旋
RotateR(prev->_right);
RotateL(prev);
}
void RotateLR(Node* prev)
{
//先左旋, 再右旋
RotateL(prev->_left);
RotateR(prev);
}
void _inorder(Node* root)
{
if (root)
{
_inorder(root->_left);
cout<< root->_kv.first<< "--"<< root->_kv.second<< endl;
_inorder(root->_right);
}
}
bool _isRBTree(Node* root, int blackNum, int benchmark)
{
if (root == nullptr)//走到空节点
{
if (benchmark == blackNum)
{
//for debug
//cout<< blackNum<< endl;
return true;
}
else
{
//for debug
//cout<< blackNum<< endl;
cout<< "不是所有路径的黑色节点个数都相同"<< endl;
return false;
}
}
if (root->_col == BLACK)
{
++blackNum;
}
//判断是否有连续的红节点
if (root->_col == RED && root->_parent->_col == RED)
{
cout<< "出现了连续的红色节点"<< endl;
return false;
}
return _isRBTree(root->_left, blackNum, benchmark)
&& _isRBTree(root->_right, blackNum, benchmark);
}
Node* root = nullptr;
}; #define _CRT_SECURE_NO_WARNINGS 1
#include"RBTree.h"
templateclass Set
{
public:
struct SetKeyOfT
{
const K& operator()(const K& key)
{
return key;
}
};
typedef typename RBTree::iterator iterator;
pairinsert(const K& key)
{
return _t.insert(key);
}
iterator begin()
{
return _t.begin();
}
iterator end()
{
return _t.end();
}
private:
RBTree_t;
}; #define _CRT_SECURE_NO_WARNINGS 1
#include"RBTree.h"
templateclass Map
{
public:
struct MapKeyOfT
{
const K& operator()(const pair& kv)
{
return kv.first;
}
};
typedef typename RBTree, MapKeyOfT>::iterator iterator;
pairinsert(const pair& kv)
{
return _t.insert(kv);
}
V& operator[](const K& key)
{
pairret = insert(make_pair(key, V()));
return ret.first->second;
}
iterator begin()
{
return _t.begin();
}
iterator end()
{
return _t.end();
}
private:
RBTree, MapKeyOfT>_t;
}; 你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
