#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
using namespace std;
enum Color
{
RED, BLACK
};
template<class K, class V>
struct RBTreeNode
{
RBTreeNode<K, V>* _parent;
RBTreeNode<K, V>* _left;
RBTreeNode<K, V>* _right;
pair<K, V> _kv;
Color _color;
RBTreeNode(const pair<K, V>& kv)
:_parent(nullptr)
, _left(nullptr)
, _right(nullptr)
, _kv(kv)
, _color(RED)
{}
};
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);
return true;
}
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
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
{
assert(!cur);
}
}
//需要将这个节点连接起来
cur = new Node(kv);
cur->_color = RED;
cur->_parent = parent;
if (parent->kv.first > cur->_kv.first)
{
parent->_left = cur;
}
else if (parent->kv.first < cur->_kv.first)
{
parent->_right = cur;
}
//根据不同情况就行调整,父亲节点是黑色就是走到根了
while (parent && parent->_color == RED)
{
Node* grandfather = parent->_parent;
//这里默认插入都是红色,这里需要进行调整
if (parent == grandfather->_left)
{
Node* uncle = grandfather->_right;
if (uncle && uncle == RED)
{
parent->_color = uncle->_color = BLACK;
grandfather = RED;
cur = grandfather;
parent = cur->_parent;
}
//uncle不存在或者为黑色,需要旋转
else
{
if (cur = parent->_left)
{
RotateR(grandfather);
parent->_color = BLACK;
grandfather->_color = RED;
}
else
{
RotateL(parent);
RotateR(grandfather);
cur = BLACK;
parent->_color = grandfather->_color = RED;
}
}
}
else
{
// 情况二:叔叔不存在或者存在且为黑
// 旋转+变色
// g
// u p
// c
if (cur == parent->_right)
{
RotateL(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
else
{
// g
// u p
// c
RotateR(parent);
RotateL(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
}
_root->_col = BLACK;
return true;
}
void RotateR(Node* parent)
{
Node* SubL = parent->_left;
Node* SubLR = SubL->_right;
parent->_left = SubLR;
if (SubLR)
SubLR->_parent = parent;
SubL->_right = parent;
Node* ppNode = parent->_parent;
parent->_parent = SubL;
if (parent == _root)
{
SubL = _root;
SubL->_parent = nullptr;
}
else
{
if (ppNode->_left == parent)
{
ppNode->_left = SubL;
}
else if (ppNode->_right == parent)
{
ppNode->_right = SubL;
}
SubL->_parant = ppNode;
}
}
void RotateL(Node* parent)
{
Node* SubR = parent->_right;
Node* SubRL = SubR->_left;
parent->_right = SubRL;
if (SubRL)
SubR->_parent = parent;
SubR->_left = parent;
Node* ppNode = parent->_parent;
parent->_parent = SubR;
if (parent == _root)
{
SubR = _root;
SubR->_parent = nullptr;
}
else
{
if (ppNode->_left == parent)
{
ppNode->_left = SubR;
}
else if (ppNode->_right == parent)
{
ppNode->_right = SubR;
}
SubR->_parant = ppNode;
}
}
bool IsBalance()
{
if (_root->_color == RED)
{
return false;
}
int refNum = 0;
//记录单独一边黑色节点个数
Node* cur = _root;
while (cur)
{
refNum++;
cur = cur->_left;
}
return Check(_root, 0, refNum);
}
void InOder()
{
_InOder(_root);
cout << endl;
}
private:
bool Check(Node* root, int blackNum, const int refNum)
{
//接下就是遍历每条路径了
if (_root == nullptr)
{
if (blackNum != refNum)
{
cout << "不满足每条路径相同黑色节点" << endl;
return false;
}
return true;
}
if (root->_col == RED && root->_parent->_col == RED)
{
cout << root->_kv.first << "存在连续的红色节点" << endl;
return false;
}
if (root->_col == BLACK)
{
blackNum++;
}
return Check(root->_left, blackNum, refNum) && Check(root->_right, blackNum, refNum)
}
void _InOder(Node* _root)
{
_InOder(_root->_left);
cout << endl;
_InOder(_root->_right);
}
private:
Node* _root = nullptr;
};
感谢大家的观看!以上就是本篇文章的全部内容。我是店小二,希望这些高阶数据结构笔记能为你在学习旅途中提供帮助!