2005-07-31

「二分木 9」

これまで見てきた二分木では、すべて、データ構造体のテキスト内で定義がされています。

より多くの制御が必要となったとき、例えば、下に動くだけでなく、双方向リストと同じように、木の上方にも移動させたいことがあります。

そのためには、そのノードの親 - parent - へのポインタが必要です。それは次のように実装できます ▽

struct Node {
int data;
struct Node *parent;
struct Node *left;
struct Node *right;
};

構造体にシンプルな変更を加えることで、別のポインタをいじれるようになります。

挿入前と同じ動作 - semantics - を確保するため、同じように、ちょっとだけ new_node を変更する必要があります ▽

int make_node(struct Node **node, struct Node *parent, int value)
{
*node = malloc(sizeof(**node));
if (*node == NULL)
return 0;

(*node)->data = value;
(*node)->parent = parent;
(*node)->left = NULL;
(*node)->right = NULL;
return 1;
}

注意するのは、親 - parent - にポインタを渡すのは、ノードポインタへのポインタと同じだということです。

ここでは、空の木 - empty tree - の場合に特別な処理を行うことで、挿入がよりやさしくできます ▽

int tree_insert(struct Node **tree, int value)
{
struct Node *node;

node = *tree;
if (node == NULL)
return make_node(tree, NULL, value);
for ( ; ; ) {
if (value > node->data) {
if (node->right = NULL)
return make_node(&node->right, node, value);
node = node->right;
}
else if (value < node->data) {
if (node->left == NULL)
return make_node(&node->left, node, value);
node = node->left;
}
else
return 1;
}
}

この操作での注意点は、null へはノードを割り当てられないことです。そこで、実際にそこへ行かずに、規則に則って - play game to - 正確な位置を見つけます。

例えば、挿入したい値が現在のノードの値より大きく、node->right が null の場合は、node->right のアドレスが欲してる新しい項目の場所であり、ノードが親であることがわかっています。

node->right が null でなければ、ノードが node->right を指すようにセットします。

同じ手順で、左の分肢をたどっていきます。

よくできた参考書のあの腹のたつシキタリ - infuriating traditions - に従って、親ポインタ - parent pointers - の削除については、あなたがたの演習のために、残しておきましょうね。:p

前に使った削除用の関数で、どうしてノードへの successor を見つけたかを覚えていますか ?

あの関数が変更できるかオネガイすることはできないでしょうか ?

よろしい、今だと親ポインタもあって、再帰を使わずに木の上方へと移動できるので、簡単にそれを書くことができます ▽

struct Node **successor(struct Node *node)
{
struct Node *heir;

if (node->right != NULL) {
heir = node->right;
while (heir->left != NULL)
heir = heir->left;
}
else {
heir = node->parent;
while (heir != NULL && node == heir->right) {
node = heir;
heir = heir->parent;
}
}
return heir;
}

初めの部分は tree_remove とまったくいっしょで、次のところもほとんど同じです。その 2番目のところには、リーフ - 木のちょうど一番下にあたるノード - を見つけることが含まれています。

それで、リーフでないノードの successor を見つけて、ノードの右の分肢の、さらにその左の分肢を全てたどっていきます。

リーフノードの successor を見つけると、それ以上進むことができないところまで、左の分肢を上がっていきます。

いま、「でもそれじゃ、親ポインタで、一つの方向に上がってるだけじゃないか !」と思ったでしょう。

そうですよ ! しかし、以前訪れてコード上に示されていた方角が、どちらなのかということも、同じく見失うことがないのです。

それがどうして実行されるのかわかるために、このロジックを紙の上に書いてみる、ということを忘れないでください。

二分木の tutorial 初回分は、これでおしまいです。

まだあるのか ... oLr

sekiyo’s diary

はじめての C