Dokusyo-nissi Bessitu

<< 2005/07 >>
1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31

[Debian Memo] (for Woody)
[sekiyo HPへ]

[はじめてのC] C言語のページ (1)
[その 2] (2)
[その 3] ABC of C
[その 4] CPP World Tutorial (1) (by Prelude) linkrot
[その 5] The Standard C Library (Null)
[その 6] CPP World Tutorial (2) linkrot
[その 7] (3)
[その 8] (4)
[その 9] 作ってわかる Cプログラミング (1)
[その 10] (2)
[その 11] Arrays and Pointers in C
[その 12] Learning GNU C (1)
[その 13] (2)
[その 14] (3)
[その 15] (4)
[その 16] アドレスブック
[K & R 2nd] The C Programming Language (1)
[その 2] (2)
[その 3] (3)
[その 4] (4)
[その 5] (5)
[その 6] (6)

[my bookcase]

(サーチエンジンから 来られた方で 該当する
キーワードが 見つからないときには、上の
はてな検索窓から 再度検索してください ←
[日記] のほうを クリック)

 | 

2005-07-21 φ(-_-)

[]はじめての C

二分木 5

木 - tree - への 挿入は、上の 検索と ほぼそのまま 同じになります。ただ 一つ 違ってるのは、null ノードが 見つかったときに、失敗時に 要求された 返り値をもつ 新しい (ノードを) 1つ 挿入することです ▽

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

prev = tree;
node = *tree;

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

すぐに 明らかになる 事実として、ダブルポインタが 使われています。

木への ダブルポインタで、tree_insert に 渡す ノードに 変換できるようにして、さらに 整数の形で 成功 または 失敗したことを 返すように できます。

なぜ これで そうなるのか、より 詳しいことは、そう、ポインタの tutorial を 参照してください :p

2つ目の ダブルポインタは わかりやすいとは いえません。

初めて 二分木構築の 方法を 学んだ頃は、最終的に 理解できるまで、長い間 グズグズしていたものです。

木を 渡っていき、null ポインタか どうかの テストを して、一度 そこで (nullを) 得てしまうと、木との 繋がり - connection - を 見失ってしまいます。

木は null を 指し示すことは できますが、null には それが 木の どの部分かを 知らせる 方法が ないのです。

そのため、null を 指し示す ポインタの アドレスを 確保しておく 必要が あります。そうすることで、必要とされる 新しいノードに 繋ぐことが 成功するのです。

prev ポインタは、ポインタの アドレスの 確保という 必要に 答えて、ノードが 実際に 繋がってる すぐ 前まで、ノードを たどります。


この考え方を 追っていくことは かなり 難しいので、これを デバッガ - debugger - に かけてみることと、その違いを 見るため、コードから prev を 除いてみることを 勧めます。


再帰版の コードは シンプルですが、ここに 選んだものは、設計上の 自由度に 関しては、実用的とは いえません。

たとえば、成功か 失敗かを 整数値で 返すかわりに、tree の root を 返すようにすると、再帰での 効率的な 解決法に なるでしょう ▽

struct Node *tree_insert(struct Node *tree, int value)
{
if (tree == NULL) {

struct Node *nn;

if (new_node(&nn, value))
return nn;
else
return NULL;
}
else if (value > tree->data)
tree->right = tree_insert(tree->right, value);
else if (value < tree->data)
tree->left = tree_insert(tree->left, value);
return tree;
}

これは、今までに なじんでいる見方 - familiar ground - です。

ただ 注意するのは、tree_insert への 再帰呼び出しの 返り値は、木の 左と 右との ポインタに 割り当てられるのであって、木 それ自身にでは ない ということです。

二分木を 学んだとき、それが わからなかったことを 思いだします ... oLr

(追記) ちょっと 訂正。

 | 

[シラノの新聞]

[枇杷と柿]

[馬葉礼 談話]

[My Links]

[Network Archives]


[かうんた→ 531232]