Я создаю свою собственную структуру карты (необходимо для класса), используя дерево RB. Из того, что я узнал о вставке, у нас есть 3 случая для обработки. я следую этот реализация. Тем не менее, я получаю нарушение памяти после вставки 3-го значения (и далее) при исправлении древовидной структуры RB. Как мне справиться с этим делом?
Ребенок вставляется:
Итак, вот моя реализация:
struct Node
{
pair<int,int> key;
int Value;
Node *LeftNode;
Node *RightNode;
Node *Parent;
bool color; // 0 - black 1 - red
};
class Map
{
int size;
public:
Map();
void insert(pair<int,int>, int);
private:
void RotateLeft(Node*);
void RotateRight(Node*);
void InsertNode(Node*, pair <int,int>, int);
void RestoreColor(Node*);
Node* root;
};
void Map::RestoreColor(Node* child)
{
while( child->Parent!=root && child->Parent->color==1 )
{
if(child->Parent == child->Parent->Parent->LeftNode)
{
Node* uncle = child->Parent->Parent->RightNode;
if(uncle->color == 1)
{
child->Parent->color = 0;
uncle->color = 0;
child->Parent->Parent->color = 1;
child = child->Parent->Parent;
}else
{
if(child = child->Parent->RightNode)
{
child = child->Parent;
RotateLeft(child->Parent);
}
child->Parent->color = 0;
child->Parent->Parent->color= 1;
RotateRight(child->Parent->Parent);
}
}else
{
if(child->Parent == child->Parent->Parent->RightNode)
{
Node* uncle = child->Parent->Parent->LeftNode;
if(uncle->color == 1) {
child->Parent->color = 0;
uncle->color = 0;
child->Parent->Parent->color = 1;
child = child->Parent->Parent;
}else
{
if(child = child->Parent->LeftNode)
{
child = child->Parent;
RotateRight(child->Parent);
}
child->Parent->color = 0;
child->Parent->Parent->color= 1;
RotateLeft(child->Parent->Parent);
}
}
}
root->color=0;
}
};
Нарушение происходит в uncle
доступ, где в этом примере uncle
равняется null
, Как мне изменить функцию?
Вы используете реализацию, которая зависит от сторожевых узлов в качестве конечных узлов, поэтому у вас всегда есть черный узел, который вы можете разыменовать в подобных случаях. Чтобы изменить его, вам нужно изменить такие строки, как
if(uncle->color == 1)
к
if((uncle != NULL) && (uncle->color == 1))
Затем он примет предложение ‘else’, как и должно быть, как и в дозорной версии, цвет всегда будет черным в том случае, если у вас будет нулевой указатель в не дозорной версии.
RotateLeft(child->Parent);
RotateRight(child->Parent);
Разве вышеприведенное в вашем коде не должно быть
RotateLeft(child)
а также RotateRight(child)
соответственно.