机缘
一开始呢，其实写博客是老师推荐去写的
慢慢的也是学会去当做分享什么的，不过有段时间经常没空，就忘了写博客
收获
- 获得了367粉丝的关注
- 在创作中也受到了赞和评论等正向反馈
- 能和一些志同道合的人一起进步，是莫大的荣幸
日常
- 创作是否已经是你生活的一部分了
- 有段时间忙碌的忘了创作，最近又开始了新的创作
- 赶紧生活在创作下更丰富
成就
提示：你过去写得最好的一段代码是什么？ 请用代码块贴出来
例如：
我写过最好的代码算是一个封装吧
#pragma once
#pragma once
#include<iostream>
using namespace std;
namespace bit
{
enum Colour
{
Red, Black
};
template<class T>
struct RBTreeNode
{
T data;
RBTreeNode<T>* left;
RBTreeNode<T>* right;
RBTreeNode<T>* parent;
Colour col;
RBTreeNode(const T _data)
: data(_data)
, left(nullptr)
, right(nullptr)
, parent(nullptr)
{
}
};
template<class T,class Ref,class Ptr>
struct RBTreeIterator
{
typedef RBTreeNode<T> Node;
typedef RBTreeIterator<T, Ref, Ptr> Self;
public:
Node* node;
Node* root;
RBTreeIterator(Node* _node=nullptr,Node* _root=nullptr )
:node(_node)
,root(_root)
{
}
Self& operator++()
{
if (node->right)
{
Node* leftmost = node->right;
while (leftmost->left)
{
leftmost = leftmost->left;
}
node = leftmost;
}
else
{
Node* cur = node;
Node* parent = node->parent;
while (parent && cur == parent->right)
{
cur = parent;
parent = cur->parent;
}
node = parent;
}
return *this;
}
Self& operator--()
{
if (node == nullptr)
{
Node* rightmost = root;
while (rightmost&&rightmost->right)
{
rightmost = rightmost->right;
}
node = rightmost;
return *this;
}
else if (node->left)
{
Node* rightmost = node->left;
while (rightmost->right)
{
rightmost = rightmost->right;
}
node = rightmost;
}
else
{
Node* cur = node;
Node* parent = node->parent;
while (parent && cur == parent->left)
{
cur = parent;
parent = cur->parent;
}
node = parent;
}
return *this;
}
Ref operator*()
{
return node->data;
}
Ptr operator->()
{
return &node->data;
}
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 RBTreeIterator<T, T&, T*> Iterator;
typedef RBTreeIterator<const T, const T&, const T*> ConstIterator;
Iterator begin()
{
Node* cur = root;
while (cur&&cur->left)
{
cur = cur->left;
}
return Iterator(cur,root);
}
Iterator end()
{
return Iterator(nullptr,root);
}
ConstIterator begin()const
{
Node* cur = root;
while (cur && cur->left)
{
cur = cur->left;
}
return ConstIterator(cur, root);
}
ConstIterator end() const
{
return ConstIterator(nullptr, root);
}
RBTree() = default;
RBTree(const RBTree& t)
{
root = copy(t.root);
}
Node* copy(Node* t)
{
if (t == nullptr)
return nullptr;
Node* tmp = new Node(t->_kv);
Node* left = copy(t->left);
Node* right = copy(t->right);
tmp->left = left;
tmp->right = right;
return tmp;
}
RBTree& operator=(RBTree t)
{
swap(root, t.root);
return *this;
}
~RBTree()
{
Destory(root);
}
void Destory(Node* root)
{
if (root == nullptr)
return;
Destory(root->left);
Destory(root->right);
delete root;
root = nullptr;
}
pair<Iterator,bool> insert(const T& _data)
{
if (root == nullptr)
{
root = new Node(_data);
return make_pair(Iterator(root,root),true);
}
KeyOft keof;
Node* parent = nullptr;
Node* cur = root;
while (cur)
{
if (keof(cur->data) > keof(_data))
{
parent = cur;
cur = cur->left;
}
else if (keof(cur->data) < keof(_data))
{
parent = cur;
cur = cur->right;
}
else
{
cout << "已经重复了" << endl;
return make_pair(Iterator(cur,root),false);
}
}
cur = new Node(_data);
Node* newcur = cur;
cur->col = Red;
if (keof(parent->data) > keof(_data))
{
parent->left = cur;
}
else
{
parent->right = cur;
}
cur->parent = parent;
while (parent && parent->col == Red)
{
Node* grandfather = parent->parent;
Node* uncle = nullptr;
// g
//u p
// c
if (parent == grandfather->right)
{
uncle = grandfather->left;
if (uncle && uncle->col == Red)//叔叔是红色的 ，就改变颜色
{
parent->col = uncle->col = Black;
grandfather->col = Red;
cur = grandfather;//改完色之后 更新成爷爷为插入的结点了
parent = cur->parent;
}
else//uncle 为黑色 或者 不存在 就看单旋还是双旋
{
//统一一根线是单旋
if (cur == parent->right)
{
grandfather->col = Red;
parent->col = Black;
RotateL(grandfather);
}
// g
// u p
// c
else
{
RotateR(parent);
RotateL(grandfather);
cur->col = Black;
grandfather->col = Red;
}
break;
}
}
else
{
// g
// p u
//c
uncle = grandfather->right;
if (uncle && uncle->col == Red)//叔叔是红色的 ，就改变颜色
{
parent->col = uncle->col = Black;
grandfather->col = Red;
cur = grandfather;//改完色之后 更新成爷爷为插入的结点了
parent = cur->parent;
}
else//uncle 为黑色 或者 不存在 就看单旋还是双旋
{
//统一一根线是单旋
if (cur == parent->left)
{
grandfather->col = Red;
parent->col = Black;
RotateR(grandfather);
}
// g
// p u
// c
else
{
RotateL(parent);
RotateR(grandfather);
cur->col = Black;
grandfather->col = Red;
}
break;
}
}
}
root->col = Black;
return make_pair(Iterator(newcur,root), true);
}
void RotateL(Node* parent)
{
Node* subR = parent->right;
Node* subRL = subR->left;
parent->right = subRL;
if (subRL)
subRL->parent = parent;
Node* PParent = parent->parent;
subR->left = parent;
parent->parent = subR;
if (PParent)
{
subR->parent = PParent;
if (PParent->left == parent)
PParent->left = subR;
else
PParent->right = subR;
}
else
{
subR->parent = nullptr;
root = subR;
}
}
void RotateR(Node* parent)
{
Node* subL = parent->left;
Node* subLR = subL->right;
parent->left = subLR;
if (subLR)
subLR->parent = parent;
Node* PParent = parent->parent;
subL->right = parent;
parent->parent = subL;
if (PParent == nullptr)
{
root = subL;
}
else
{
if (PParent->right == parent)
PParent->right = subL;
else
PParent->left = subL;
}
subL->parent = PParent;
}
int Height()
{
return _Height(root);
}
int Size()
{
return _Size(root);
}
void InOrder()
{
_InOrder(root);
cout << endl;
}
bool IsBalance()
{
return _IsBalance(root);
}
bool Find(const T& _data)
{
Node* cur = root;
while (cur)
{
if (keof(cur->data) > keof(_data))
{
cur = cur->left;
}
else if (keof(cur->data) < keof(_data))
{
cur = cur->right;
}
else
{
return true;
}
}
return false;
}
private:
RBTreeNode<T>* root;
bool _IsBalance(Node* _root)
{
if (_root == nullptr)
return true;
if (_root->col == Red)
return false;
Node* cur = _root;
int count = 0;
while (cur)
{
if (cur->col == Black)
{
count++;
}
cur = cur->left;
}
return check(count, 0, _root);
}
bool check(int count, int num, Node* _root)
{
if (_root == nullptr)
{
if (count != num)
{
cout << "路径长度不一致" << endl;
cout << count << "::" << num << endl;
return false;
}
return true;
}
if (_root->col == Red)
{
if (_root->parent->col == Red)
{
cout << "连续红色" << endl;
return false;
}
}
if (_root->col == Black)
{
num++;
}
return check(count, num, _root->left) && check(count, num, _root->right);
}
void _InOrder(Node* _root)
{
if (_root == nullptr)
return;
KeyOft keof;
_InOrder(_root->left);
cout << keof(_root->data) << " ";
_InOrder(_root->right);
}
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 _Size(Node* _root)
{
if (_root == nullptr)
return 0;
return _Size(_root->left) + _Size(_root->right) + 1;
}
};
}憧憬
慢慢进步吧，一点一点