{
node * new_node = CreateNode(in_value);
if (in_parent == head) // 插入的是根节点
{
head->parent = new_node;
head->left = new_node;
head->right = new_node;
new_node->parent = head;
new_node->color = node_black;
}
else // 插入的是非根节点
{
if ( new_node->val < in_parent->val )
{
in_parent->left = new_node;
if (in_parent == head->left) // 若插入点的父节点是最小节点，更新最小值节点指针
{
head->left = new_node;
}
}
else
{
in_parent->right = new_node;
if (in_parent == head->right)// 若插入点的父节点是最大节点，更新最大值节点指针
{
head->right = new_node;
}
}
new_node->parent = in_parent;
if (in_parent == head)
{
head->parent = new_node;
in_parent->parent = Root();
}
Rebalance(new_node/*,head->parent*/);
node_count++;
return new_node;
}
// 未实现，这个函数比较复杂
void My_Rb_Tree::RebalanceForErase(node * _cur)
{
return;
}
// 依赖RebalanceForErase的实现
void My_Rb_Tree::Erase(node * in_cur)
{
return;
}
node * My_Rb_Tree::Find(value_type _val)
{
node * _t = Root();
while(_t)
{
if (_t->val == _val)
{
return _t;
}
else if (_t->val > _val)
{
_t = _t->right;
}
else
{
_t = _t->left;
}
}
return 0;
}