二分探索木に最初の値を挿入するときのプログラムの挙動について

Question

リンク内容### 前提・実現したいこと

二分探索木T に対し、以下の命令を実行するプログラムを作成してください。

insert k: Tにキー k を挿入する。

という問題なのですが、これをC++で実装するにあたって模範解答を見ると以下のようになってました。しかしこのinsert関数の部分ですが、一番初めにデータを挿入するときrootにどのようにデータが追加されるか理解できません。これだと、xがrootで初期化されていて、whileループに入り、yにxのrootが代入されて, yがNILでなくなってしまうのではないでしょうか。そうなるとif(y == NIL)が偽になってしまい、結局rootが定まらなくなってしまうと思います。もしwhileループを経ないのであれば、どのタイミングでxにNILが代入されるのでしょうか。この点について解説していただけますか。

該当のソースコード

#include <cstdio>
#include <cstdlib>
#include <string>
#include <iostream>

using namespace std;

struct Node{
    int key;
    Node *right, *left, *parent;
};

Node *root, *NIL;

void insert(int k)
{
    Node *y = NIL;
    Node *x = root;
    Node *z;

    z = (Node *)malloc(sizeof(Node));
    z->key = k;
    z->left = NIL;
    z->right = NIL;

    while(x != NIL ){
        y = x;
        if(z->key < x->key){
            x = x->left;
        }else{
            x = x->right;
        }
    }
    z->parent = y;
    if(y == NIL){
        root = z;
    }else {
        if(z->key < y->key){
            y->left = z;
        }else{
            y->right = z;
        }
    }
}

void inorder(Node *u)
{
    if(u == NIL) return;
    inorder(u->left);
    printf(" %d", u->key);
    inorder(u->right);
}

void preorder(Node *u)
{
    if(u == NIL) return;
    printf(" %d", u->key);
    preorder(u->left);
    preorder(u->right);
}

int main()
{
    int n, i, x;
    string com;

    scanf("%d", &n);

    for(i = 0; i < n; i++){
        cin >> com;
        if(com == "insert"){
            scanf("%d", &x);
            insert(x);
        }else{
            inorder(root);
            printf("\n");
            preorder(root);
            printf("\n");
        }
    }
    return 0;
}

Comments

[mjk]

何かの「問題」に関する質問には「問題」へのリンクを貼ってください。

コードの書き方について(LouiS0616さん)
https://teratail.com/questions/151115
>>teratailには、コードを見やすく表示する機能があります。
>>質問編集画面を開き、コードを選択した状態で<code>ボタンを押してください。

[mjk]

AOJの問題ですよね？引用する場合は「問題」へのリンクを貼ってください。

[rdld036]

https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/8/ALDS1_8_A

Answer 1

グローバル変数を宣言のみした場合、０に初期化される。一方ローカル変数ではごみ値で初期化される。今回はポインタ変数なのでどちらもnullptrになり、結果最初の時点でx==NILになった。

Answer 2

これだと、xがrootで初期化されていて、whileループに入り、yにxのrootが代入されて, yがNILでなくなってしまうのではないでしょうか。

模範解答を疑っても仕方ありません。
模範解答が理解出来ない時はデバッグしてみましょう。

1回目のinsert 7の処理ではwhile()ループには入っていません。
何故ならx != NIL がfalse、つまりx == NILだからです。

2回目のinsert 5でやっとwhile()ループに入ります。

  if (x == NIL) printf("x=NIL1\n");
  while (x != NIL) {
    y = x;
    if (z->key < x->key) {
      x = x->left;
    } else {
      x = x->right;
    }
  }
  if (x == NIL) printf("x=NIL2\n");

3
insert 7
insert 5
print

3
insert 7
x=NIL1
x=NIL2
insert 5
x=NIL2
print
 5 7
 7 5

もしwhileループを経ないのであれば、どのタイミングでxにNILが代入されるのでしょうか。

xにNILが代入されるというよりも、比較したら値が同じということです。
Node *root, *NIL;
Node *x = root;
つまり全て空っぽのNodeなので比較しても同じということです。

Node *root, *NIL;

void insert(int k) {
  Node *y = NIL;
  Node *x = root;
  Node *z;

Comments

[rdld036]

初期化せず宣言だけしたとき、両方のポインタ変数の値はNULLを返すということでしょうか

[mjk]

ポインタの値というよりも、Nodeが空なので比較したら全て同じという結果です。
x==NILなのでwhile (x != NIL) {}ループに入らないというデバッグ結果を見ても納得いかないですか？

[mjk]

cout << root << " " << NIL << endl;
これを見たい場所に入れるだけで見れますよね。
それくらい聞く前にご自分でデバッグして出力して試したらどうでしょうか？
私はあなたのテスターではありませんよ。

[rdld036]

おそらくグローバル変数で初期化せず宣言したためにx==NILになったのかと思います。いろいろご指摘していただきありがとうございます。

[rdld036]

私は結果論ではなくそうなる理由を知りたかっただけですので。でも自力で解決したので大丈夫です。質問の仕方については以後気をつけます。ありがとうございました。