はじめての C

lang

「二分木 4」

さて、ノードを 1つ つくるための コードを 書かないといけませんね。それには、新しい ノードが 二分木へと リンクできる 必要が あります。

初めに 注意することの 一つは、木には いくつかの 検索形式を 含む、多くの 操作方法が あるということです。これが 二分木探索の どこが 優れているか ということです。

二分木探索の 設計 - design - によって、たいていの どんな 検索操作でも、二分木探索としての 効率的な 結果に なるでしょう。つまり、計算時間が 0(logN) だと いうことです。

挿入や 削除は 検索 - searching - を 含んでいます。それで、ノードが 木に 含まれているか どうかを、初めに 確認するための コードを よく 見ることに しましょう ▽

int tree_search(struct Node *tree, int value)
{
struct Node *node

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

このコードでは 前へと 進んでいき、真か 偽かが 判明するまで (無限) ループします。ノードが null であれば、そこは それ以上 どこにも 行けません。そのノードは 木には ないのです。

次に、それらが 等しいか どうか 値を 比べます。

値が ノードより 大きいのなら、項目は 木の 右半分に あることを 求められます。もし 値が ノードより 小さいと、項目は 木の 左半分に あることが 求められます。

注意するのは、このロジックが どういうふうに 二分木探索と 正確に 同じなのか ということです。上の どちらでも ないのが 正しい - true - とすると、その値は ノードに 等しいことが まちがいないので success を 返します。

特別な credit では、ときには 二分木探索の 操作が 再帰的に 実行されることが あります。tree_search を 再帰版で あらわすと ▽

int tree_search(struct Node *tree, int value)
{
if (tree == NULL)
return 0;
else if (value > tree->data)
return tree_search(tree->right, value);
else if (value < tree->data)
return tree_search(tree->left, value);
else
return 1;
}

このコードは 短いものです。しかし、再帰呼び出しや 二分木探索に 慣れてないと、すぐには 理解できません。

二分木探索を 書くときには、できるだけ 多くの 反復法 - iterative solutions - を 用いるほうが いいのです。それは 効率性を 含んだ 実際的な もので、通常では 複雑なことを 追加しません。

例えば、tree traversal のような 特別のものに ついては、後で 始めることに しましょう。