Thomas H Cormen の本「Introduction to Algorithms」などの赤と黒の木の疑似コードがあります。
挿入と挿入修正の疑似コードはここにあります
while(n->parent->color == 'r')
「8」を挿入しようとすると、以下のテスト データを使用する挿入修正関数内で、次の行でセグ フォールトが発生します。
テストデータ:
i 5
i 7
i 1
i 8
i 3
これは、 n の親が存在しない可能性があるためだと思いますか? しかし、疑似コードを完全に台無しにすることなく、コードを適切に変更する方法がわかりません。
ここに私の挿入があります:
void insert_fix(node * n)
{
node * y;
if(n->parent)
{
while(n->parent->color == 'r')
{
if(n->parent == n->parent->parent->left)
{
y = n->parent->parent->right;
if(y->color == 'r')
{
n->parent->color = 'b';
y->color = 'b';
n->parent->parent->color = 'r';
n = n->parent->parent;
}
else
{
if(n == n->parent->right)
{
n = n->parent;
rotate_left(n);
}
n->parent->color = 'b';
n->parent->parent->color = 'r';
}
}
else
{
y = n->parent->parent->left;
if(y->color == 'r')
{
n->parent->color = 'b';
y->color = 'b';
n->parent->parent->color = 'r';
n = n->parent->parent;
}
else
{
if(n == n->parent->left)
{
n = n->parent;
rotate_right(n);
}
n->parent->color = 'b';
n->parent->parent->color = 'r';
}
}
}
}
root->color = 'b';
}
これが私の挿入修正です:
void insert_fix(node * n)
{
node * y;
if(n->parent)
{
while(n->parent->color == 'r')
{
if(n->parent == n->parent->parent->left)
{
y = n->parent->parent->right;
if(y->color == 'r')
{
n->parent->color = 'b';
y->color = 'b';
n->parent->parent->color = 'r';
n = n->parent->parent;
}
else
{
if(n == n->parent->right)
{
n = n->parent;
rotate_left(n);
}
n->parent->color = 'b';
n->parent->parent->color = 'r';
}
}
else
{
y = n->parent->parent->left;
if(y->color == 'r')
{
n->parent->color = 'b';
y->color = 'b';
n->parent->parent->color = 'r';
n = n->parent->parent;
}
else
{
if(n == n->parent->left)
{
n = n->parent;
rotate_right(n);
}
n->parent->color = 'b';
n->parent->parent->color = 'r';
}
}
}
}
root->color = 'b';
}
*明確にするために、上記のwhileループの周りに余分なifステートメントを追加して、ノードがルートである場合は何も起こらないようにしましたが、私が望んでいたように私の問題を解決しませんでした.
参考までに、インターネットで見つけた情報に基づいて、右回転と左回転の関数を多少異なる方法で作成しましたが、かなりよく書かれていると思います。
void rotate_right(node *n)
{
node* left = n->left;
swap_nodes(n, left);
n->left = left->right;
if(left->right != NULL)
left->right->parent = n;
left->right = n;
n->parent = left;
}
void rotate_left(node *n)
{
node* right = n->right;
swap_nodes(n, right);
n->right = right->left;
if(right->left != NULL)
right->left->parent = n;
right->left = n;
n->parent = right;
}
void swap_nodes(node* oldNode, node* newNode)
{
if(oldNode->parent == NULL)
root = newNode;
else
{
if(oldNode == oldNode->parent->left)
oldNode->parent->left = newNode;
else
oldNode->parent->right = newNode;
}
if(newNode != NULL)
newNode->parent = oldNode->parent;
}
繰り返しますが、実際のコードは擬似コードに正確に従っているように感じますが、欠けている部分がわかりません。
お知らせ下さい!ありがとう!