連載 : し、 : し、 v6 図 5 申込書 ( 8 ページ ) ー・第第ぐ、 : 人し新円事に、物にををつあ 0 一日・をを、《だい・ ツ材ンツ、ンみ に正確に記入します。 NW 技旦当者連絡先 これも上記と同様で、申込者の連絡先と同しなら一番上 の欄をチェックするだけです。 重要なのは、障害などによるサービス停止情報を受け取 るためのメールアドレスです。 これは必須事項なので、 かならす記入してください。 請送付先 請求書の送付先を記入します。申込者か設置場所の住所 であれば該当する欄をチェックし、それ以外の場合は記 入します。 青求に関するこ靼当者 法人の場合は、技術担当と経理担当が違うのが普通で す。ここには、請求書を処理する担当者の情報を記入し ます。 支払方法 : ムいガ去お尺します。口座振替、請求書払い、クレ ジットカード払いの 3 つのなかから選び、クレジット カードの場合はカード番号などを記入します。 「こ刳用内容のこ内」送付先ー万 この項目には記入する欄がありません。「ご利用内容の 案内」には、インターネット , 材妾続するための認証用 ID とノヾスワード、メールサーピスのための ID とノヾス ワードなどの重要な情報が含まれています。送付先はモ デムと同かならす設置場所住所になります。 要するに、モデムもパスワードなどの重要情報も設置場 所に届けます、という石忍てす。 9 ページ ( 図 6 ) モデム 1 青報 2002 年 11 月の時点ではモデムは選択できないので、 書くことはありません。サーピス形態などの牛か記載 されているので、目をとおしておきましよう。 設置場戸泉工事情報 、、タイプ 2 のお客さまのみ記入いただきます " という括 弧書きがあります。ちょっと紛らわしいのですが、 れは可万設を希望する場合です ( デュアルサーピスの 、、プラン 2 " とは関係ありません ) 。 V 10 ページ ( 図 7 ) OCN サブドメイン申言劑青報 ローまロ第亠 ′′ ? い第をル′ - る・第、りを -3 れ 0 物 0 物載人、 0 レト 0- ド - 物でを講イを′い え・内気・ 1 ・・スにい : 第第、画今 0. 金′入 ( い : ロ . ロ % レジンをドによ嶐受い ・物キ 1 : : : つ、直 第を物す・、 : インタ - 第 , , 第・ 140 ー′・材・亠 . パスつ一ド物う第・・を : 第豊れでおいます . ・ドー第、 : つい「 . をこま第年、第に、物は物宿・↓、をを、にくことはぐき第せな 新たに申し込むのなら、 7 ページ目の最初にあるこの項 目は関係ありません。いままて利用していたサービスか ら移行する場合には、 N で始まる OCN お客さま番号 ( 請求書などに記載されています ) を記入し、オプショ ンお尺します。 IPv6 通信ご禾堋形態 プラン 2 お尺することにして先に進みます ( プラン 1 は、記入項目カヾ成るだけです ) 。 ADSL 品目 点では、、 8M 品目 " (8Mbps の ADSL サーピス ) だけなので、記入する項目はありません。 ADSL タイプ 通常の電話 ( アナロクを利用していて、 ADSL サ ービスを導入する場合は、タイプ 1 の共用型を尺する ことが多いと思います ( 私も、自宅の回線はそうしてい ます ) 。 ただし、 ADSL 回線を新設するほうがなにかと楽なこ ともあるので、とくに法人ではタイプ 2 を選ぶとよい かもしれません。 マ 8 ページ ( 図 5 ) 個人の場合は、申込者の住所と同じであれば、一番上の 欄をチェックするだけです。もちろん、自宅以外の事 務所などて利用する人もいるでしようし、とくに法人 であれば、実際に使う場所を指定することも多いと思い ます。そのような場合は、設置場所の担当者情報ととも 三 - ロ 設置場所イ沂 55 UNIX MAGAZINE 2003.2
SoIaris 特集 ・問題の現象 - ティンう ーエラー、警告などのメッセージ ( 省略せすに正確に ) ー間題に邑したとき窈状 ( 正しくない実行結異 常な動作、ハングアップ、システムダウンなど ) ・問題の発生する竟 —SunOS のノヾージョン ( 必彡却 ーハードウェアのモデル名 ー使用しているディスクやその他の周辺装置 ー使用しているアプリケーションとそのバージョン ーネットワーク竟の概要 不具合の発生頻度 UNIX MAGAZINE 2003.2 さまざまな情報が自動第勺に収集できる。 パッケージをインストールし、コマンドを実行するだけで (SunSolve Online からダウンロードできる ) 。これは、 て、 Sun から explorer というツールか提供されている 環境やハードウェア構成を調べるためのコマンドとし 際に取り出してヾる。 は、 ( めったに必要になることはないか ) ポードを実 (Programmable Array Logic) などのバージョン と prtdiag コマンドで市忍できる。それ以、タ ) PAL る。 CPU の ROM のバージョンは、起重加の表示 あるが、部品を分解しなければ分からないものもあ 型名は dmesg コマンドなどによって分かることも ン 一周辺装置の型名と ROM などがあれはそのバージョ いる。ポードの不職頁はパーツ番号で区別される。 Sun の製品は各ポードにバーコードのタグが付いて ー各ポードの不頁とバージョン ーポード、周辺装置の構成 ・ハードウェア構成 には、次のような報を j 助日する。 成に関する田な情報が必要になることもある。その場合 間題の性質によっては、使用しているハードウェアの構 問題の鮹夬か重要なのかを記す ) ・問題の重要度 ( 早期の鮹夬を求める場合には、なぜこの ー現象を再現させる手順 ー現象を再現させるためのプログラム が早い ) 不具合の再現方法 ( 下記のどちらかがあると間題の鮹夬 Sun に質間する場合、 explorer の実行によって得られ る情報の添付を求められるケースか増えてきている。この ツールは、新しい Sun プラットホームがリリースされる たびに更新カ功日えられている。したがって、使用するとき は、そのつど SunSolve Online からダウンロードする必 要がある。 explorer このツールを利用するときは、下記の点に注意する。 ・ソフトウェア、ハードウェアの新規リリースやバージョ ンアッフの際には、それに対応した explorer がリリー スされる。したがって、夫彳叔こはかならず SunSoIve O ⅲ ine から職万のパッケージをダウンロードしたうえ で情報を取得する。 ・大きなシステムでは取得する情報量か増えるため、実行 の終了までにかなりの時間がかかる。 ・さまざまなデバイスにアクセスして情報を取得するた め、ふだんは使っていないテンヾイスのバグなどにより、 うまく実行できない場合がある。 ダウンロード SunSoIve OnIine にアクセスし、 のところにある、 ・ Explorer Data C011ector 、パッチ分析ッ ーノレ ' のリンクをクリックする。さらに、表示されたページの上 のほうにある、、 View License Agreement and Down- load Explorer" をクリックし、ライセンス許諾条件を読 んで [Agree] ボタンを押すとパッケージがダウンロード できる。 執芋点 ( 2002 年 12 月中句 ) での最新版は 3.6.2 で、 ファイル名は SUNWexplo.tar. Z である ( ファイルサイ ズは、圧縮ファイルが 544 971 バイト、伸張後の *. tar ファイルが 1 , 082KB ) 。 インストール explorer のインストールは、以下の手順でおこなう。 凵石宿ファイルの展開 ダウンロードしだ宿ファイルを伸張し、 tar コマンド で展開する。 31
連載 /UNIX Communication Notes— 1 76 さらに WWW サ→ヾーの素生か電子的に石忍できるよう にするシステムである。このシステムでは、オンライン・ ショッピングなどにおいて、盜聴によってデータカヾ届れな いようにしたり、あるいは、正当な ( 詐称されていない ) WWW サーバーであるかを石忍する方法か提供される。 このため、電子図書館においても利用イ直か高く、十分に 理解しておくべき手法である。 現在では、この種のセキュアな WWW サービスは特 別なものではなく、 WWW サービスを構築するエンジニ アにとって、基礎知識というべきものになっている。 要なソフトウェア 今回は、 Apache と mod-ssl/OpenSSL を用いた実装 について説明する。この 2 つはオープンソース・ソフトウ ェアとして開発さ多くのシステムで利用されている。 HTTP サーパー Apache 周知のように、 Apache はオープンソースとして開発 された HTTP サーバーである。おそらく、則寺点では 世界でもっとも多く使われている HTTP サーバーであ り、数多くのプラットホームに対応している。以下では、 Apache 2.0.43 の利用を前提として解説する。インスト ール方法の言田には触れないが、多くのシステムではパッ ケージなどから簡単にインストールできるはすである。 ソースコードからインストールする場合は、以下の手順 で作業を進めればよい。 1. まず、 http://httpd.apache.org/ から職万版のソースコードをダウンロドし、適当なデ ィレクトリに展開する。 2. 展開したディレクトリの直下にある configure スクリ プトを実行し、必要な MakefiIe を生成する。 標準では /usr/Iocal/apache2 にインストールされる が、インストール先を変更したい場合は、 % . /configure ——prefix=/option/apache のように prefix オプションを使って指定すればよい。 3. make を実行する。 4. make install を実行する。 UNIX MAGAZINE 2003.2 Apache 自体のインストールは、これで終りである。標 準の設定では、実行形式ファイルは /usr/local/apache の下の適切なディレクトリにオ内される。また、サーバー が参照するドキュメントのルートになるディレクトリは、 ファイルシステム内の適当な場所 (/var/www など ) に 設定される。 SSL モジュール SSL/TLS を利用するには、 Apache のモジュールの 1 つである mod-ssl が必要になる。 Apache のノヾージョン 2.0. x のリリース・ノヾッケージに は、はしめからこの mod-ssl が含まれている。したがっ て、 2.0. x 以 . ヒのバージョンを導入したのであれば、あら ためて mod-ssl をインストールする必要はない。 一方、 Apache のバージョン 1.3. x 系列を利用してい る場合は、 mod-ssl を別途インストールしなければならな い。その場合には、 ・ http://www.modssl.org/ から最新版の mod-ssl を入手してインストールする。 のパッケージは、 Apache 1.3. x のソース・ディレクトリ に対するパッチ集として作られている。つまり、 Apache 1.3. x のソースコード 0 ンヾッチを当て、再コンパイルをし て Apache を作りなおす必喫がある。そのための乍業は、 以下のような手順でおこなう。 1. パッケージを入手し、適当なディレクトリで展開する。 2. Apache 1.3. x のソースコードを展開したディレクトリ を叩佖 c ん es 几とすると、 % cd m 。 d ー ssl を展開したディレクトリ % . /configure -—with-apache=apachesrc のようにしてパッチを適用する。 3. OpenSSL をまだインストールしていない場合は、次 項で説明する手順に沿って OpenSSL をインストール する。 4. 叩“ん e “ c ディレクトリに移動してコンパイルする。 43 % make certificate % make —enable—module=ssl . /configure % setenv SSL—BASE=/path/to/openss1
SoIaris 特集 ・ユ - ティンり 図 12 file コマンドの実彳」 # file core core : ELF 32 ービット MSB コアファイル SPARC パージョン 1 [ ファイル名 a. out] 図 13 core が作られた原因を調べる (dbx) % dbx a. out core a. out のシンポル情報を読み込んでいます。 コアファイルのヘッダを正しく読み込みました rtld /usr/lib/ld. so . 1 のシンポル情報を読み込んでいます。 1ibXt . so . 4 のシンポル情報を読み込んでいます。 プログラムはシグナル BUS ( 無効なアドレス整列 ) により停止しました (dbx) 図 14 (dbx) [ 2 ] [ 3 ] [ 4 ] [ 5 ] 升 le コアダンプが発生した場所を調べる where uti1—destroy(Ox114f48, 0X1 , 0X1 , 0X0 , 0X0 , 0X0 ) 、アドレス 0X734a4 exec—destroy—uti1-pid(Ox114f48 , 0X3051 , Oxefffef8c , 0X0 , 0X0 , 0X0 ) 、 アドレス 0X740d0 catch—sigch1d(Ox12, 0X0 , Oxeffff050, 0X0 , 0X0 , 0X0 ) 、アドレス 0X68b1C シグナルハンドラからシグナル 18 (SIGCLD) で呼び出されました -libc—read() 、アドレス Oxef4b87e8 get1com(Ox1bOc48, 0X1b0C48 , Ox1d, 0X0 , 0X0 , 0X0 ) 、アドレス 0X78ee8 ファイルの種別を調べるためのコマンドで、 core ファ イルに対して実行すると、そオ功ゞどのプログラムによって 作られたかを表示する ( 図 12 ) 。 dbx dbx はテンヾッグ用のツールであるが、プロセスの core ファイルが作られた原因を調べるときにも使える。ただ し、 Solaris 2. x で dbx を利用するには、 SPARC コン パイラ製品か必要である。 core カ非られた原因を謌・ヾるには図 13 のように、コア ダンフ。か発生した場所を調べるには図 14 のようにする。 dis コマンド 38 ーネルやプロセスの内部状態を調べる場合に有効である。 これらのコマンドは、システムに異常が発生した際のカ adb 、 kadb 、 crash 、 mdb コマンド ることかできる ( 図 15 ) 。 スコードがなくても内部でイ可がおこなわれているかを調べ センプルする。このコマンドを使うと、プログラムのソー /usr/ccs/bin/dis は、夫行形式のファイルをディスア 典型的には、システムが panic あるいはハングアップし たような場合である。具イ勺な使い方は次回に説明する。 Solaris 9 では crash コマンドはなくなったが、同等の 機能をもつ mdb か利用できる。 テパックのためのメッセージ コマンドのなかには、テンヾッグ出力をおこなうためのオ フションが用意されているものもある。以下では、各コマ ンドごとに使えるデバッグ・オプションについて説明する 俵 2 も参照 ) 。 automountd —vT のログ情報 オートマウントの設定がうまくいかない場合は、 auto- mountd をテンヾッグモードて起重屓 - ると、どの部分の処理 がおかしいかが分かる。テンヾッグモードで起動するには、 次のようにする ( 下線を引いた 1 行目は、すでにデーモン aut omount : nounmount S aut omount : Ⅱ 0 mount S # /usr/sbin/automount —v # /usr/lib/autofs/automountd —vT # /etc/init. d/autofs stop カ疑旦動されている場合に実行 ) 。 UNIX MAGAZINE 2003.2
・ユ - ティンう SoIaris 特集 図 1 installboot 吏用例 ・ SPARC 版 Solaris 2.5 以降の場合 # cd /usr/platform/ プラットホーム名 /lib/fs/ufs # /usr/sbin/installboot bootblk /dev/rdsk/c0t3dOsO ・ SPARC 版 Solaris 2.4 以前の場合 # cd /usr/lib/fs/ufs # /usr/sbin/installboot bootblk /dev/rdsk/c0t3dOsO ・ lntel 版 Solaris 2.5 以降の場合 # cd /usr/platform/ プラットホーム名 /lib/fs/ufs # /usr/sbin/installboot pboot bootblk /dev/rdsk/cOt3dOsO なお、スクリプトで題が発生している箇所を特定する 場合、スクリプトの頁を次のように変更するとより詳 しい状況が分かる。 # ! /sbin/sh ↓この部分を以下のように変更 # ! /sbin/sh set —X 、ノションや所有者か変更さ システムファイノレのノヾーご、、 れると、正常に動かなくなる機能やコマンドがある。 の場合は、 pkgchk コマンドを用いて、パッケージ情報 ミッションや所有者を復元することかできる。 からノヾ シングルユーサー・モードでも起動しない シングルューサー・モードでも起動できない場合は、ル ート・ファイルシステムが壊れている可能性がある。典型 的なのは、システムを正しく停止しなかったためにファイ ルシステムに不整合カ吽じたか、あるいは、なんらかの障 害や財巣作によってプートプロックが壊れたといったパ ターンである。 いずれにせよ、シングルューザー・モードでも起動でき なければ、 OS の CD-ROM から起動して以下の手順で ルート・ファイルシステムをイ夏する。 1. OS の CD-ROM から起動する ok boot cdrom 2 ー A. SoIaris 2.5 以、降の場合 : コマンドッールを起動 Solaris 2.5 以降では、 CD-ROM から起動すると自 動的にウインドウ環境になる。そこで、ワークスペー ス・メニューから、、ユーティリティ " を選ぶと、コマン ドッールを起重丿けるメニューか表示される。 2 ー B. SoIaris 2.4 以前の場合 : 自重加勺に起動される sys- idtool に清報を与える terminal type ロ、ここは何を指定してもよい hOSt name ←このナ昜 - へ connected tO net? (y/n) n subnets? (y/n) Ⅱ NIS, NIS + , none? none enter time zone これらの情報を与えると、 suninstall プログラムか起 動される。この suninstall のメインメニューから、、 [ d ] Ab 。 rt " を選ぶと、 # プロンプトか表示される。 3 ー A. プートプロックカれている場合 プートプロックが壊れているだけならば、 installboot コマンドの実行により、データを損なうことなく復旧で きる ( 図 1 ) 。 installboot は、プートプロック・ファ イルをプートテパイスの所定の位置にコピーするコマン ドである ( プートデバイスを指定するときはローデバイ スを使用する点に注意 ) 。 3 ー B. ファイルシステムカれている場合 ファイルシステムの不整合の場合は、 OS の CD-ROM から起動し、 fsck を使って復旧を試みる。 # fsck /dev/rdsk/cOtOdOsO 3 -C. ファイルの設定ーヒの間題の場合 己ミスなど、ファイルの設定に原因があると思われる ときは、以下の手順で復旧を試みる。 ( a ) 作業用ディレクトリの作成 # mkdir /tmp/a ( b ) 手夏したいファイルシステムのマウント # mount —F ufs /dev/dsk/cOt3dOsO /tmp/a (c) ファイル刎正 ( 例 ) # cd /tmp/a/etc # vi passwd 変更部分を修正 :wq! ←修正結果を保存して終了 一三ロ 23 UNIX MAGAZINE 2003.2
SoIaris 特集 ーティンう (d) マウントの解除 # cd / # umount /tmp/a (e) リプート # reboot ライプラリのクラッシュ ドカ硬えなくなる。ただし、その場合でも以下のコマンド 共有ライプラリがクラッシュすると、はとんどのコマン たびに、、 Memory fault" となる。 このほかにも、 B シェル ( sh ) ではコマンドを実行する warmng for OIder minor version used expected %d ld. so : warning: %s has older version than - います。以下同椥 リにリンクされた場合 ( 誌面の都合上、で折り返して ている実行可能ファイルが、旧いバージョンのライプラ ・新しいバージョンの共有ライプラリとすでにリンクされ 1d. SO : %s is not for this machine type 1d. so: can't read struct exec for %s ld. SO.• open error errno for 0/oS するように構成されている場合 インストールされている、ほかのアーキテクチャで実行 共有ライプラリか破壊されている、不正なアクセス権で ld. so : lib%s . %d. %d not found crtO: Ⅱ 0 /usr/lib/ld. so ・ ld. s 。などの共有ライプラリがみつからない場合 カ起こる。 えなくなってしまうのである。この場合、次のような現象 ラリがクラッシュすると、ほとんどすべてのコマンドか使 ただし、これによって新たな問題も生した。共有ライプ 図っている。 スペースの節約、ライプラリのバージョン管理の簡易化を リの機能を導入し、メインメモリの効率的使用とディスク Solaris 2. x でも、 SunOS 4. x と同様に共有ライプラ 24 は利用できる。 /sbin ディレクトリ UNIX MAGAZINE 2003.2 パッチをダウンロードした場合、パッチの適用順序や、本 ッチをダウンロードできるようになっている。 1 つ 1 つの SunSolve OnIine て情報を検索し、そのまま必要なパ 手しやすくなった。 およびこれに里する情報は数年前にくらべてはるかに入 インターネットの普及やメーカーの成熟により、 パッチの入手 い、問題のシステムに適用する。 ない。該当するパッチを迅速にみつけて釧何薩忍をおこな バグを修正するためのパッチを適用する以外に回復ガ去は トラブルの原因が OS のバグなどである場合は、その パッチによるトラカレの回復 ファイルシステムにコピーする。 OS の CD-ROM から起動し、必要なファイルを /usr できない場合 ・バックアッフ。がなく、ネットワーク経由でのコピーも コピーする。 ら、 /usr/sbin/static/rcp を使って必要なファイルを 同しネットワークに接続されているほかのシステムか ・ネットワークに接続されている場合 ドする。 い、バックアップ・メディアから必喫なファイルをロー /usr/sbin/ufsrestore か /usr/sbin/static/tar を使 ・ノヾックアップをとってある場合 のときの状況によって以下のように異なる。 共有ライプラリがクラッシュした場合の復旧ガ去は、そ イルしたプログラムは利用できる。 付けて実行し、共有ライプラリを使用しないようにコンパ ューサーが C コンノヾイラ (cc) に—Bstatic オプションを できるように、スタティック・リンクされている。なお、 これらは、共有ライプラリがクラッシュしたときに復旧 cp 、 ln 、 mv 、 rcp 、 tar ・ /usr/sbin/static ディレクトリ ufsrestore 、 fdisk /usr/sbin ディレクトリ 111 、 swapadd 、 sync 、 uadmin 、 umount 、 uname autopush 、 init 、 jsh 、 mount 、 sh 、 soconfig 、 sulog-
連載 / IPv6 の実装ー 最後に、巨大ペイロード・オプションて指定されたペ イロード長を plenp に成疋し、次のオプションの処理に 進みます。すでに解説したとおり、 plenp は巨大ペイロー ド・オプションの重複検出にも利用されます。 1435 default : 図 3 オプションの頁 0 7 1436 1438 1439 if (hbhlen く IP60PT-MINLEN) { goto bad; 1 , 435 行目から始まる default ケースは、未知のオプ ションを扱います。 1 , 436 行目ではオプションとしての最 低限の条件を石忍します。 IP60PT-MINLEN は ip6- opt 構造体の大きさ、すなわち 2 オクテットです。オプ ションの不鶤頁とオプションの長さをオ内するだけの最低限 の大きさか残っていない場合、 1 , 438 行目でバケットを破 棄します。 1440 1441 1442 1443 1444 1445 optlen = ip6—unknown—opt (opt , opthead) ; erroff + opt break ・ optlen + = 2 ; return ( ー 1 ) ; if (optlen IPv6 では未知のオプションに対し、次の 4 つの処理方 法を定義しています。 無視する。 きます。ー 1 カ隧されたときはバケットを破棄し、そオ人 するかどうかは ip6-unknown-opt() の返り値で判断で のなかから 1 つお尺して処理します。バケットを破棄 ip6-unknown-opt() は未知のオプションを調べ上記 RAM-PROB メッセージを返送する。 ャスト・アドレスではない場合にのみ、 ICMP6-PA- ・オプションを含むバケットの終点アドレスがマルチキ ・ ICMP6-PARAM-PROB メッセージを j 逶する。 ・オプションを含むバケットを破棄する。 タ ) 場合は次のオプションの処理に進みます。 1446 1447 1449 1450 1451 1452 1453 return ( 0 ) ; return ( ー 1 ) ; m—freem(m) ; bad : UNIX MAGAZINE 2003.2 1454 } すべてのオプションの処理か完了したら 1 , 449 行目で 呼出し元へ戻ります。処理の途中でエラーが発生した場合 は 1 , 452 行目でバケットを解放し、一 1 のエラーを返し ます。 未知のオプションの里 処理対象のオプションか未知のものであれは、オプショ ンの不頁に応して適切に処理する必要があります。未知の オプションの処理ガ去を白寉に判断できるよう、 IPv6 で はオプションの不頁を示す値の一に一定の意味をもたせ ています。オプションの不鶤頁は図 3 に示すように 8 ピッ トで表現されます。 このなかで、上位 3 ピット (aac) カ畤別な未をもち ます。ます、上位 2 ピット (aa) はオプションが未知の 場合の処理ガ去を示します。 65 あることを愈未し、 1 の場合は途中のルータがオプション から終点ノードにいたる過程でオプションの内容は不変で か変更されるかどうかを表します。 0 の場合は始点ノード 続く 1 ピット (c) は、転送の過程でオプションの内容 RAMPROB-OPTIONO のコード番号は不正なオプションを示す ICMP6-PA- RAM-PROB メッセージを返送する。このメッセージ キャスト・アドレスではない場合にのみ ICMP6-PA- このオプションを含むバケットの終点アドレスがマルチ ・ 11 の場・合 RAMPROB-OPTION0 のコード番号は不正なオプションを示す ICMP6NA- RAM-PROB メッセージを返送する。このメッセージ このオプションを含むバケットを破棄し、 ICMP6-PA- ・ 10 の場合 このオプションを含むバケットを破棄する。 ・ 01 の場合 このオプションを無視し、バケットの処理を継続する。 ・ 00 の場合
図 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 れに上ける手間でおこなえますが、最 このように、二分探索を用いオ酩は、もっとも効率 のではないでしようか。
特集・プログラミング入門 図 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
特集・プログラミング入門 } 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