部分 - みる会図書館

1. UNIX MAGAZINE 2003年2月号

特集・プログラミング入門図 11 子と弟の表現をニ分木としてみるさきはどの定義を使うと、プログラムは次のようになります。 tree search(tree t , etype key) 1 2 3 5 int ; if (t = = NULL) return NULL ; if ((i t—>elem ー key) return t ; if (i > 0 ) return search(t—>left , key) ; else return search(t—>right , key) ; 二分木のデータ構造は再帰的データ橢匿なので、この関数も再帰関数として実現しています。より効率のよい探索関数を作ることも可能ですが、これについてはもうすこしあとて紹介します。二分探索では酉冽カイ吏えるため、探索の対象となるレコード以外のよけいな領域は必要ありませんでした。ところが、こ : 分探索木を利用する場合は明カ勺に冓造を作らなければなりません。したがって、リンク尉寺するための領域が必要になり、実際にリンクにするデータも代入しておかなければなりません。このように書くと、二分探索木を利用するガ去は二分探索とくらべてまったく利点がなさそうに思えますが、そんなことはありません。二分探索で大きな間題になるデータの j 助日は、二分探索木を利用する舌を探索に戻しましよう。ここまでみてきたように、図場合にはあまり間題にならないのです。 3 で示した探索が進められる様子は二分木になっています。この木には 1 つ特徴があります。この木を通りがけ順二分探索でデータの追加が大変なのは、追加後のデータで走査すると、データか」しているのです。見方を変えを整列しなおす必要があるからです。一方、二分探索木にると、あるノードに注目したとき、その左部分木に含まれデータを追加する場合は、冓造の適当な位置をみつけ、るノードは親のノードのもっデータよりも小さな値をもっそこにデータを自由に追加することかできます。この挿入ていますし、右部分木に含まれるノードは親のノードのもする際のコストの低さが、二分探索本を使うガ去の大きなつデータよりも大きな値をもっています。利点です。二分探索では、あらかしめ整列した、、配列 " を準備しまこで、 1 ~ 7 の整数をノードとする二分探索木を考えしたが、この二分木を直接準備していたらどうでしようてみましよう。おそらく、図 12 のような冓造がい浮か。探索する値と本比 ) ノードの値とを上交し、一致していかぶのではないでしようか。れは探索は終了です。一致しない場合は、探索する値と根たしかに、この牙冓造は二分探索木の条件を満たしていの値とを上交し、探索する値のほうが小さければ左部分木ます。どのノードをとっても、その左部分木にあるノードの処理に、探索する値のはうが大きけれは省部分木の処理より大きな値であり、右部分木にあるノードよりも小さなに秘します。それぞれの部分木の処理は、根のノードの値になっています。ところが、これらのデータから構築で処理と同しです。きる二分探索木はこれ 1 つだけではありません。たとえ 7 = 0 ) 8 クをもっているため、実際に作られる橢匿は二分木とは異なります。しかし、図 10 から親へのリンクを取り除いてノードの位置をーれば、できあがる構造は二分木とみなすこともできます ( 図 11 ) 。この二分木を行きがげ頂て処理すると、 1 、 2 、 3 、 4 、 5 、 6 、 7 、 8 となるのが分かるでしよう。これは、もともとの木での行きがげ頂でもあります。また、新たに作られた一分木を通りがげ頂て処理すると、 3 、 4 、 2 、 6 、 7 、 8 、 5 、 1 となります。これは、もともとの木では帰りがげ頂になります。二分木の行きがけ順や通りがけ順での処理方法はすでにみましたが、それと同様なガ去で処理するだけで、木の行きがけ順や帰りがけ順での処理が可能になります。ニ分探索木一三ロ 110 UNIX MAGAZINE 2003.2

2. UNIX MAGAZINE 2003年2月号

特集・プログラミング入門図 27 削除にともなう一重回車云 1 3 2 図 28 削除にともなうニ重回車云 1 1 1 2 3 2 4 3 2 AV し木を扱うコード typedef enum { てみました。す。今回は、次のような列挙 (enum) 型を定義して使っ左右の部分木の高さの差を表す値をイ尉寺するだけで一ト分で持する必要があるように思えるかもしれませんが、実際はなけれはならないので、すべての部分木について高さを保ます、データ構造です。左右の部分木の高さを上交しました。す。そこで、今回は工ッセンスだけをとりあげることにしせんが、さきはどの二分探索木のプログラムの約 3 倍でテスト用のコードも入っているので正確な上師交にはなりまたためか、プログラムが巨大になってしまったからです。ます。というのも、アルゴリズムを忠実に実現しようとし・・と書きたいところですが、部分的な紹介に留めておきそれでは、 AVL 木を扱うコードをみていきましよう、 tooleft left even = 0 , r i ght tooright } balanced ; 118 2 3 ノードを表すデータ構造では、この値尉寺するため 4 UNIX MAGAZINE 2003.2 q—>balanced— q—>left = p; if (i > 0 ) { たに追加するノードです。次はそのコードの部分ですが、 q か親のノード、 p カ噺 anced の値を各します。加したあと、追加した位置にもとづいて親のノードの b 心の場合と同様です。問題は挿入後の卩髜各です。ノードを追挿入の操作については、ノードの挿入自体は二う対架索木く同じコードが使えます。されてはいますが、基本的には二 . 分探索木なので、まったす。 AVL 木は、罸造が適度にバランスするように工夫探索の操作自体は、二分探索木を用いた探索と同一でら冓造を操作するようにしました。す。そこで、親を孑一リンクを設けて、これも管理しなが親を効率的に参照できたほうカワ。ログラムが高速になりま AVL 木では親の様子を調べる機会がたくさんあるので、もう 1 つ加えたのは、親を表すリンクの parent です。まった場合は、整か必要なことを表します。 right か言午容示巨囲内で、 tooleft や tooright になってしのフィールド balanced を追加しています。 left 、 even 、

3. UNIX MAGAZINE 2003年2月号

特集・プログラミング入門図 24 1 図 25 1 一重回車云の好 2 図 26 1 ニ重云の好 2 日 3 3 ニ重回車訒要な告 3 2L 2R すれも同し高さのものです。 b の下にある部分木の高さが揃っています。このどちらかが 1 つ高く、そちらに新たなノードカ功日えられた場合、高さが 2 変わることになります。このとき、図の a に b が対応し、高いほうの部分木の根が b に対応するとみると、この図と同し形式になるはすです。一重回転をおこなうのは、この図の左側のケースです。この場合、図 24 のようなかたちにノードを回転します。この回転は簡単です。また、回転後の本の高さはもとここには描かれていないもとの料冓造と変わらないため、殞則のヨ寸冓 j を、、景か被及することもありません。難しいのは、右側のようなかたちになってしまったときです。この場合は、二重回転をしなければなりません。さきはど、二重回転には 3 つのノードか闕与すると書きましたが、この図では a と b の 2 つのノードしかありません。ノードをもう 1 つ追加した絵を描いてみましよう ( 図 25 ) 。この図では、新たに加えたノードを 2L の下に付けていますが、これが 2R の下にあってもアルゴリズムとしては基本的に変わりません。重要なのは、高さの等しい 2L と 2R のどちらかにノードが 1 つ付くため、それらが 1 や 3 の部分木と同し高さになる点です。ただし、 d 自身が」砌日されたノードという場合もあります。このようなときは、 UNIX MAGAZINE 2003.2 左右の部分木は高さ 0 て等しいことになるので注意が必要です。また、 1 や 3 の部分木は空になりますから、 d の左右の部分木はどちらも 1 や 3 と同し高さになることになります。さて、これを二重回転すると図 26 のようになります。この場合も、回転した結果、本の部分木の高さはノードの j 助日前と変わらないので、さらに外部について景を調べる必要はなくなります。削除についても考え方はです。ます、二分探索木の場合とに削除を実行します。たとえば、左右両方の子をもつノード x を削除するときは、代わりになるノード Y をみつけ、これとノード X とを交換し、簡単に削除できる位置に移動させたノード X を実際に削除するのです。もちろん、木のバランスか削巣作によって崩れるので、この場合にも調整が必要になります。これにも一重回転と二重回転の 2 不頁があります。一重回転は、挿入のときの一重回転の反対のような操作になります ( 図 27 ) 。この図は、薄く描いた c のノードを削除した様子を表しています。この変換では、処理前と処理後とで部分木全体の高さか変わってしまうため、この変更がほかに景界些を与えるかどうかをヾる必要があります。なお、 2 の部分木はもう 1 つ高いものでも同し処理をおこないます。その場合は、変更後の部分木の高さは変わらないので、はカの景斧些を調べる必要はありません。削除にともなう二重回転も、やはり挿入における二重回転の反対のような動きになります ( 図 28 ) 。 2 や 3 の部分木のいすれか片方は、図よりも 1 つ短い可能性があります。しかし、いすれにせよ部分木全体は 1 つ短くなるため、この場合もやはりはかの部分での景グを調べる必喫があります。 117

4. UNIX MAGAZINE 2003年2月号

特集・プログラミング入門両方の子をもつ / ードの削除図 18 図 16 子をもたないノードの削除図 17 片方・をもつノードの削除ノード " を満たしています。もちろん、右部分木の一番左のノードについてもまったく同様です。代わりに根とすべきノードをみつけたら、そのノードの子を親に耐妾つないだあと、みつけたノードを根に移動します ( 図 18 ) 。置すれば、二分探索木の生質尉寺できます。したがって、それでは、実際に削除を実行する関数をみてみましょ親のノードのリンクに、削除したいノードがもっ子を代入う。作成した関数の前半では、目的の値をもつノードを検すれはいいでしよう ( 図 17 ) 。索しています。この部分は、挿入をおこなう関数とたいへこの図では、左の子だけをもつノードを削除していますんよく似ています。が、右の子だけをもつノードについてもまったく同様に削除できます。 delete(tree t , int key) 削除したいノードが両方の子をもっている場合は厄介です。このノードを削除すると 2 つの子に対するリンクか鞘えてしまうため、親からのリンクだけで両方を一尉寺することはできません。このようなケースでは、削除するノードを根とする部分木のなカ功、ら、削除するノードの代わりに根となることができ、かっ削除か容易な位置にあるノードをみつけ、そのノードと根のノードを交換してから目的のノードを削除する処理が必要になります。こで間題になるのは、新たに根となるノードのみつけ方です。これは、左部分木のなかでもっとも右に位置する re turn NULL ; ノードか、右部分木のなかでもっとも左に位置するノードノードをみつけるだけなら探索の関数と同様にしてもよをみつければいいでしよう。左部分木にあるすべてのノーさそうですが、あとでノードを削除することを考えると、ドの値は、根のノードの値よりも小さいはすです。そのなそのノードを指しているリンクも記慮しておきたくなりまかで一番右にあるノードは最大の値をもっているはすですす。だからこそ、探索よりも挿入の関数によく似たものとから、左部分木のはかのどのノードよりも大きな値をもつなっているわけです。はすです。さらに、このノードのもつ値は右部分木のどのこの関数は、指定したノードを削除するためのものなのノードのもつ値よりも小さいはすですから、ちょうど、根で、削除すべきデータがみつからなかったらそれで終了しのノードとしての条件を満たすことになります。さらに、左部分木の一番右の子ということは、それよりも右側に子ます。その場合には NULL を返し、削除していないことがいないことを意味します。つまり、すくなくとも右の子を示します。は存しないことが分かっているわけです。すでにみてき削除すべきデータをみつけたときは、 goto 文を使ってたように、これはもう 1 つの条件である、、削除が容易なラベル found までジャンプします。ラベル found の部分 Q) Q) V V ・ 1 while (p ! = NULL) { if ( (i = p—>val ー key) goto found ; else if (i > 0 ) else = 0 ) 114 UNIX MAGAZINE 2003.2

5. UNIX MAGAZINE 2003年2月号

特集・プログラミング入門 } else { q->right = p; q—>balanced + + ; i は追加するノードの位置を調べる際に利用している変数で、正なら左部分木に、負なら右部分木に追加します。ノードを追加したあとは、 j 助日した部分木の高さが 1 増えるため、親のノードの balanced の値を訓整しています。この訓整では、列挙型の定数ではなく、整直であるかのように扱います。左部分木に追加したときはデクリメントし、以前に even であったなら left に、以前に right であったなら even に変更されることになります。バランスの訓整は、いま balanced の値を修正した親のノードから順に、根のノードに向かっておこないます。 for (p = q; p—>parent & & p->balanced ! = even;=> p = p¯>parent) { さきほど、図を示しながら説明したときに外部への景グの有無について触れましたが、外部に対して景グがなければこの検査を終了します。親が left か right の場合、いまおこなった追加によって部分本か高くなったことが分かります。そのため、この変史をさらにその親 ( 祖父 ) に伝播するために、値の調整をおこないます。 if (p—>balanced left Ⅱ right) { p—>balanced if (p->parent—>right p¯>parent—>balanced + + ; else p¯>parent—>balanced— この場合、親は大丈夫でも、その祖先のなかにはバランスが崩れてしまうノードがあるかもしれません。そこで、ループに戻ってチェックを続けます。親が tooleft の場合には、回転処理か必要です。このときの左部分木を q とすると、 q が le 仕状態であれは一重回転で対応できます。 } else if (p—>balanced q = p¯>left ; if (q—>balanced = left) { / * 一重回転で OK * / この処理をおこなう部分は省略しますが、一重回転を実現するコードです。左部分木が right であれは、二重回転 tooleft) { UNIX MAGAZINE 2003.2 が必要になります。 } else if (q—>balanced = right) { / * ニ重回転が必要 * / もちろん、こにも二重回転をおこなうコードがありますが、これも省略します。これら以外、つまり左部分木が even ということはありえません。図 23 において、左側であれは・ 2 の部分木が、右側であれば 1 の部分木が 1 つ高い場合になります。ところが、このような状態だとすると、ノード c を追加する前にノード a において左右の部分木の高さが 2 以上異なるので、調整されていることになります。よって、 even にはなりえないわけです。そのため、もしこのような状態になったら、その旨を示す工ラーメッセージを出力するようにします。 } else { fprintf (stderr, break; "This can' t happen\n" ) ; また、これらの処理により、部分木全体の高さがノードを追加する前と同しになるため、さらに祖先を調べる必要はなくなります。そこで、 break を用いて祖先をたどる for ループを抜けています。このあと、はは 1 司じ内容で right と left を入れ替えたコードか読き、 for ループを終了します。一方の削ド作のほうも処理は同様です。ます、二分探索木における削除をおこない、削除したノードの親からバランスを調整します。挿入の場合には、次のようなコードを用いて自分カ襯の右の子なのか左の子なのかを判断することができました。 p¯>parent—>right ところが、ノードを削除してしまうと、削除したノードがどこに付いていたのかカ喇断できなくなります。そこで、どちらの子を削除したのかが分かるように新たな変数を設けました。さらに、削除したときに注目している部分木の長さが処理によって短くなったかどうかを示す変数 (shorten) も設けています。これは、挿入の場合とは異なり、削作ではイイ系で実行した削除の景グが、回転処理をおこなっても祖先まて伝播することがあるためです。バランスをとるためのコードでは、やはり親ノードと子ノードの balanced の値にもとづいて場合分けをおこないます。それぞれの場合に一重回転や二重回転を実行し、さ 119

6. UNIX MAGAZINE 2003年2月号

特集・プログラミング入門図 20 1 を挿入する前の豈 5 3 7 6 2 ただし、 4 図 21 1 図 23 図 22 0 1 1 の挿入後の告 5 0 を挿入し、回転したあとの告 6 7 5 3 2 1 4 このガ去ではさまざまなキーのデータの」助日・削除を繰り返していると、死んでいるノードか彳余々に増え、探索の手間もよけいにかかります。この点には注意が必要です。 AVL 木二分探索木を使うと、平均的には効率よく探索がおこなえますが、都合の悪い入力が与えられたときはれに比例する手間がかかってしまいます。最悪の場合もこれほど手間がかからないように、 : 冓造をある程度バランスさせるようなイ督はみも考えられています。これを、、平衡化 " と呼び、このような仕組みを採り入れた冓造を、、平衡木 (balanced tree)" と呼びます。二分探索木に対して、、回転 " という操作を定義し、ある程度バランスさせるようにした平衡木が AVL 木です。この名称は、考案者である G. M. AdeI'son-VeI'skii と E. M. Landis の名前にちなんだものです。 AVL 木は、 2 つの兄弟を根とする部分木の高さがたかだか 1 しか異なっていないという性質をもっています。 : 冓造をバランスさせるのであれば、つねに木を一にしておくのがもっとも効率的です。しかし、そのための手間は無視できるはど小さくはありません。図 20 を見てください。この図のイ冓造に値が 1 のノードを追加したとき、木を一杯にするには、図 12 のような冓造に変更する必要があります。このとき、 2 ~ 7 の既存のすべてのノードでは、親となるノードか変更されています。つまり、この処理はどうがんばってもれに上 tf 列する手間がかかってしまうのです。 AVL 木では、兄弟を根とする部分木の高さが 1 違っていてもよいので、値が 1 であるノードを追加して、図 21 のように少々いびつな構造になっても許容されます。この料冓造に対し、さらに 0 を値とするノードを追加 116 3 2 4 7 6 ノードの挿入によってパランスが覇れる本好 3 2 1 3 2 すると、 2 のノードの左右の部分木において左側は高さが 2 、右側は高さが 0 となり、高さの差が 2 になります。そこで、回転操作をおこないます。こ巣作は、根のノードの左の子を新しい根とし、もとの根のノードをその右の子とします。さらに、新たに根となったノードのもとの右の子は、もとの根のノードの左の子とします。この操作により、冓造は図 22 のようになります。回転には、 2 つのノードカ与する、、一重回転 " と 3 つのノードが関与する、、二重回転 " があります。上記の、 0 を挿入したときにおこなわれた回転は一重回転です。一重回転がおこなわれる様子をみてみましよう。 AVL 木として羽厮している : イ冓造にノードが追加されてバランスカ繃れる場合には、図 23 の 2 通りがあります ( もちろん、これの左右対称の状態になることもありますが、それは反転して考えてください ) 。この図のなかで三角形て表している 3 つの部分木は、い UNIX MAGAZINE 2003.2

7. UNIX MAGAZINE 2003年2月号

図 12 図 15 探索の手間かれに上錮」するニ分探索木 1 図 13 1 図 14 1 特集・プログラミング入門 1 ~ 7 のニ分探索木 4 2 3 6 7 6 5 5 7 もう 1 つのニ分探索木 3 2 6 4 5 7 造らしくないニ分探索木 7 4 5 3 6 2 UNIX MAGAZINE 2003.2 を見ると、探索の手間がれに比例する理由もすぐに分かるかりやすいのは、図 15 のような冓造でしよう。この図れに上 tf 列する手間がかかってしまいます。図 14 よりも分きはどの図 14 に示したようなオ冓造では、探索するのにまったく意味をなさない場合があるのです。たとえは、さ悲参な結果になります。一所懸命に冓造を構築しても、一方、最悪のケースでは、二分探索木を用いた探索では手間は二分探索と同様に 1 。 g れに上第」します。分探索における探索経路とまったく同しですから、探索のこのとき、二分探索木を用いた探索で採られる糸各は、いのは、図 12 のような完全二分木になっている場合です。カ躱索の手間に大きく関係してきます。もっとも効率がよここ分探索木を用いた探索の場合には、二 . 分探索木の構造ニ分探索木を用いた探索の手間と冓造とはかけ離れたものになってしまいます。この程度なら、また冓造といえますが、図 14 になるば、図 13 のようなものも考えられます。 4 3 2 1 111 ばなりません。そこで、リンクされたリストのときと同様ますが、今回は根のノードの処理だけ特別扱いにしなけれ根のノードは木を指すポインタで直孑旨し示すこともできタをもたない葉のノードは、 NULL て表すことにします。と、根のノードの扱いを決めておかねばなりません。デーいことがあります。木の表現ガ去です。葉のノードの扱いもう 1 つ、プログラミングを始める前に決めておきたも、コードの基本部分はそれほど変わりません。法で実現してみましよう。親へのポインタを利用する場合と削幇です。この場合は、親へのポインタを使わない方こで、親へのポインタが必喫になるのはデータの挿入時ら、二分木のデータ構造をそのまま使うことができます。探索木はノードに値をイ尉寺することができる二分木ですか最初に、木の表現を決定しなければなりません。二分ましよう。それでは、ここ分探索木を扱うコードをみていくことにしニ分探索木を扱うコ - ドれでも、一杯に近いバランスのとれた木になるのです。ーーなな二分木になることはますないと思いますが、そ与えられたとき、できあがるヨ冓造か完全二分木になった手間にかかる定数の部分が異なります。入力がランダムにます。ただし、最良の場合とまったく同じわけではなく、きは、最良の場合といに log れに出列する手間がかかり雑になるので省きますが、ランダムな入力が与えられたとかる手間はどのくらいになるのでしようか。計算はやや複最良と最悪の場合の手間は分かりましたが、爿」的にか悪の場合にはれに上 tf 列する手間がかかってしまうのです。のよいときは 1 。 g れに上ける手間でおこなえますが、最このように、二分探索を用いオ酩は、もっとも効率のではないでしようか。

8. UNIX MAGAZINE 2003年2月号

写真 1 PDA と携帯舌合 Handspring Treo 270 Communicator ( 左 ) と T Mobile Pocket PC Phone Edition ( 右 ) 連載 UNIX Communication Notes—@ になる PC と情報を同期させる機能 ) はよくできているので、たとえばふだんは PC で管理している住戸形求なども、手軽に期させることができる。また、ポイスメールや FAX なども、自宅やオフィスの PC で受け取ったものを PDA にコピーして再生するといった使い方も十分に考えられる。こうなってくると、真の意味でのモバイル環境とオフィス ( またはホーム ) 竟の融合か期待できる。ところが、残念なことに、日本ではこの種の製品がまったくない。たんなる擱則だが、なんらかの規制があって携帯電話端末として認定されないとか、携帯電言末のメーカーからの圧力があるとか、あるいは、携帯電話サービスを提供する企業は本当は PDA が大嫌いであるとか、そうはつらいのも事実である。その理由は、次の 3 点に集約でいった理由でもあるのだろうか。技勺にはとくに困難なきる。部分はなく、十分に実現可能と思えるだけに、なせ登場し・ 2kg 前後と重い。ないのかか不思議でならない。・バッテリーでは、せいぜい獅間程度しカ硬えない。 NTT DoCoMo や au 、 J- フォンなど秀帯電話サー携帯電話端末などとくらべると手軽には使えない。ビス会社が、本当に第 3 世イ秀帯電話を普及させたいと願っているのであれば、コンピュータとの本格的な連まや携帯電話端末だけでは機能不足だからラップトップ PC データ通信を中心とした利用形態をもっと強く打ち出すべも持ち歩く、という考え方は分かるし、私自身も日頃からきであろう。ぜひとも、 PDA と携帯電話端末との融合を実践している。とはいえ、携帯電話の軽央感を失うのはや真剣に検討してほしいものである。はり残念である。そう思っている人はかなり多いらしく、このジレンマをセキュアな WWW サービス鮹夬する新たな製品か登場し始めている。残念ながら日本では販売されていないが、 PDA と携帯電話を合体させた前回は、 X. 509 証明書とその利用力法の各を述べた。製品である。丐点では PDA と GSM 携帯電話を組み私たちが入手できる X. 509 証明書は、次の 2 種類で合わせたものが大部分で、携帯電話としての機能は第 2 世ある。イ秀帯電話、すなわち狭帯域サーピスしか使えない点か残念ではある。・ WWW サイト側の証明書写真 1 を見れば分かるように、これらの製品では PaIm これは WWW サーバーの素生を明らかにするための OS や Pocket PC を載せた PDA に携帯電話のダイヤラ証明書である。 WWW サーバー側で SSL/TLS サーーカ咐いており、通常の音声通話もできる。則の Hand- ピスを提供するときに必喫となる。 spring 製の端末では、イヤスピーカーとマイクカ埔ⅱ面の・個人用証明書カバーに組み込まれていて、通話中もボタンやタッチセこちらはネットワーク・サービスを利用するユーザーンサーの部分に身体の一黯にが触れないように工夫されていの、、身分証 " である。こ刎固人用証明書を使ってアクセる。インターネットへのアクセスについては、 GPRS とス制御をおこなったり、あるいは、電子メールに付ける呼ばれる GSM 携帯電話システムのバケットサービスを電イ署名を生成したりすることかできる。利用する。今回は、最初にセキュアな www サーピスの構築方第 3 世秀帯電話にもこういう製品が登場すれば、本法について述べる。つまり、 WWW サーバーとクライア格的な情報処理と携帯電話の利点を活かした使い方ができントとのあいだの通信が SSL/TLS によって暗号化さるはすである。現在の多くの PDA の同期機能 ( べース ← ( 415 ) 555 ・す 2 を 3 をいル 42 UNIX MAGAZINE 2003.2

9. UNIX MAGAZINE 2003年2月号

特集・プログラミング入門に、地頁にダミーのノードを追加することにします。変数として木尉寺する場合は、このダミーノードを指し示します。これによって、木の根のノードを変更する場合も、もともとの変数を変更する必要がなくなります。これらの点を考慮してプログラムを書くと、 : 冓造のデータを匆祺月化するコードは次のようになります。 typedef struct —node { struct _node *1eft ; struct _node *right ; int va1 ; } node, *tree; initialize 関数でネ川月化された冓造を返しますが、ノードを 1 っ作り、右の子 (right) に NULL を代入することで冓造が空であることを示しています。左の子 (left) と値 val は、利用することはありませんが、一応 NULL や 0 で期化しておきます。次はデータを追加するコードを・・・・・・といきたいところですが、ぐっとこらえて、データを探索するコードをさきにみておきましよう。さきはど示した探索のためのコードでは、再帰関数として関数を実現していました。関数をよくみていくと分かりますが、探索をおこなうのは末尾再帰の関数です。したがって、簡単に区し関数に変換するこ t , initialize(void) tree t; (tree)malloc(sizeof(node)) ; t t->left = t—>right = NULL; t—>val = 0 ; return t ; 初のダミーノードの扱いを加えると、関数の部分は次のよとカきます。再帰関数を縄区し関数に変換し、さらに最うになります。 search(tree tree p; int int key) p = t—>right, while (p ! = NULL) if ()i = p—>val ー key) return p ; else if (i > 0 ) 112 p = p¯>left ; else p = p->right; return NULL ; ます、根のノードを指すために right をたどっています。これによって、ダミーのノードを読み飛ばしています。その次は、再帰関数を縄区し関数に変換した部分です。その終了条件は、注目するノードが NULL にならない、つまりデータか存在するあいだという系お区しです。注目するノードが NULL になるようなときは、目的のデータがないことが分かるため、すぐに探索の失敗を示す値 (NULL) を返せます。一方、ノードにデータがある場合は、その値と探索する値とを上交します。これらカしければ注目しているイゞ目的の値になりますから、目的の値がみつかったことを示すために、そのノードのアドレスを返します。両者カしくなければ、 2 つの値の大小関係をヾて次に探索すべきノードを決定します。 : 冓造のノードのほうが大きな値であれは方の子を、小さな値であれば右の子を次に探索します。この関数では、ループを 1 度まわるたびに right か left のリンクを 1 回たどるため、対象とするノードのレベルがかならす 1 すっ増えていきます。二分探索木の高さは有限ですから、このプログラムはいつかは停止することになります。木構造か適度にバラけていれは、この木の高さが 1 。 g れに比例する値となるので、探索も 1 。 g れに上 tf 列する手間でおこなえるわけです。次は、レコードを追加するための関数をみてみましょう。二分探索木にデータを追加する場合は、ます、追加し UNIX MAGAZINE 2003.2 これらの処理をおこなうための関数は、次のように作れにすることができます。加して値を登録すれば、二分探索木の条件を満た、・すを冓造の場合は、ちょうど注目している位置に新たなノードを追に葉に到達していて、 NULL となっているはすです。データが求されていなければ、注目するノードはすで録されているデータのノードのアドレスを返します。重登録はエラーとして扱っているため、関数ではすでに登ていることになり、 . : : 重疆こなります。この例では、るデータがみつかったら、同しキーの値がすでにイ求されたいデータをキーとして探索を実行します。これで対応す

10. UNIX MAGAZINE 2003年2月号

特集・プログラミング入門図 5 根を上に描いた木図 6 造の用語 ( 1 ) ・ノード ( 頂点、節点 ) 糸目系冓造を表す図などにも似ています。図 5 では、ある点から 3 本の枝カ咄ているものもあるのでトーナメント表にたとえるのはやや無理がありますが、組であれば 1 点から 3 本以ーヒの枝カ咄ていても不思議ではありません。 : 冓造の構成要素を示すために使われる用語には、糸目織図と似た構造をもつ家系図 (family tree) から借用したものがたくさんあります。 : イ冓造の用語について、簡単に説明しておきましよう ( 図 6 ~ 7 も見てください ) 。ます、さきはど冓造における、、点 " と呼んだ部分は、ノード、項点、節点などといいます。ノードどうしを結ぶ線は、リンク、辺、枝などといわれます。冓造のノードのなかで、、根 " と呼ばれるものが 1 つだけあり、これはその他のノードとはすこし異なる性質をもっています。討冓造として表現する場合、根を上に配置したときにリンクの上側にくるノードを親ノード、一ド側にくるノードを子ノードと呼びます。 : 冓造中のすべてのノードは、根のノードを除き、かならず 1 つの親ノードをもっています。 1 つの親ノードに複数の子ノードがある場合もありますが、これらの子ノードをまとめて、、兄弟 " と呼びます 1 。兄弟のノード間に順番がある場合、順番がさきのものを兄、順番があとのものを弟と呼びます。親や子という関係を 2 段 1 英語では sibling で男女の区別はないのですが、日 : 吾では適当な言吾リンク ( 辺、枝 ) リンク 106 がないので、とりあえす、兄弟 " とします。図 7 告の用語 ( 2 ) 祖先親 / ヾス子兄弟 (sibling) 子子孫葉階たどると、それそれ祖父や孫のノードとなります。あるノード ( 仮にノード A とします ) を中心としてみたとき、根からノード A まで到達するための経路をパス (path) と呼びます。ノード A へのパス上に位置するすべてのノードをノード A の、、祖先 " 、ノード A の子やその子たちをあるノードのパスの長さ、つまり、根のノードから対象ードを、、内部ノード " などと呼びます。のがあります。子をもたないノードを、、葉 " 、子をもつノありません。一方、ノードには子をもつもの、普通のノードには親がありますが、根のノードには親がすべてまとめてツ了孫 " と呼びます。もたないも UNIX MAGAZIN E 2003.2 は、二分木において、一番下のレベルを除くどのレベルに二分木が、、一杯 " であるということがあります。これ扱われます。区別するため、図 8 の 2 つの冓造は異なるものとして二分木では、左の子 ( 左部分木 ) と右の子 ( 右部分木 ) をます。ただし、実際には二分木を利用する場合がほとんどいているような冓造は、、多分木 (n-ary tree)" と呼はれるノードがもっ子の数がれ以下で、子のあいだに順番カ咐ことを、、二分木 (binary tree)" といいます。ー殳に、あというように ) 順番が付いています。このようなヨ冓造のつ以下に決まっていて、それぞれの子のあいだに佐と右さきほどの図 3 ク材冓造では、ノードのもっ子の数が 2 ( y 剽に描きます。構造を図示するときは、同じレベルのノードを同し高さとも大きいものをその木の、高さ " と呼びます。通常、木らに、木に含まれるすべてのノードのレベルのうち、もっはならないかを、、レベル " または、、深さ " と呼びます。さとするノードに到達するまで、何本のリンクを通らなけれ