アルゴリズム ・前のノード ( 樹形図で 1 つ上位にある では , プログラムコードを示しながら見 す。木へのデータの追加と削除は , ていきましよう。「 2 分木 (binary tree) 」と ノード ) は「親ノード」 (a) あるノードに新しい子ノードを追加 呼ばれている , いちばん簡単な木構造を紹 ・次のノード ( 1 つ下位にあるノード ) は する (Fig. 6-(a)) 介します ( これで感覚をつかめば , ほかの 「子ノード」 ( b ) あるノードとその親 / 子ノードの間に , 木構造にも問題なく応用ができます ) 。 ・同じ親を持つノードは「兄弟ノード」 もう 1 つノードを挿入する ( Fig. 6- ( b ) ) ・子を持たないノードは「葉 (leaf) 」 ( c ) " 葉 " を切り取る (Fig. 6-(c)) 2 分木 (binary tree) ・木全体の根本が「根 (root) 」 ( d ) 途中のノードを切り取る ( Fig. 6- ( d ) ) ( e ) 部分的な木構造を丸ごと追加したり ・あるノードから親 , その親 , さらにそ 2 分木というのは , 「あるノードが最大 2 , すべてひっくるめて「先祖」 削除したりする (Fig. 6- (e) ) の親・・ 個しか子ノードを持たない」という木構造 といった形になります ( (d) のケースでは , ・あるノードの子 , その子 , さらにその 子・・・・・・ , すべて合わせて「子孫」 です。要するに , Fig. 7 のように最大でも 2 切り取った後に残された " 子孫 " をうまく移 動してやる必要があります ) 。なお , プロ 個ずつに枝分かれしていくだけの木構造を などと呼ばれています。 グラムの目的によっては , 上記 (a) ~ (e) す 2 分木 ( あるいは 2 分探索木 ( b ⅲ a Ⅳ search 仕 ee ) ) と呼ぶのです。この 2 分木を使うと , べてのパターンを実装する必要はありませ 頻繁に追加・削除が行われるデータの整理 木へのデータの追加や削除も , リストと ん。状況に応じて必要な追加・削除のパタ と検索を , 配列を使うよりもずっと高速に ーンを実装すれば OK です。 同じようにポインタをつなぎ替えて行いま 行えます。木構造の具体例を見ながら , そ の方法を紹介しましよう。 並び方の特徴 Fig. 7 をもう一度注意深く見てください。 Fig. 3 リスト構造のノードと木構造のノード ( b ) 木のノード ( a ) リストのノード 要素の追加と削除 Fig. 2 リスト構造 (a) リスト構造 ( 単方向リスト ) 次のノードへの 次のノードへの 次のノードへの ポインタ ポインタ ポインタ (b) ノードの挿入 次のノードへのボ インタは 1 つだけ 複数のポインタ を持てる Fig. 4 木構造 (c) ノードの削除 これを削除 前後のノードをつないで , 切り離したノードを削除 1 5 / プログラミングの宝箱

( 2 ) もしもその場所にすでに既存のノー 帰を使って実際にプログラムしたコードを 手順とほとんど同じです。 Fig. 7 の 2 分木か ドが存在したら , そのノードに対し List2 に示します。 ら「 20 」という数字を探してみましよう。 て ( 1 ) を行う まず , 根の「 47 」と「 20 」を比較して 47 > 20 これを読んで , 何か気づきませんか ? なので , 左側の子ノードを探します。する そう , この動作は前回説明した「再帰」を使 次に , 2 分木で特定の値を検索する方法 と , 「 23 」という数値を持ったノードが出現 う処理に向いているのです ( コラム 1 ) 。再 を考えます。探索の手順は先ほどの挿入の するので , 23 > 20 より再び左側の子ノード 2 分木の探索 2 分木のデータ追加・探索・削除 tree—node* node,int val ) / * 発見した tree-node のポインタを返す。無い場合は阯 * / / * 自分より小さい値ならば、左側 * / if(node->valuoval ) if(node →厄ft==部乢) / * もし左側に無ければ、 val はない * / return Nt 」 LL ー て e 加て n find—value(node->left,val / * 自分より大きい値ならば、右側 * / if(node->value く val) if ( ncde->right==NULL ) / * もし右側に無ければ、 val はない * / return NULL ・ て e 加て n find—value(node->right,val / * 見つかれば、見つかった値を返す * / return node ・ 分木の探索 #include «stdio. h> #include く stdlib. h> typedef struct int value; struct —tag—tree—node* left; struct —tag—tree—node* right; } tree—node ー tree—node *tree—root=NULL; tree—node* create—new—node(int num) tree—node *tree—new ー / * 新しいれ ode を作成して、初期化する * / tree—new= ( tree—node* )ma Ⅱ oc ( sizeof ( tree—node ) if ( tree-new==NULL ) exit(EXIT—FAILURE); tree—new—>left=NULL ・ tree—new—>right=NULL ・ tree—new—>value=num; return tree—new; / * この node が持つ値 * / / * 自分より小さい値の node : 紙面では左の node * / / * 自分より大きい値の node : 紙面では右の node * / void insert—tree ( int num , tree—node *node ) / * ーっも挿入されていない場合 * / if(node==NULL) tree—root=create—new—node ( num return ー Fig. 9 2 分木から子孫を持つノードを削除する ( 1 ) 削除したいノードの " 左側 " の子孫から " 最大の値”を持つノードを検索 47 除ノ / * num が現在の node の値よりも小さい場合 * / if(node → value > num) if(node->left ! = NULL) insert—tree ( num , node-> 厄 f セ e ー se / * 左に追加する * / node-> left=create—new—node ( num e ー se / * num が現在の node の値以上の場合 * / if(node->right ! = NULL) insert—tree ( num , node->right ); e ー se / * 左に追加する * / node->right=create—new—node ( num 1 7 35 72 53 20 1 5 31 左側の子孫で最大 ( 2 ) 削除したいノードと ( 1 ) で見つけたノードの値を入れ替え , 入れ替えた 先のノードを削除 47 88 return ー tree—node* find—value(tree—node* node,int val) / * 発見した tree-node のポインタを返す。無い場合は * / / * 自分より小さい値ならば、左側 * / if(node->value>val ) if(node → Ieft==NULL) / * もし左側に無ければ、 val はない * / return NULL ー return find—value(node->left,val / * 自分より大きい値ならば、右側 * / if(node->value く val) if(node->right==NULL) / * もし右側に無ければ、 val はない * / return NULL ・ return find—value(node->right,val / * 見つかれば、見つかった値を返す * / 20 35 72 53 1 7 31 値の入れ替え後 , 削除 23 88 0 160 C MAGAZINE 2001 10

させます。そして , ハフマン木からその x の葉と等しい登場頻度を持つノードを探し , Fig. 6 V アルゴリズムでのハフマン木更新手順 入れ替え処理を行います ( ノードに子ノー ドが付いている場合は , 子ノードも移動し ( 1 ) 入力文字に対応する葉に注目する。もし , 初めて現れたデータ値であれば , 「未出現値」の葉 に注目する ( 2 ) 注目ノードの状態によって以下の ( A ) ~ ( C ) のように処理を分ける ( A ) 現在注目しているノードが「未出現値」である場合 現イ 0(0) 注目ノード 未出現値 0 ( 0 ) 2 ( 0 ) 1 ( 0 ) 注目ノード ※未出現値ノードの部分を , 右側に「新たに出現したデータ値」と左側に「未出現値」を子 に持つ節ノードに置き換える。このとき , 新たに加えた 2 つのノードの登場頻度はとも に , 現在のノードの重みを 1 増やした後 , 親のノードを注目ノードとする を探し ( 自分自身でもよい ) , そのノード ( とその子孫 ) を現在のノードと入れ替える。次 現在の注目ノードと同じ登場頻度を持つノードの中から , いちばん番号の大きいノード ( C ) 現在注目しているノードが上記 ( A ) ( B ) 以外の場合 ノードの重みを 1 増やした後 , その親ノードを注目ノードとする ( B ) 現在注目しているノードが「未出現値」の兄弟 ( 同じ節ノードを親に持つ ) である場合 でノード番号を付け直す。そして , 次の注目ノードを右側の子ノードとする に 0 とする。番号は , 左側のノード→右側のノード→今までの木のノード番号という順 ( 3 ) 次の注目ノードについて , ( 2 ) の処理を行う。これを注目ノードが根にいたるまで繰り返す Fig. 7 画像テータのヘッダフォーマット ファイル識別子 ( 定数 ) 画像の横幅 (long 型 ) G B 画像の縦幅 (long 型 ) 画素値 255 の日 GB 値 日 G B ます ) 。等しい登場頻度を持つノードがな ければ , データ値 X の入力に伴ってハフマ ン木の構造を変える必要がないことを意味 するので , 入れ替え処理は行いません。 このようにすれば , x の葉の重みを + 1 し てもすべての節において 2 つの子の番号を 連続させることができ , 兄弟条件を維持で きます。入れ替えを行った後は , その親ノ ードに注目して , 登場頻度を 1 っ増加させ た後 , 同じ入れ替え処理を行います。そし て , 最終的に根にたどり着くまで登場頻度 の 1 増加と入れ替え処理を繰り返すことで ハフマン木の更新が行えます。 前述の「未出現値」と「 EOF 」を用いたハフ マン木の場合も同様に処理できます。この 場合 , 今までに出てきていないデータ値を 処理した後は , 未出現値の葉を Fig. 4 のよ うに更新した後 , 前述の更新処理を行いま す。 V アルゴリズム FGK アルゴリズムをさらに改良したアル ゴリズムが 1987 年 , J. S. Ⅵ tter によって提 案されました。 Vitter はノード番号の付け 方を工夫することで , より効率のよいハフ マン木の再構築が行えることを発見しまし た。これは V アルゴリズムと呼ばれるもの です。 V アルゴリズムでは , 「ノード間の距離」 という概念を導入しています。「ノード間 の距離」とは , 「あるノードからあるノード 1 画素のビット数 (long 型 ) ( この後 , 画像データ本体 ) 168 日 G B 画素値 0 の RGB 値 C MAGAZINE 2001 10 日 画素値 1 の日 GB 値

ものを右側というふうになっています。 では , 実際にこの木を使って判定を行う 手順を見てみます。やはり文章で書くとわ かりづらいのですが , しつかりと追ってみ てください。まず , 図の☆の地点に注目し ます。木の根ノードの分断面 a と比べると 裏側に☆が存在しているので , 根ノードの 裏側の子 h に進みます。次に h に対して比 較すると今度は表側なので , d2 へと進みま す。 d2 の表で el のノード el に進んだところ で , 子ノードが存在しなくて終了となりま す。 は , 木をさかのばればすべて手に入れるこ たつもりです。 この手順は , 今回の最初に説明した特性 では , さらに進まれる方のために , いく とができますし , 点線 ( P 。血 1) を用いて隣 の管理に向いているのです。 a の点線と , h, っか参考文献をあげておきます。 接する部屋をリストアップすることもでき d2, el で囲まれた平行四辺形の中に存在す [ 1 ] 佐藤義雄監訳 , 『コンピュータグラフィ ます。この , 隣接を検出する問題は , 四分 る点であれば , ☆に限らず , すべて el のノ ックス理論と実装』 (lSBN4-274-0640 木などでは苦手とされているので BSP の利 ードで終点を迎えます。間取りでいえば同 5-0 ) 点といってよいでしよう。 じ部屋ということになりますが , この部屋 以前にもあげた "Computer Gr 叩 hics: Pri ほかの特性をあげてみると , 物陰に隠れ という単位にさまざまな特性を埋め込むこ nciples and practice" の邦訳です。空間管理 ている間は見つからない , 歩くと特別な音 とができるのです。☆について同じような 関係でも , この文献をあげていることが多 がする , 光源からの影が落ちるかどうか , 探索を行ってみてください。 g の裏側の子 くありました。良書ですが , 非常に分厚い など , 工夫しだいであらゆる特性を考える ノード ( 存在しません ) で探索が終わると思 本なので , 足の上に落とすとたいへん痛い ことができます。この BSP は Quake という います。このことは , g の裏側カ壁の中と 思いをします。 ダンジョン型 3D ゲームで用いられたこと いう特性を持っているのだと考えることが [ 2 ] id-software, "Quake T00 source code で有名になった方法なので , ダンジョンで できます。つまり , BSP ツリーでは , 登録 www.id-software.com にて入手できる , Q ないと効果が薄いという評価がなされがち と参照がこの部屋という単位で行われるこ uake というゲームのソースコードです。 B です。しかし最近ではさまざまな拡張によ とになるのです。これは画期的なことだと SP はこれから広まったといっても過言では って広範に使われてきているので , 新たな いえるでしよう。 ないと思われます。描画の高速化をはじめ , 手法を生み出す可能性を持った , よい方法 たとえば描画の刈り込みに関して , 少し シャドウマップやラジオシティ , さらには 特殊なアプローチが用意されています。そ だと思われます。 音が聞こえるかどうかまで , BSP で取り扱 れぞれの部屋に , その部屋にいるときにほ かのどの部屋が見えるのかという情報 ( PV っています [ 3 ] 宇治社中 , “ 3D 補講” S ) を特性として保持する方法です。扉を開 手前味噌になりますが , 私のホームペー け放ったとしても , あなたが今いる部屋か ジにて BSP の説明を取り扱っています。今 今回は空間管理の手法をいくつか取り上 ら見える空間には限りがあります。見える 回書ききれなかった範囲や , サンプルソー げてみました。少しゲームに偏った評価を 空間を絞り込めれば , ほかのオプジェクト スコードも存在します。ぜひ一度ご覧にな しましたが , CG ツールや CAD などでも , や地形も同様に絞り込むことができるでし まず間違いなくこれらの方法が用いられて ってみてください。 U Ⅲは , よう。見えるはずのない部屋に登録されて います。それぞれに長所や短所がある方法 http://www.cc.rim.0「.jp/-devilman/ いるオプジェクトはいっさい描画する必要 です。 がないのです。 なので , いったいどのようにしているのだ 次回は LOD (Level Of Detail) にまつわる また , 当たり判定 , 位置関係の特定にも ろうと逆に推測するのもおもしろいと思わ 問題を取り上げることにします。 効果があります。今いる部屋を構成する壁 れます。その手がかりになるようにと考え Fig. 9 BSP ツリーの最終状態 dl ☆ d2 d2 dl e 1 ☆ e2 / e 1 e2 まとめと参考文献 Enter The 3D Programming 175

Fig. 6 木構造へのデータの追加と削除 (a) 新しい子ノードの追加 Fig. 5 木の各部分の名称 根 先祖 新しい (b) 親子の間にノードを挿入 このノードを 兄弟 葉 基準とした場合 葉 葉 子 葉 葉 葉 ※子孫を持たないノードを「葉」 と呼ぶ F 、ロ追加する 葉 葉 葉 (c) 葉を切り取る 子孫 葉 削除 削除する Fig. 7 2 分木の例 47 ( d ) 途中のノードを切り取る (a) 23 削除する (b) 72 53 35 17 88 31 20 1 5 Fig. 8 2 分木へのデータの挿入 ①根の値と挿入するデータ ( 37 ) を比較 挿入する > 37 ② 47 > 37 なので , 左側 47 データ の子ノードに進む ③データをノードの値と 23 < 比較して . 23 < 37 な ので右側に進む (e) 部分的な木を丸こと追加 & 削除 木 A 削除 追加 37 ④データをノードの値と 37 比較して , 3 5 く 37 な ので右側に進む 、⑤進んだ先にノードがない ので , 新しくノードを作 成してデータを格納する 35 < 1 7 木 B 削除する部分木 37 ー 31 20 158 C MAGAZINE 2 1 10

でたらめにデータが挿入されているわけで はなく , ある規則に従ってデータが並べら れていることに気づきましたか ? そう , あるノードの子ノードを見ると , 左側の子 ノードは親よりも小さな値になっていて , 右側の子ノードは親よりも大きな値になっ ているのです [ 注 2 ] 。 たとえば , (a) のノード ( 23 という数 ) に 注目すると , 左の子ノードは 17 ( 23 より小 さい ) , 右の子ノードは 35 ( 23 より大きい ) , となっています。 (b) のノード ( 72 という数 ) は子ノードを 1 つだけ持っていますが , そ の子ノードは 88 ( 72 より大きい ) なので右側 にきて , 左側の子ノードのスペースは空に なっています。 このデータ構造を C 言語の構造体で表す と , List 1 のようになります。最初にこの 構造体を 1 つ用意して , それを木の " 根 " に します。そして , " 根 " にデータをどんどん 追加したり , 必要に応じて検索したりデー タを削除したりすることで , 2 分木を使っ た効率のよいデータ管理ができるわけで す。 [ 注 2 ] このように兄弟ノード間の並び方に ( 何 らかの ) 順序がつけられている木構造の ことを「順序木」と呼んでいます。 typedef struct —tag—tree—node ます。そこで , 次にこの「 23 」と「 37 」を比較 ノードにはすでに「 23 」という値が入ってい とがわかります。ところが , 根の左側の子 で , 37 は根の左側に入るべき数値であるこ 入っている ) と「 37 」を比べると 47 > 37 なの まず最初に木全体の根 ( Fig. 8 では「 47 」が を挿入することになったとしましよう。 ます (Fig. 8 ) 。たとえば , 「 37 」という数字 でに「 35 」というノードがあるので , 同じよ 側の子ノードの位置にきます。そこにもす して , 23 く 37 なので , 37 はこのノードの右 2 分木のノード アルゴリズム うが小さければ右側の子ノードに付 ば左側の子ノードに , 既存の値のほ 較して , 既存の値のほうが大きけれ ( 1 ) 挿入する値と既存のノードの値を比 す。 挿入します。まとめると次のようになりま かったので , 37 のノードを作成してここに きスペースとなっている正しい位置が見つ になることがわかります。ここでついに空 うに 35 く 37 と比較し , 37 は右側の子ノード ける int value; struct —tag—tree—node* right ー struct —tag—tree—node* left ー / * このノードが保持する値 * / / * 自分より小さい値の node : 紙面では左のノード * / / * 自分より大きい値の node : 紙面では右のノード * / 木構造と再帰 2 分木にデータを追加 0 return ー tree—て oot=create—new—node ( num if ( node==NULL ) / * ーっも挿入されていない場合 * / void insert—tree ( int num ,tree_node *node ) / * n ・・・挿入する値 node ・・・値を挿入する木の根を指すポインタ * / return tree—new ー tree—new—>va ー ue=num ー tree—new->right=NULL ・ tree—new-> Ieft=NULL• exit(EXIT—FAILURE); if ( tree—new==NULL ) tree—new=(tree—node*)malloc(sizeof(tree-node) / * 新しい node を作成して、初期化する * / tree—node *tree—new ー tree—node* create—new—node(int num) 2 分木へのデータ追加 とって , データを挿入する方法を見ていき 考えてみましよう。 Fig. 7 の木構造を例に まず , 2 分木へのデータの追加について 木構造は , 再帰で処理をするのにとても 向いているデータ構造です。なぜ再帰に向 いているのでしようか ? 前回も述べましたが、再帰は「全体の一 部分を取り出しても同じような構造をして いるデータ」 , つまり“入れ子のようになっ ているデータ”を扱うのに向いています。 木構造は , 全体の一部を取り出してもやは り同じように木構造になっているため , 再 List 2 0 帰で処理するのに適しているのです。 さらに , 木構造は階層構造を持っている ために単純な fo 「文や wh ⅱ e 文では扱いにく いという特徴があります。配列やリスト構 造なども入れ子構造で表現可能という点で は木構造と同じですが , これらのデータ構 造は階層的な構造を持たないためにあまり 積極的に再帰を利用する必要はなく , 普通 の fo 「文などで処理できます。 / * num が現在の node の値よりも小さい場合 * / if(node->value > num) if(node → left ! = NULL) insert—tree ( num , node-> left / * 左に追加する * / node->left=create—new—node(num); e ー se / * num が現在の node の値以上の場合 * / if(node->right ! = NULL) insert—tree ( num , node->right e ー se / * 左に追加する * / ( num return ー プログラミングの宝箱 159

フログラ アルゴリズム 入門 第 6 回 木構造 . 春日伸弥 ・紀平拓男 樹形図のようにデータ同士の関連が階層的に枝造を使うのがいちばんです。以前取り上げた 「リスト構造」にほんの少し手を加えるだけで , 慕物 、 = き分かれしているタイプのテータ群を扱うには , 蘿まその名もずばり「木構造 ( ツリー構造 ) 」という構すぐに「木構造」を実装することができます。 Borland C + + 5.5.1 Compiler 日本語版 協力 : ポーランド ( 株 ) ( 有 ) スウイフト い , 木構造は 2001 年 7 月号で紹介した「リ 樹形図のように枝分かれ スト構造」をほんの少し ( たった 1 か所 ! ) 変 えただけのものです。今回はリスト構造の 世の中には , 樹形図状に枝分かれしてい 復習を含めて , 木構造について紹介した後 , るものが山ほどあります。たとえば , 生き いちばん単純な「 2 分木」の例を紹介します。 物の分類や会社の組織からコンピュータの Ⅲ「リスト構造」のおさらい ファイルやディレクトリまで・・・・・・ ( Fig. 1 ) 。 どれも " 小さいカテゴリの要素が集まって 先ほどのリストのノードを Fig. 3 のよう ではまず , 復習も兼ねて「リスト構造」の 大きなカテゴリを作り , それが集まってさ に , " 次のノード " を複数持てるように ( 次 らに上位のカテゴリを作って・・ " という おさらいをしてみましよう。リスト構造は のノードへのポインタを複数保持できるよ 構造になっています。こうした樹形図状の Fig. 2- ( a ) のようなものでした。配列の要素 うに ) 変えてみます。こうしてできた新し データを効率的に扱うために , 「木構造 ( ツ に相当する「ノード」がたくさんあり , 1 つ いノードをたくさんつなげていくと・・ リー構造 ) 」というデータ構造が使われます のノードは 1 つのデータ + 次のノードへのポ Fig. 4 のようにもう木構造のできあがりで ( まさに名前そのままですね ) 。木構造を使 インタ [ 注 1 ] を持っています。先頭のノードか す ! たったこれだけです。木構造は , リ うと , 樹形図の中を検索したり , データ同 らポインタを順番にたどっていくことで , スト構造のノードが複数の " 次のノード " を 士の位置関係を把握したり , といった操作 すべてのデータを操作することができま 持てるようにしたというだけなのです。 が非常に楽になります。 す。要素の挿入と削除は Fig. 2-(b) や Fig. 2- 木構造の各部分の名前は , Fig. 5 のよう 「木構造だなんて , いったい何者 ! ? 」と身 (c) のように , ポインタを操作してノード になっています。 1 つ 1 つの要素はリスト をリストの適切な位置に結合したり切り離 と同じように「ノード ( 節 ) 」と呼ぶ一方 , 構える必要はありません。なんのことはな Fig. 1 枝分かれしているデータの例 ( a ) 生き物 生物 したりすることによって行います。 [ 注 1 ] 単方向リストの場合。双方向リストで は「前のノード」へのポインタも持って います。 木構造 ( b ) ファイルシステム C : 植物 動物 鳥 魚・・・ほ乳類昆虫 indOW C. exe b. doc a. txt ocumen S ste f. cpp Win. ini クジラ・ 人 e. dll d. dll 156 C MAGAZINE 2001 10

いう問題があります。これは , 1 つのオプ ジェクトがノードをまたがってしまうこと を意味し , それだけ登録する情報の重複が 増えることになるのです。 また別の問題もあります。たとえば , 最 高地上 5000 メートルの範囲で空中戦を行う ゲームを作ったとします。この空間の最初 の分割は , 地上 2500 メートルのところでな されることになるでしよう。ところが , 地 上にある障害物で , 地上 1000 メートルに達 しそうなものはそうありません。たかだか 20 や 30 メートルの障害物のために根ノー ドの下半分は常に検索対象の灰色ノードと なってしまうのです。 登録の重複が増えたり , 刈り込みの足か せになったりするのは , どうやら半分に切 です。図を比較して指差しながら手順を追 も子ノードを持っています。このような場 るという四分木 , 八分木のルールのせいだ 合は , 各ノードの子ノードに再帰的に比較 ってみてください。 と思われます。この点を拡張したのが , 次 こでできた結果の木はまさに AUB = S を掘り下げていきます。 A の NE の子ノード の Kd ツリーになります。 に相当する演算で , あげた例でいうなら , たち , B の NE の子ノードたちをそれぞれ比 静的に生成しておいた木と動的に生成され べると , すべて灰色が勝って塗りつぶされ た木との合成をとったことになります。描 ることがわかります。これは , 生成のとき 画の刈り込みに用いるのであれば , 静的で に説明した分割不可の黒ノードに相当する 複雑な地形は前処理で生成した木を保持し ので , 新たに作られる S の NE は子ノードを この方法は , 半分に切らなくてはいけな ておくことで効果が期待できます。 持たない灰色となることになります。ただ いというルールを破ることから始まります。 まをく同様に今度は白優勢のルールで し , 子供が管理していた情報 , 登録された 自由に切ることによって合成する利点はな 比較を繰り返すと , 2 つの木の積 APIB = S を バウンディングボックスやポリゴンはすべ 求めることができます (Fig. 6- (b) ) , こち くなりますが , そのぶんメリットも生まれ て親が吸い上げなければいけないことに注 ます。また , 四分木や八分木では軸ごとに らは 2 つの木の間で当たり判定を行う場合 意が必要です。 分割することが必須になっていましたが などに有効な方法といえます。機械同士の 続けて , A の sw と B の SW を見ます。どち 今回はどれか 1 つで分割することを繰り返 らも灰色ですが , A の SW は子ノードを持た かみ合わせなど , 複雑な形状同士の判定に すことにしましよう。データ構造としては , なる場合 , ポリゴン同士の判定の前に積を ない , いわゆる黒いノードなので , これも 二分木になります。 とっておくと , 判断の必要な領域を絞り込 容赦なく黒を S の SW として登録します。そ Fig. 7 の左側は , 空間上でオプジェクト むことができるのです。 の際 , B の SW ( の子ノード ) に属していた がどのように配置されているかを表してい こまで利点をあげてきたわけです 情報も同じく S の SW に登録されます。 ます。ここで注目していただきたいのは , が , やはり少し欠点も存在します。これは 最後に A の SE と B の SE ですが , これも灰 各四角形が正方形ではないことです。この セルの説明の際に注意した , 何を管理する 色と白の組み合わせです。勝った A の SE を ことがぐっと自由度を上げてくれます。い S の SE として子ノードごとぶら下げます。 かにも関係してきます。 ちばん外側が根ノードになるところは同じ 四分木や八分木の特徴として , 正方形や こうして , 白か灰色か , 場合によっては で , 以下 , 図右側の二分木を見ながら説明 立方体を繰り返し半分ずつに区切っていく 黒 ( 子がすべて灰色 ) かという概念を用い を進めていきます。最初は図の縦方向 , y て , 機械的に探索と比較を繰り返すと , Fi ことがあげられます。そのことが木同士の がある値 a より小さいか大きいかによって , 合成を簡単にしているのですが , 一方で管 g. 6- ( a ) の木ができあがります。文章で読 子ノードを 2 つ作成します。これで , 地形 理する対象を容赦なしに横切ってしまうと むと長くなるのですが , これは再帰の宿命 Fig. 6 2 つの木の和と積の結果 (b)AßB (a)AUB Kd ツリー Enter The 3D Programming 173

Fig. 3 3 段階目まで行った場合の四分木の状態 ロ空のノード ロ再分割が必要 ロ分割不可 ます。 Fig. 5 木同士の合成 NW SE NE 図の灰色で塗られた部分は , まるごとオ プジェクトの中であったりして , それ以上 分割する意味のないノードです。極端なこ とをいえば , 灰色の部分が ( ほとんど ) なく なって白か黒かが決まるまで分割を繰り返 すことによって , オプジェクトの形そのも のをツリーとすることもできます。 これが , 四分木による空間の管理方法で す。例では二次元での四分木でしたが 次元では 3 平面による分割で 8 つの子ノード ( 八分子 (octant)) を作る同様の手順で管理 を行うことができます。 構造を理解したところで , この四分木 , 八分木の利点や欠点を見ていくことにしま す。 1 番目の利点は , 描画についての刈り込 1 / 2 c MAGMINE 2001 10 SW A と兄弟である時点で , A, B ともに視野か もう一段階早い段階で刈り込まれています。 さらに , 図の B にある子ノードたちは , だけ , ということがわかります。 クトは白いノードに登録されているもの 逆にいうと , 描画する必要のあるオプジェ た範囲は , 視野に入ることはありません。 むことができるのです。図で灰色に塗られ じ方法で , 木の各ノードをまるごと刈り込 前回までに紹介したような当たり判定と同 二次元空間上では線分で表せます。すると , この視野角錐は三次元空間上では平面で , 視界 , 視野角錐 (view frustum) だとします。 P が視点やカメラの位置で , 太線がその ださい。 みが可能になることです。 Fig. 4 を見てく Fig. 4 描画についての刈り込み ら外れているので , B の子ノードは探索す る必要がないのです。対象となるオプジェ クトやポリゴンが細かく , 四分木や八分木 が深く作り込まれているほど , この刈り込 みは効果的になります。 もう 1 つ , 四分木や八分木ならではの利 点があります。それは木同士の合成が比較 的簡単に行えることです。 Fig. 5 のように , 四分木が A と B , 2 つあ る場合を考えてください。このような状況 は , 動かないオプジェクトであらかじめ生 成しておいた B と , 動くオプジェクトで動 的に生成した A など , いろいろと考えられ ると思います。 ここで , この 2 つの集合の和をとること にします。 A U B=S という合成です。これ は , 2 つの木を同時に探索しながら比較す ることによって行えます。まず , A と B の親 ノードを比較します。これはどちらも灰色 なので , 結果となる木 , S の親ノードを灰 色として生成します。 次に両者の子ノードを比較していきます。 A の NW は白 , B の NW は灰色です。和をと るときのルールとして , 灰色は白より強い ということを決め , S の NW は灰色ノード であると判断して B の NW をそのままコヒ。 ーします。 A の NE と B の NE はともに仄色で , どちら

ードをそのまま削除してしまうと , 残された 2 つの子ノードのうち片方 は , 行き場を失ってしまう。そこで , 左側の子ノード以下にぶらさがって いる部分木全体の中から最大の値を 持つノードを探して , 削除したいノ ードの値をその値に入れ替える。そ して , 先ほど見つけた ( 最大の値を 持つ ) ノードを (a) または (b) の方法 で削除する (Fig. 9 ) 以上の処理をプログラムで記したもの が , List 4 で , その実行結果は Fig. 10 のとお りです。データの追加・検索・削除がきち んと行えていることを確認してください。 分木と「マップ」 このように , 2 分木ではデータの追加と 検索・削除がとても効率よく ( 理想的には O ( 10g ( n ) ) のオーダーで ) 行えます [ 注 3 ] 。 2001 年 6 月号で取り上げた「バイナリサーチ」も O ( log ( n ) ) の時間で検索を行うことができ ましたが , バイナリサーチの場合は ・あらかじめデータをソートしなければ ならない ・配列を使うので , データの頻繁な追加 と削除を行うのには向かない という欠点がありました。これに対し , 2 分木では , ・データは 2 分木への挿入時に整理され Fig. 11 2 分木を使ったマップ て配置される ・リストと同じようにノード同士をポイ ンタで結ぶだけなので , 挿入や削除が 容易 というメリットがあります。この 2 分木の メリットをもっともじようずに利用してい るのが , C + + 標準ライプラリなどの「マップ ( m 叩 ) 」です。「マップ」は , 「 " キー " と " 値 " をセットにして 1 データとして 2 分木へ挿入 し , " キー " にある値を指定して検索を行え ばそのキーに対応する " 値 " がすばやく検索 できる」という非常に便利な 2 分木の応用例 です (Fig. 11 ) 。「キー」に使うデータ型は , ( 2 分木の性質上 ) 値の大小関係さえ定義で きればよいので , s cmp ( ) 関数などを利用 して文字列をキーにしてしまうことも可能 です ( 文字列をキーにして文字列を検索す る例として List5 を示しておきます ) 。この 「マップ」については , 次回に詳しく紹介し ます。 [ 注 3 ] 計算量が 0 ( log ( n ) ) になる理想的な条 件とは , 「 2 分木が左右バランスのとれ た形で広がり , 枝分かれが豊富」という 状況です。反対に最悪の状況は「すべて のノードが ( 根から葉まで ) 一直線上に 並び , リストとまったく同じ形になっ てしまう」というもので , その場合は挿 入・検索・削除とも 0 ( n ) の時間がかか ってしまいます。できるだけ理想的な 木の形を保っために , 「 AVL 木」や「 B 木」 などといったさまざまなデータ構造が 考え出されています。今回は詳しく紹 介できませんが , 興味があればぜひ調 べてみてください。 「キー」と「値」の組み合わせを 2 分木に登録しておくと , 「キー」に対する「値」をすばやく検索できる 47 starfish" 23 kri 『 アルゴリズム squid 61 しています ! で気軽にメールをお寄せください。お待ち りましたら , 筆者 (algo@teamswift.com/ ま なお , 本連載に関する質問・要望などあ ッシュ表」をテーマにする予定です。 次回は「マップ」と , それに関連した「ハ から・・ だ単に付けたり切り離したりするだけです いならば , もっと簡単になるでしよう。た 木の場合と同じです ( 順序木にしなくてよ を行います。追加や削除などの方法は 2 分 hile 文などを使って子ノードに対する処理 を " ポインタ配列 " などにして , for 文や w 多分木の場合は , 子ノードへのポインタ して「多分木」などと呼びます ) 。 場面に応用ができるでしよう ( 「 2 分木」に対 の組織構成を扱うケースなど , さまざまな ァイルシステムを扱う場合 , あるいは社内 の子ノードを持つ木は , ディレクトリやフ ドを持つようにすることも可能です。多数 張して , 1 つのノードがたくさんの子ノー ノードしか持ちませんでしたが , これを拡 2 分木は 1 つのノードが最大でも 2 つの子 Ⅲ多数の子ノードを持つ木 20 23 31 35 47 53 61 72 88 "dolphin" beluga" grampus kri 『 Otte 「 medusa starfish" beluga swo 「 dfish dolphin" OCtopus 1 5 squid" orca 31 Otte 「 35 medusa 53 0 rca 20 g 「 ampus 88 swordfish" 72 octopus 164 たとえば , 上図で 35 番に対応する文字列を検索する場合 , リニアサーチでは 6 回の比較が必要だが 2 分木を使えば 3 回の比較で検索できる C MAGAZINE 2001 10