l->parent->left = l;
}
else
{
l->parent->right = l;
}
}
_cur->left = l->right;
if (l->right)
{
_cur->left->parent = _cur;
}
l->right = _cur;
_cur->parent = l;
}
void My_Rb_Tree::Rebalance(node * _cur)
{
node * _root = Root();
_cur->color = node_red;
if (_cur->parent == head) // _cur is root node
{
_cur->color = node_black;
return;
}
if ( _cur->parent->color == node_black ) // now is balance state.
{
return ;
}
// 根据原来的树是符合红黑规则，祖父节点必定为黑色
while( (_cur != Root()) && (_cur->parent->color == node_red)) // 当前节点的父节点为红色，违反规则
{
if (_cur->parent->parent->left == _cur->parent) // 父节点为左子节点
{
if(_cur->parent->parent->right
&& _cur->parent->parent->right->color == node_red) // 伯父节点为红
{
// 把父节点和伯父节点变成黑色，祖父节点变成红色
_cur->parent->parent->right->color=node_black;
_cur->parent->color = node_black;
_cur->parent->parent->color = node_red;
// 因为祖父节点为红色，需要继续向上测试是否满足规则
_cur = _cur->parent->parent;
continue;
}
else // 伯父节点为黑或不存在
{
if ( _cur == _cur->parent->right )
{
// 以父节点为轴，左旋转后变成两个左外节点连续为红。
_cur = _cur->parent;
RotateLeft(_cur/*,_root*/);
// 改变颜色，以祖父节点为轴，右旋转。
_cur->parent->parent->color = node_red;
_cur->parent->color = node_black;
RotateRight(_cur->parent->parent/*,_root*/);
// 此时进入下一次while判断跳出循环
}
}
else // 父节点为右子节点，依照左子节点的同样方法解决。
{
if(_cur->parent->parent->left
&& _cur->parent->parent->left->color == node_red) // 伯父节点为红
{
// 把父节点和伯父节点变成黑色，祖父节点变成红色
_cur->parent->parent->left->color=node_black;
_cur->parent->color = node_black;
_cur->parent->parent->color = node_red;
// 因为祖父节点为红色，需要继续向上测试是否满足规则
_cur = _cur->parent->parent;
continue;
}
else // 伯父节点为黑或不存在
{
if ( _cur == _cur->parent->left )
{
// 以父节点为轴，右旋转后变成两个右外节点连续为红。
_cur = _cur->parent;
RotateRight(_cur/*,_root*/);
}
// 改变颜色，以祖父节点为轴，左旋转。
_cur->parent->parent->color = node_red;
_cur->parent->color = node_black;
RotateLeft(_cur->parent->parent/*,_root*/);
// 此时进入下一次while判断跳出循环
}
}
}//end while
_root->color = node_black;
}
node * My_Rb_Tree::InsertUnique(value_type in_val)
{
node * y = head;
node * x = Root();
bool comp = true;
while( x )//一层一层深入找到合适的插入点
{
y = x;
comp = ( in_val < x->val );
if (in_val == x->val)
{
return 0;
}
x = comp x->left : x->right;
}
return Insert(y,x,in_val);
}
node * M