Красно-черная вставка для крепления дерева

Я создаю свою собственную структуру карты (необходимо для класса), используя дерево 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, Как мне изменить функцию?

1

Решение

Вы используете реализацию, которая зависит от сторожевых узлов в качестве конечных узлов, поэтому у вас всегда есть черный узел, который вы можете разыменовать в подобных случаях. Чтобы изменить его, вам нужно изменить такие строки, как

if(uncle->color == 1)

к

if((uncle != NULL) && (uncle->color == 1))

Затем он примет предложение ‘else’, как и должно быть, как и в дозорной версии, цвет всегда будет черным в том случае, если у вас будет нулевой указатель в не дозорной версии.

2

Другие решения

RotateLeft(child->Parent);

RotateRight(child->Parent);

Разве вышеприведенное в вашем коде не должно быть

RotateLeft(child) а также RotateRight(child) соответственно.

0

По вопросам рекламы [email protected]