はじめての C

「二分木 6」

さてと 二分木を つくる コードも できたし、同じように、木から ノードを 削除できれば、というのは いい 考えですね。

これは より こみいった 作業です。 というのも、当てはまる ノードを 見つけた後で、処理に 3つの ケースが あるからです。

このことは、3つの 管理用の アルゴリズムを 採り入れることになり、それを たどるのは なかなか 困難です ▽

int tree_remove(struct Node **tree, int value)
{
struct Node **prev, *node;
struct Node *right, *heir; /* heir <- successor */

prev = tree;
node = *tree;
for ( ; ; ) {
if (node == NULL)
return 0;
else if (value > node->data) {
prev = &node->right;
node = node->right;
}
else if (value < node->data) {
prev = &node->left;
node = node->left;
}
else
break;
}

if (node->right == NULL)
/*
* ケース 1: ノードは 右に 子 - child - を もたない。
* ノードを、ノードの 左の子と 取り換える。
*/
*prev = node->left;
else {
right = node->right; /* ここの 2つの right は それぞれ 別のもの */
if (right->left == NULL) {
/*
* ケース 2: ノードは 右に 子を もってるが、その右の子は、左に 子を もっていない。
* ノードの 右の子が ノードの 左の 分肢 - subtree - を 得て、ノードを 取り換える。
*/
right->left = node->left;
*prev = right;
}
else {
/*
* ケース 3: ノードは 右に 子を もっていて、その 右の子も 左に 子を もっている。
* ノードの 右の 分肢の、一番 小さい値の ノードを 見つけだす。
* ノードを この successor と 取り換える。
* successor の 右の 分肢が、successor の 左の 分肢になる。
*/
heir = node->left;
while (heir->left != NULL) {
right = heir;
heir = right->left;
}
right->left = node->right;
heir->left = node->left;
heir->right = node->right;
*prev = heir;
}
}
free(node);
return 1;
}

初めの loop は 明らかに、検索の 方法と 同じです。そこでは 初めから 前に 述べた 追加分の prev の ダブルポインタが 使われています。

二分木削除の ところは コードは 一見 長いようですが、そうでは ありません。 すでに わかっている コメント部分を さがして 除いたものが、実際の コードの 中身です ▽

if (node->right == NULL)
*prev = node->left;
else {
right = node->right;
if (right->left == NULL) {
right->left = node->left;
*prev = right;
}
else {
heir = node->left;
while (heir->left != NULL) {
right = heir;
heir = right->left;
}
right->left = node->right;
heir->left = node->left;
heir->right = node->right;
*prev = heir;
}
}
free(node);

コメントを たどってみると、二分木からの ノードの 削除には 3つの ケースが 含まれています。

最初の ケースは 思いっきり シンプルです。 削除する ノードは 右に 子を もってませんので、ノードを 左の 分肢 - subtree - と 取り換えるだけです。

2つ目の ケースも 同じく シンプルです。 削除する ノードは 右に 子を もってますが、その 右の子は 左に 子を もっていません。 ノードを 削除するには、それを 単に 右の子と 取り換えるだけです。 それで その 左の分肢を、右の子の 左の分肢に 割り当てるのです。

All of this sounds like a mouthful.*1 ですが コード上は ほんとに シンプルなんです。

ロジックが 理解できるまでは、それを 紙の上に 書いてみる という 習慣を つけてください。

3つ目の ケースは むずかしい。 削除する コードは 右に 子を もっていて、その 右の子も 左に 分肢が あります。

このケースで 実行に 必要なのは 何かというと、削除したい ノードの successor を 見つけることです。 successor とは、削除したい ノードの 右の 分肢の なかで、一番 小さい 値の ノードのことです。

では 考えてみましょう。 ノードの 右の 分肢に 移動して、そこで その 左の 分肢を それ以上 左へ 行けないところまで たどること、これが この シンプルな 操作で 必要な 全てです。次のコードを 参照してください ▽

heir = node->right;
while (heir->left != NULL) {
right = heir;
heir = right->left;
}

successor を 見つければ、親 - parent - が とらえられ、その結果 successor の 右の 分肢を 首尾よく 扱うことが できるのです。

紙の上に 書いてみて ちょっとだけ 考えてみれば、この 3つの ケースは ほんとうは シンプルなんですよ、そうじゃない ?

(追記) ちょっと訂正

*1:なにかの コトワザ ?