#pragma once
using namespace std;
#include
typedef enum{RED=0,BLACK} Color;
template
struct RBTNode
{
Color color;
Type Key;
RBTNode* left;
RBTNode* right;
RBTNode* parent;
};
template
class RBTree
{
public:
RBTree()
{
Nil = BuyNode();
root = Nil;
Nil->color = BLACK;
}
~RBTree()
{
destroy(root);
delete Nil;
Nil = NULL;
}
void InOrder() { InOrder(root); }
bool Insert(const Type& value)
{
RBTNode* pr = Nil;
RBTNode* s = root;
while (s != Nil)//相当于从根节点开始找,哪个节点能当你你传入的这个值的父节点
{
if (value == s->Key)//如果你要插入的这个值和这个点的值一样大,那么彻底无法插入
{
return false;
}
pr = s;
if (value < s->Key)
{
s = s->left;
}
else
{
s = s->right;
}
}
//根据while的条件,可以判断出while循环结束后,s一定是某一个空的叶子节点
s = BuyNode(value);//在这个空节点上,我们建立新的节点
if (pr == Nil)//如果pr为空,则说明当前创建的节点为根节点,因此要维护一下根节点的附属关系
{
root = s;
root->parent = pr;
}
else
{
if (value < pr->Key)
{
pr->left = s;
}
else
{
pr->right = s;
}
s->parent = pr;
}
Insert_Fixup(s);
return true;
}
void Remove(Type key)
{
RBTNode* t;
if ((t = Search(root, key)) != Nil)
{
Remove(t);//找到了就去除
}
else
{
cout << "ERROR::KEY IS NOT EXIST." << endl;//找不到就报错
}
}
void InOrderPrint()
{
InOrderPrint(root);
}
protected:
RBTNode* BuyNode(const Type& x = Type())
{
RBTNode* s = new RBTNode();
//static_assert(s != NULL);
s->color = RED;
s->left = s->right = s->parent = Nil;
s->Key = x;
return s;
}
void InOrder(RBTNode* root)
{
if (root!=Nil )
{
InOrder(root->left);
cout << root->Key << " ";
InOrder(root->right);
}
}
//一个旋转节点只和自己的右节点发生左旋,只和自己的左节点发生右旋
void LeftRotate(RBTNode* z)
{
RBTNode* y = z->right;
z->right = y->left;
if (y->left)
{
y->left->parent = z;
}
y->parent = z ->parent;
if (root == z)
{
root = y;
}
else if (z == z->parent->left)
{
z->parent->left = y;
}
else
{
z->parent->right = y;
}
y->left = z;
z -> parent = y;
}
void RightRotate(RBTNode* z)
{
RBTNode* y = z->left;
z->left = y->right;
if (y->right)
{
y->right->parent = z;
}
y->parent = z->parent;
if (root == z)
{
root = y;
}
else if (z == z->parent->left)
{
z->parent->left = y;
}
else
{
z->parent->right = y;
}
y->right = z;
z->parent = y;
}
void Insert_Fixup(RBTNode* s)
{
RBTNode* uncle;
while (s->parent->color == RED)//这里很简单:我们最核心的诉求就是新插入的这个节点不要和它的父节点都是红节点而已
{
if (s->parent == s->parent->parent->left)//当我们想要具体的知道叔伯节点时就已经要开始分情况了
{
uncle = s->parent->parent->right;
if (uncle->color == RED)//如果叔伯节点为红色
{
s->parent->color = BLACK;
uncle->color = BLACK;
s->parent->parent->color = RED;
s = s->parent->parent;
}
else//如果书伯节点为黑色或不存在叔伯节点
{
if (s == s->parent->right)//插入节点->父节点->爷节点呈<,则先进行一次左旋,再进行右旋
{
s = s->parent;
LeftRotate(s);
}
//如果插入节点->父节点->爷节点呈/则直接到这里改变颜色然后右旋即可
s->parent->color = BLACK;
s->parent->parent->color = RED;
RightRotate(s->parent->parent);//这里提示了我们,无论左旋还是右旋,我们所说的旋转节点全部都是
}
}
else
{
if (s->parent == s->parent->parent->right)//父节点是爷节点的右节点
{
uncle = s->parent->parent->left;
if (uncle->color == RED)
{
s->parent->color = BLACK;
uncle->color = BLACK;
s->parent->parent->color = RED;
s = s->parent->parent;
}
else//同样的还是叔伯节点为空或者黑节点时
{
if (s == s->parent->left)
{
s = s->parent;
RightRotate(s);
}
s->parent->color = BLACK;
s->parent->parent->color = RED;
LeftRotate(s->parent->parent);
}
}
}
}
root->color = BLACK;
}
RBTNode* Search(RBTNode* root, Type key) const
{
if (root == Nil) return Nil;
if (root->Key == key)
{
return root;
}
if (key < root->Key)
{
return Search(root->left,key);
}
else
{
return Search(root->right,key);
}
}
void Transplant(RBTNode* u, RBTNode* v)
{
//注意!!!!这里并没有对中间的这个父节点u进行任何更改
if (u->parent == Nil)
{
root = v;
}
else if (u == u->parent->left)
{
u->parent->left = v;
}
else
{
u->parent->right = v;
}
v->parent = u->parent;
}
RBTNode* Minimum(RBTNode* x)
{
if (x->left == Nil)
{
return x;
}
return Minimum(x->left);
}
void Remove(RBTNode* z)
{
RBTNode* x = Nil;
RBTNode* y = z;
Color ycolor = y->color;
if (z->left == Nil)
{
x = z->right;
Transplant(z, z->right);
}
else if(z->right==Nil)
{
x = z->left;
Transplant(z, z->left);
}
else
{
//这个就很容易理解了,当被删除节点两个节点都存在时,我们可以选取左子树中最大的节点来替换它,也可以选
//取右子树中最小的节点替代他,这里我们使用的是右子树最小节点的方法
y = Minimum(z->right);
ycolor = y->color;
x = y->right;
if (y->parent == z)//这里的if else也看懂了,当y就是z的右节点时,它想替换z的位置就不用继承什么z的右节点了,相反如果不是
//z的直接右节点,我们的节点搬上去就需要把z节点的左右节点都继承上
{
//x->parent = y;
cout << "写你吗呢" << endl;
}
else
{
Transplant(y, y->right);
y->right = z->right;
y->right->parent = y;
}
Transplant(z, y);
y->left = z->left;
z->left->parent = y;
y->color = z->color;
}
if (ycolor == BLACK)
{
Remove_Fixup(x);
}
}
void Remove_Fixup(RBTNode* x)
{
while (x != root && x->color == BLACK)
{
if (x == x->parent->left)
{
RBTNode* w = x->parent->right;
if (w->color == RED)
{
w->color = BLACK;
x->parent->color = RED;
LeftRotate(x->parent);
w = x->parent->right;
}
if (w->left->color == BLACK && w->right->color == BLACK)
{
w->color = RED;
x = x->parent;
}
else
{
if (w->right->color == BLACK)
{
w->color = RED;
w->left->color = BLACK;
RightRotate(w);
w = x->parent->right;
}
w->color = w->parent->color;
w->parent->color = BLACK;
w->right->color = BLACK;
LeftRotate(x->parent);
x = root;
}
}
else
{
RBTNode* w = x->parent->left;
if (w->color == RED)
{
w->parent->color = RED;
w->color = BLACK;
RightRotate(x->parent);
w = x->parent->left;
}
if (w->right->color == BLACK && w->left->color == BLACK)
{
w->color = RED;
x = x->parent;
}
else
{
if (w->left->color == BLACK)
{
w->right->color = BLACK;
w->color = RED;
LeftRotate(w);
w = x->parent->left;
}
w->color = x->parent->color;
x->parent->color = BLACK;
w->left->color = BLACK;
RightRotate(x->parent);
x = root;
}
}
}
x->color = BLACK;
}
void destroy(RBTNode* root)
{
if (root == Nil) return;
if (root->left != Nil) destroy(root->left);
if (root->right != Nil) destroy(root->right);
delete root;
root = NULL;
}
void InOrderPrint(RBTNode* node)
{
if (node == Nil) return;
if (node->left != NULL)
{
InOrderPrint(node->left);
}
cout << node->Key << "(" << ((node->color == BLACK) ? "BLACK" : "RED") << ")" << " ";
if (node->right != Nil)
{
InOrderPrint(node->right);
}
}
public:
RBTNode* root;
RBTNode* Nil=nullptr;
};
