第327回 シーズン33 エピソード7

二分探索木（前編）

階段教室にて

テトラ「先輩、それでは今日は二分探索木のお話をしたいと思いますっ！」

僕「階段教室は広い黒板が使えるからいいね。 図もたくさん書いて議論できそうだ」

テトラ「今回は、お願いしてリサちゃんにも来ていただきました」

リサ「《ちゃん》は不要」

テトラ「リサちゃ……リサには、 あたしが変なことを言ったら注意してもらおうと思って声を掛けたんです。 よろしくお願いします」

僕「なるほど」

リサ「……」

僕「それで、今日のお題は《二分探索木》なんですね、テトラ教授！」

テトラ「いつのまにか教授になってますよ……はい。 《二分探索木》……Binary Search Treeというデータ構造です。略してBSTと呼ぶこともあります」

僕「バイナリ・サーチ・ツリー」

テトラ「これまではノードが一次元に並ぶデータ構造だけを考えてきましたが、二分探索木は違います」

僕「そういえばそうだね。スタックも、キューも、ぜんぶ一次元といえば一次元か。 要素を《横》から取り出したりはしないから？」

テトラ「はい。線形リスト、双方向リスト、スタック、キュー……すべてノードが一列に並んでいました。 今日お話する《二分探索木》も、情報を格納するノードが繋がっていますが、 こんなふうになっています。これは10から70までの情報を格納した二分探索木の例です。これをExample Treeと呼ぶことにします」

僕「樹形図みたいに枝分かれしているね」

テトラ「二分探索木は、全体としてはこのような形をしているんですが、 細かく見ますと、ノードがリンクでつながりあっていることがわかります」

僕「そうだね。そこは線形リストや双方向リストと同じ仕組みになってる」

テトラ「二分探索木にもさまざまな実装方法がありますが、ここでは一つのノードが三つのフィールドを持つ実装にしています。key、left、rightというフィールドです」

僕「keyと、leftと、right。このノードにはvalueはないんだね」

テトラ「はい。 ノードが持つ値はkeyというフィールドに収めることにしています。 理由はまた後ほどお話ししますね」

僕「はい、わかりました。お待ちします、先生！」

テトラ「一つのノードにはkeyとleftとrightというフィールドがあります」

• keyフィールドには、キーと呼ばれる整数値を保持します。
• leftフィールドには、このノードの「左」にあるノードへのリンクが保持されています。左につながったノードを左の子といいます。
• rightフィールドには、このノードの「右」にあるノードへのリンクが保持されています。右につながったノードを右の子といいます。

僕「さっきのExample Treeには $-\infty$ というノードがあったよね。これはリストヘッドみたいなもの？」

テトラ「はい、そうです。これは実装の都合で用意したノードです。 この二分探索木のどのノードが持つキーよりも小さな値であればかまわないのですが、便宜上、 $-\infty$ というキーとしています。そして、 $-\infty$ のノードのrightフィールドが指しているノードを、二分探索木の根（ね）と呼びます」

僕「ね……というのは根っこの根？」

テトラ「ですです。二分探索木を木に見立てたときの根です。Example Treeでは《ノード40》が根になります」

僕「それから、leftとrightに保持されているリンクは、メモリ上のアドレスだよね？」

テトラ「はいはい、そう考えてくださってかまいません。 要するに左や右のノードに《たどり着く》ための情報ならばいいので、 アドレスでなければいけないというものではありませんけれど」

僕「うん、わかったよ。リンクをたどる話は、これまでもたくさんしてきたからね。これまではnextやprevでたどったけれど、 こんどはleftやrightでたどる。大丈夫、イメージできるよ」

テトラ「リンクの中には《どこも指していない》ことを表すnilというリンクもあります。図では斜線で表すこともあります。 これもすでにお話ししましたよね。 ですから、二分探索木のノードは、子の存在に関して四通りのパターンがあることになります」

僕「そうだね。ここまでの話は、線形リストや双方向リストとだいたい同じだ」

テトラ「はい。ここからが《二分探索木》ならではのお話になります」

二分探索木条件

テトラ「二分探索木には満たすべき条件があります。二分探索木条件という条件です」

僕「……なるほど！　これはおもしろいね。テトラちゃんが言う《二分探索木条件》というのは、 Example Treeでいえば、具体的にこういうことだよね。キーの値が40になっているノードより左側にあるどのノードを見ても、キーの値は40よりも小さくなっている。 そして、右側にあるどのノードを見ても、キーの値は40よりも大きくなる」

テトラ「そうです。そうです。先輩はやっぱりすぐに例で確かめるんですね」

僕「《例示は理解の試金石》だからね。 しかもテトラちゃんが最初に例を出してくれたから、それを使いたくなる」

テトラ「先輩はExample Treeの一つのノードについて二分探索木条件を確かめましたが、 この条件は二分探索木のどのノードについても成り立たなければいけません」

僕「ああ、なるほど。こういうことだね。ノード20の左右についても、ノード60の左右についてもそれぞれ二分探索木条件が成り立つ」

テトラ「ではここでクイズをお出しします。 たとえば、これは二分探索木ではありません。なぜでしょうっ！……って簡単ですね」

僕「……これはもちろん《二分探索木条件》を満たさないからだよね。ここと、ここ」

テトラ「はい、正解です！」

僕「《キー32のノード》の《右の子》に、 《キー28のノード》があるけど、これはおかしい。 《二分探索木条件》によれば、 右部分木にあるどのノードも、32より大きなキーじゃなくてはいけないはずだから」

テトラ「ですね」

僕「それから、《キー61のノード》の《右の子》の《左の子》に、 《キー59のノード》があるけれど、これもおかしい。 なぜかというと、これじゃあ61の右部分木の中に61よりも小さなノードがあることになってしまう。 これも《二分探索木条件》に反する」

テトラ「はい……あたし、これと同じ問題が出たときに28がおかしいことはわかったんですが、 59がおかしいことには気付きませんでした」

僕「へえ……」

テトラ「それはですね、61と63を比べたら正しく63の方が大きくて、 63と59とを比べたら正しく59の方が小さかったからです」

僕「なるほどね。大小関係を局所的に見ちゃったんだね」

テトラ「局所的……」

僕「ノード一つ分、親子関係一個分だけみて判断しちゃったという意味だよ」

テトラ「そうです、そうです」

二分探索木を組み立てよう

僕「じゃあ、これで二分探索木のプログラムを書くのかな？」

テトラ「そうですね。List 40が、二分探索木のノードを作る手続きNEW-NODEです。 本来なら、双方向リストと違う名前にした方がいいんですが、NEW-BINARY-SEARCH-TREE-NODEだと長すぎますのでNEW-NODEとします」

僕「List 40は特に不思議なことはないね。ノードを確保して、 left, right, keyというフィールドに初期値を入れる」

テトラ「そして、List 41が、空っぽの二分探索木を作る手続きNEW-TREEです。 リストヘッドに相当するノードを確保します。キーの値は便宜的に $-\infty$ とします」

僕「いいよ」

テトラ「では、ここでクイズです。NEW-TREEとNEW-NODEを使って、 Example Treeを組み立てる手続きNEW-EXAMPLE-TREEを作ってください！」

僕「おお、なるほど！ これは、10から70までのキーを持つノードをNEW-NODEで作って、 フィールドを適切にリンクすればいいというクイズだよね？」

テトラ「そうです、そうです。そういうことです。 NEW-EXAMPLE-TREEの概略はList 42のようになります。 この3行目を具体的に書くことになります」

僕「この3行目って、たった一行になっているけど、ものすごい重みがあるなあ！　ここを詳細化したら何行になるんだろう！」

テトラ「いかがでしょう」

僕「うん、地道につないでいけばできるね。List 43で完成かな」

テトラ「ああ！　なるほどです」

僕「えっ！　何かもっとすごい方法があるの？」

テトラ「いえいえ、違います。そうですよね。一つ一つ作ってから組み上げればいいんですよね……あたしは、 List 44のようにすごいことになってしまいました」

僕「僕は下から上に作っていったけど、テトラちゃんは上から下に作っていったんだね。いろんな方法があるんだ」

テトラ「できたものは同じくExample Treeになりますね」

探索

僕「次はどういう話になるの？」

テトラ「はい、ではいよいよ二分探索木を使った探索のお話をします。Example Treeを使って説明しますね」

僕「うん」

テトラ「Example Treeには10から70までのキーがありますが、 この二分探索木の中に50というキーがあるかどうかを探索したいとします」

僕「……いいよ」

テトラ「この二分探索木の根となっている《ノード40》に注目してスタートして、次のように考えます。ステップ1です」

僕「うんうん、それを繰り返すんだね！」

テトラ「はいはい、そうです。《ノード40》のrightフィールドをたどった先にあるノードに注目します。 これは右部分木の根にあたります。 ステップ2です！」