Dokusyo-nissi Bessitu 2005-07-14 φ(-_-) ■ [lang]はじめての C 「二分木」 二分探索法 - binary search - は、役にたつ強力なアルゴリズムです。ただし、リ ストの中を自在に動ける - jump around - ようにするための、二分探索法に適した データ構造 - data structure - を選択しておく、という規制があります。 リンクリストは実用的で、どの箇所が必要になっても、捜しだすまで連続してポイ ンタを追跡します。 配列はもっともシンプルな選択になります。というのも、すでに言語に組み込まれ ており、使い方もやさしくてコンパクトだからです。それに検索も高速で、どこの 配列であっても効率的に取りだすことができるという利点があります。 二分探索の代わりに配列を利用すると、新しい項目の挿入や削除が必要な際にはそ の魅力が半減してしまいます。 コンピュータサイエンスを学生が学び始めたときなど、配列の要素の移動、すなわ ちその挿入あるいは削除の処理については、操作が expensive になるというので、 できるだけ避けるようにといわれます。 データ構造のリンクだと、挿入や削除には適しています。ただしより速く動けるよ うなやり方でリンクをおこなう必要があります。 それで、少し detail を足すという追加策を設けないと、そのままでは目標に達し ないだろうと思います。 構造体を効率的に検索できるようリンクするのではなく、それぞれのノードを、そ の値より大きいか小さいかによって、別のノードへリンクできれば、ということが 言えるのです。 二分木探索の基本的な仕組みとして、0 またはそれ以上のノードの集合があり、そ れぞれのノードがポインタによって、左側の分肢 - subtree - と右側の分肢に繋が っています。 左側の分肢は常にその値が親 - parent - より小さく、右側の分肢は常にその値が 親よりも大きくなっています。 それぞれの分肢も、そこが null でなければ、自分自身の二分木をもっています。 つまり、二分木は再帰的に - recursively - 定義されているのです。 二分木は、一見すると、シンプルなデータ構造です。リンクリストのように、そこ で動く基本となるコードも簡単だし、追跡も容易です。しかしもし他に、つりあい - balancing - のような要件が加えられたときには、複合的 - complex - になって 、非常に高速になります。 この tutorial ではつりあいについては扱いません。将来連載することに期待して もらえれば ... 2005-07-16 φ(-_-) ■ [lang]はじめての C 「二分木 2」 木 - tree - は、木のそれぞれの要素を必要としないどんな操作でも、計算時間 - time complexity - がその木の高さ - height of tree - と等しくなるという、も ともとの特性をもっています。 その結果、高さが最適に近ずくという条件では、非常に良好な性能になります。 二分木探索で、(あらかじめ) ソートされているデータ、または 1, 5, 2, 4, 3 の ように交互に組まれたデータを使って構築すると、二分木のそれぞれのノードは、 たった 1つだけ通路 - path - をもつことになります。 これだと、基本的にはリンクリストですので、二分木のもつどんな利点も吹き飛ん でしまいます。 可能な一番いいやり方として、上で述べた 2つのケースのような形を、絶対生じな いようにするのが安全です。 多くの場合実行に移すには、基本的な二分木で十分です。しかし、どのような入力 でもその高さが適切なものになるという保証が必要とされることがあります。 そのときには、つりあい - balancing - の複雑な領域を採り入れます。 つりあいについては、将来の tutorial に、短くまとめたトピックにして補充する ことにしましょう。 2005-07-17 φ(-_-) ■ [lang]はじめての C 「二分木 3」 二分木での構造体を定義したコードです▽ struct Node { int data; struct Node *left; struct Node *right; }; 簡単にするため、この tutorial ではノードの値は整数型に決めておきます。こう することで例題のコードが簡単になるのですが、この木 - tree - のままだと、他 で役にたつとはいえません。一般的に扱えるよう変換したものは、このサイトの中 にあるソース群で供給してあります。ただし、経験をつむためには、まず始めに自 分自身で試みることですね。 この tutorial では、ノードへのポインタを使って直接、操作しています。実際に 応用するには、Tree という構造体を 1つつくって、その内部に多くのものを納めま す。例えば▽ struct Tree { struct Node *root; /* Other useful info the tree */ }; こうすることで、木 - tree - は少しばかり簡素化され、より有益な情報、例えば 木の高さやノード数などを含ませることができます。しかし、表示化されることで 起こる mental な複雑さが加わることによって、少なからず難しくなってきます。 そこで、このような明らかに上級のセットアップについては、扱わないことにしま しょう。 しばしば役にたつ、シンプルな関数を定義してみます。これは、新しいノードを作 成するためのもので、何度も繰り返される労力から開放してくれるのです。ではや ってみましょう▽ int new_node(struct Node **node, int value) { *node = malloc(sizeof(**node)); if (*node == NULL) return 0; (*node)->data = value; (*node)->left = NULL; (*node)->right = NULL; return 1; } (追記) ちょっと訂正 2005-07-18 φ(-_-) ■ [lang]はじめての C 「二分木 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 のような特別のものについては、後で始めることにしまし ょう。 2005-07-21 φ(-_-) ■ [lang]はじめての 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 2005-07-24 φ(-_-) ■ [lang]はじめての 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：なにかのコトワザ ? 2005-07-27 φ(-_-) ■ [lang]はじめての C 「二分木 7」 構築したり、二分木から要素を削除する基本的な操作は手に入れました。また、木 に要素があるかどうかを調べるコードもあります。 さて、あると考えたものが、実際にあるのかを、はっきり確かめる必要があります よね。それは、木を渡っていくか、または各ノードをたどっていき、それである作 業を行うことで可能です。 再帰を使った走査 - traversal - 関数によるコードでは、上りの - ascending - ソート順で、各ノードの値をプリントしていきます。これは inorder 走査とも呼ば れます▽ void btree_walk(struct Node *tree) { if (tree == NULL) return; btree_walk(tree->left); printf("%d ", tree->data); /* <- ここが inorder */ btree_walk(tree->right); } この操作は、再帰をわかっていれば、すぐ明らかになります。*1 はじめに左の分肢をたどっていき、折り返してから - on the way back out - プリ ントします。それから、右の分肢をたどってプリントします。 上の関数からわかることは、これが再帰の実行であって、二分木探索ではないとい うことです。それで動き回る - move on - のです。 inorder 走査は、もっとも一般的な走査のやり方です。他に (走査には) postorder と levelorder と preorder とがあります。 postorder は木をこわしていくのに役にたちます。まず左と右の両方の分肢を訪れ てから、ノードへの操作を実行します▽ void btree_destroy(struct Node *tree) { if (tree == NULL) return; btree_destroy(tree->left); btree_destroy(tree->right); free(tree); /* <- ここが postorder */ } も一つ再帰がわかってない ... *1：小さい node からプリントされていく 2005-07-28 φ(-_-) ■ [lang]はじめての C 「二分木 8」 それぞれの走査は、stack か queue のどちらかを使うことで、再帰を用いることな しに、実行させることができます。一つのやり方として反復版で inorder 走査を書 いてみましょう▽ void tree_walk(struck Node *tree) { struct Node *node = tree; struct Node **stack; int top = 0; int height; height = tree_height(tree) + 1; stack = malloc(height * sizeof(*stack)); for ( ; ; ) { while (node != NULL) { stack[top++] = node; node = node->left; } if (top == 0) return; node = stack[--top]; printf("%d ", node->data); node = node->right; } } 多くの場合、反復法は最良の選択です。しかし経験からいえば、そんな機会はほん のわずかです。複雑なことが求められたと確信するその時までは、よりシンプルな 方法を用いるのがいいでしょうね。 それと、注意ぶかい人なら、この反復版 tree_walk 関数になにか潜ませてるのに気 づくでしょう。そこに記されてる tree_height 関数って何なんでしょうか ? そう、これは二分木の高さを得るための役にたつ関数です。 高さ - height - とは、null ポインタに行き着くまでにたどることのできるノード の最大数のことです。 つぎの木だと、高さは 2 になります▽ ...4... .2...6. 1.3.5.7 また、root までの数を数えようとするため、tree_walk では、stack に "高さ + 1" 分のポインタを割り当てています。 きっと、この tree_height のコードを見てみたいでしょうね。それはこうなります ▽ int tree_height(struct Node *tree) { int left_height; int right_height; if (tree == NULL) return -1; left_height = tree_height(tree->left); right_height = tree_height(tree->right); if (left_height < right_height) return right_height + 1; else return left_height + 1; } この tutorial で串ざしに - flesh out - しておいた操作のたぐい - operations - を使うことで、二分木を用いて、広い範囲にわたって作業をすることができるよ うになります。えっ、あざやかだって ? :p 2005-07-31 φ(-_-) ■ [lang]はじめての C 「二分木 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 2005-09-18 φ(-_-) ■[lang]はじめての C 二分木の挿入プログラムがやっとできた ... /* b_insert.c */ #include #include struct Node { int data; struct Node *left; struct Node *right; }; int new_node(); int tree_insert(); void btree_walk(); int tree_height(); main() { int value; struct Node *root; root = NULL; while (scanf("%d", &value) != EOF) tree_insert(&root, value); btree_walk(root); putchar('\n'); printf("%d\n", tree_height(root)); return 0; } int new_node(struct Node **node, int value) { *node = malloc(sizeof(**node)); if (*node == NULL) return 0; (*node)->data = value; (*node)->left = NULL; (*node)->right = NULL; return 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; } } void btree_walk(struct Node *tree) { if (tree == NULL) return; btree_walk(tree->left); printf("%d ", tree->data); btree_walk(tree->right); } int tree_height(struct Node *tree) { int left_height; int right_height; if (tree == NULL) return -1; left_height = tree_height(tree->left); right_height = tree_height(tree->right); if (left_height < right_height) return right_height + 1; else return left_height + 1; } コンパイルして、random.txt を使って確認。 $cc -c b_insert.c $cc -o b_insert b_insert.o $./b_insert < random.txt 2005-09-21 φ(-_-) ■[lang]はじめての C 次は二分木の削除。できればキーボードから入力したいのだが、どうもうまくできない ので、ヘッダファイルに書き込むことに ... /* b_delete.c */ #include #include #include "b_delete.h" struct Node { int data; struct Node *left; struct Node *right; }; int new_node(); int tree_insert(); void btree_walk(); int tree_remove(); main() { int value; struct Node *root; root = NULL; while (fscanf(stdin, "%d", &value) != EOF) tree_insert(&root, value); btree_walk(root); putchar('\n'); printf("remove > %d\n", DELETE); tree_remove(&root, DELETE); btree_walk(root); putchar('\n'); return 0; } int new_node(struct Node **node, int value) { *node = malloc(sizeof(**node)); if (*node == NULL) return 0; (*node)->data = value; (*node)->left = NULL; (*node)->right = NULL; return 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; } } void btree_walk(struct Node *tree) { if (tree == NULL) return; btree_walk(tree->left); printf("%d ", tree->data); btree_walk(tree->right); } int tree_remove(struct Node **tree, int value) { struct Node **prev, *node; struct Node *right, *heir; 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) *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); return 1; } 削除する数字を random.txt から選択し、ヘッダファイルを作成して*1 書き込んでおく 。 /* b_delete.h */ #define DELETE /* <- ここに 数字を記入 */ コンパイルして、random.txt を使って確認。 $cc -c b_delete.c $cc -o b_delete b_delete.o $./b_delete < random.txt *1：$vi b_delete.h 2005-09-06 φ(-_-) ■[diary]useless tips E. Kasner の「数学の世界」を読むと、数学の言葉と日常に使われてる言葉とのくいち がいについて述べられている。 数学には group, family, ring, simple curve, limit などというやさしい言葉が たくさんでてきます。 ただこれらの言葉は、日常の会話で使われるときよりも、ずっと多くの意味をもっ ています。 そして、それらのことばはますます専門的に使われるようになるにつれて、その数 学的な意味はいよいよわかりにくくなっていきます。 たとえば、function という言葉は、おそらく全数学史を通じて最も重要な概念をあ らわす言葉でしょうが、しかし多くの人々は function という言葉を聞けば*1 evening party ということを思うかもしれません。 そうだよね。プログラムの世界でも、function は関数と訳すけど、その働きはよく似て るが、正確には数学のそれとは別のものです。 recursive (再帰) なんて普通の英和辞典に載ってないし、token (トークン) もどう訳 したらいいかわからない。 その上、カタカナにしただけの用語にもヘンなのがある。 routine, sub-routine がど うしてルーチン、サブルーチンと表記されるのだろう。ルーティンではないの ? そりゃ名犬リンチンチンはリンティンティンとはいわないけど、妖精のティンカーベル はチンカーベルじゃないでしょう ! などと文句いってますが、7月16日分の日記では、 Trees have the natural property that the time complexity of any operation not involving every element in the tree is equal to the height of tree. This results in very good performance provided the height is close to optimal. のところを、なんだかな〜という訳しかたをしてる。次のほうがわかりやすい気が ... 木 - tree - にはもともと、木の各要素に依拠することなく、どんな操作において も、その計算時間 - time complexity - が、木の高さ - height of tree - と等し くなる (比例している) という特性をもっています。 その結果、(木の) 高さを最適なものに近づけることで、非常に良好な性能が引き出 せるのです。 読み返すと、いろいろアラがでてきそうで、ちょとコワイ ... *1：U.S.A.だと