第327回 二分探索木(前編)

新たなデータ構造「二分探索木」に挑戦する「僕」とテトラちゃん。単純なアルゴリズムに隠れた秘密を探る!

新シリーズ「数学ガールの物理ノート」始動!

『数学ガールの物理ノート/ニュートン力学』

『数学ガールの物理ノート/ニュートン力学』をアマゾンで見る

登場人物紹介

:数学が好きな高校生。

テトラちゃんの後輩。 好奇心旺盛で根気強い《元気少女》。言葉が大好き。

$ \newcommand{\ABS}[1]{\left|\mathstrut #1\right|} \newcommand{\TT}[1]{\textrm{#1}} \newcommand{\ANGLE}[1]{\angle\textrm{#1}} \newcommand{\TRI}[1]{\triangle\textrm{#1}} \newcommand{\HIRANO}{\unicode[sans-serif,STIXGeneral]{x306E}} \newcommand{\SQRT}[1]{\sqrt{\mathstrut #1}} \newcommand{\TRUE}{\textbf{true}} \newcommand{\FALSE}{\textbf{false}} \newcommand{\FOCUS}[1]{\fbox{$#1$}} \newcommand{\GEQ}{\geqq} \newcommand{\LEQ}{\leqq} \newcommand{\NEQ}{\neq} \newcommand{\REMTEXT}[1]{\textbf{#1}} \newcommand{\PS}[1]{\left(#1\right)} \newcommand{\LL}{\left\langle\,} \newcommand{\RR}{\,\right\rangle} \newcommand{\LLRR}[1]{\LL#1\RR} \newcommand{\Enil}{\textbf{nil}} \newcommand{\Fnext}{\textrm{next}} \newcommand{\Fprev}{\textrm{prev}} \newcommand{\Fvalue}{\textrm{value}} \newcommand{\Fleft}{\textrm{left}} \newcommand{\Fright}{\textrm{right}} \newcommand{\Fkey}{\textrm{key}} \newcommand{\LNOT}{\lnot} $

階段教室にて

双倉図書館の一般講座《リンクとストラクチャー》でアルゴリズムを学んできたテトラちゃんは、 自分の理解のため、学んだことをに向けて《講義》している。 僕たちは、線形リスト、双方向リスト、そしてスタックとキューについて議論してきた。

先日までは、学校の図書室の一角で話をしていたけれど、 今日の放課後は階段教室で話をすることになった。

テトラちゃんの新たな《講義》が始まる。

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

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

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

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

登場人物紹介(追加)

リサ:自在にプログラミングを行う無口な女子。赤い髪の《コンピュータ少女》。

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

「なるほど」

リサ「……」

テトラちゃんの言葉にも、リサは特に返事せず、 いつもと同じように真っ赤なノートブック・コンピュータを開いて何かをタイピングしている。

我関せず……と見えるけれど、は知ってる。 彼女は聞いていないようで聞いているし、 おもしろいことがあったらちゃんとコメントしてくれるはずだ。

だから、特に話しかけなくてもいいんだろうな、きっと。

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

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

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

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

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

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

Example Tree(二分探索木の例)

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

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

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

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

二分探索木のノード

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

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

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

は、テトラちゃんの教え方が上手くなっていることに気付いた。

双倉図書館の一般講座で学んだことをまとめただけじゃなくて、 に《講義》する順番をよく考えてきたのかもしれないな。

二分探索木。さっきのExample Treeの例でやりたいことは想像できるけれど、 テトラちゃんの《講義》に耳を傾けよう。

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

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

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

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

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

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

Example Tree(二分探索木の例、再掲)

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

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

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

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

二分探索木のノード

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

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

二分探索木条件

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

二分探索木条件

二分探索木の任意のノードをmとします。

  • ノードmの《左部分木》に属しているノードが持つキーの値は、すべてm.keyよりも小さい。
  • ノードmの《右部分木》に属しているノードが持つキーの値は、すべてm.keyよりも大きい。

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

Example Treeで二分探索木条件を確かめる

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

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

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

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

Example Treeで二分探索木条件を確かめる(続き)

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

クイズ

これは二分探索木ではありません。なぜでしょうか。

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

クイズの答え

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

「《キー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: NEW-NODE

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

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

List 41: NEW-TREE

「いいよ」

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

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

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

List 42: NEW-EXAMPLE-TREEの概略

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

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

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

List 43: NEW-EXAMPLE-TREE(僕の解答)

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

「えっ! 何かもっとすごい方法があるの?」

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

List 44: NEW-EXAMPLE-TREE(テトラちゃんの解答)

は、一瞬ぎょっとしたけれど、List 44を一行一行じっくり読んでみた。なるほどなあ……。

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

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

探索

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

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

「うん」

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

「……いいよ」

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

50というキーがあるかどうかを探索(ステップ1)

いま注目しているノードが持つキーは40です。

でも、いま探しているキーは50です。

40よりも50は大きいので、 探しているキーを持つノードがもしあるとするならば、右部分木にあるはずです!

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

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

50というキーがあるかどうかを探索(ステップ2)

いま注目しているノードが持つキーは60です。

でも、いま探しているキーは50です。

60よりも50は小さいので、 探しているキーを持つノードがもしあるとするならば、左部分木にあるはずです!

「次のステップ3で見つかるね」

テトラ「はい。今度は《ノード60》のleftフィールドをたどった先のノードに注目します。ステップ3です!」

50というキーがあるかどうかを探索(ステップ3)

いま注目しているノードが持つキーは50です。

いま探しているキーは50です。

探しているキーを持つノードが見つかりました!

「そんなふうに、リンクをたどりながら探索していくんだ」

テトラ「はい、そうです。キーの値を比較して、探しているキーが注目しているノードのキーよりも小さければ《左の子》へ進み、大きければ《右の子》に進んでいくんです」

「なるほど。キーの大小を利用して進む……」

テトラ「目的のキーを求めて、あいだを縫うように進んでいくんです」

「そして、小さくも大きくもなかったら、目的のキーを持つノードが見つかったことになるのか……」

テトラ「はい、その通りです。探索成功です!」

「ちょっと待って。理屈はわかったんだけど、ちょっと変な感じがするね」

テトラ「な、何かおかしかったですか?」

「細かいことだけど『50というキーを探す』といっても、すでに50という数は知ってるよね。すでに知ってるものを探しに行くというのがちょっと気になっただけ。 まあ、でも、この二分探索木が数の集合だと考えるなら、 指定した数がここに属しているかどうかを調べるというのは自然なことだけど」

テトラ「そこです! キーという表現を使ったのはそこに関係があります」

「へえ……どういうこと?」

テトラ「本格的なプログラムになりますと、ノードにはさらにフィールドが追加されて、一つのノードにもっと情報を持たせるようになります」

「うーん?」

テトラ「たとえば、10,20,30,……のようなキーは商品の番号になっていて、商品の名前や値段などの情報がノードに記録されているかもしれない、ということです」

「なるほど。何だかコンピュータっぽい話だね。具体的な応用例があるわけだ」

テトラ「けれど、そういう具体的なお話とは独立に、二分探索木というデータ構造は研究することができますので、簡単のためにキーという情報だけをノードに持たせているんです。 キーというのは、目的の情報を得るためのカギになる情報というニュアンスがあります」

「そうか、なるほどね。ここではキーとして整数値を使っているけれど、必ずしもその値そのものが欲しい情報とは限らない。キーという値をカギにしてノードを見つけ、そのノードに欲しい情報が記録されている……という様子を想像すればいいんだね!」

テトラ「そうです、そういうことです!」

「すごくよくわかったよ、ありがとう」

なるほど、とは考える。

ここにも、想像の余地がたくさんあるんだな。話を明確にするために行った単純化がある。 そこに肉付けをして《このような仕組みがあったら、何ができるだろうか》と想像する。

なるほど、なるほど。

テトラ「ではでは、キーを利用して探索を行うSEARCH-TREEという手続きを作りましょう! 問題10です!」

問題10(二分探索木を用いた探索)

二分探索木を用いた探索を行う手続きSEARCH-TREEを作ってください。

入力

  • 探索の対象となる二分探索木$t$
  • 探索するキーの値$k$

出力

  • 二分探索木の中にキーが見つかった場合には<見つかった>を返す。
  • 二分探索木の中にキーが見つからなかった場合には<見つからなかった>を返す。

Example Treeを$t$とした場合の実行例

  • $\textrm{SEARCH-TREE}(t, 50)$ → <見つかった>
  • $\textrm{SEARCH-TREE}(t, 45)$ → <見つからなかった>

テトラ「……」

「ちょっと待って。時間が掛かるかもしれないけど、これは自分でちゃんと考えたい」

はようやくこんな解答にたどりついた。List 45だ。

List 45(僕の解答)

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

「最初は混乱したけど、《似た問題を知らないか》という問いかけでわかったよ。線形リストと発想は同じなんだね」

テトラ「といいますと?」

《繰り返しのパターン》だよ(第324回参照)。《nilになるまで繰り返す》ことや、《場合分けをする》ことや、《次に進む》ことなど、全部同じ。 ただし、SEARCH-TREEの場合……」

  • 《場合分けをする》というのは、kとp.keyとの大小関係での場合分けになる。
  • 《次へ進む》というのは、p.leftに進むかp.rightに進むかの二通りがある。

「……そういう違いはあるけどね」

繰り返しのパターン

テトラ「確かにそうですね! 線形リストのnextが、二分探索木ではleftとrightの二手に分かれています!」

「ところで、テトラ先生の解答は?」

テトラ「は、恥ずかしながら、一般講習で習った解答ですので『あたしの解答』とはいえないんですが……List 46List 47が解答となります」

List 46(テトラちゃんの解答)

List 47(テトラちゃんの解答の続き)

「え?」

は混乱した。

List 46はまだいいけれど、List 47はいったい何だろう……

テトラList 46は、二分探索木の根をSEARCH-SUBTREEに渡すだけの手続きSEARCH-TREEです。List 47は与えられた部分木を再帰的(さいきてき)に探索していく手続きSEARCH-SUBTREEです」

「ちょっと待って。List 47の意味は想像が付くんだけど、頭が整理されない」

テトラ「……」

は考える。

List 47SEARCH-SUBTREEでは、場合分けをしている。四つの場合だ。

(1)$t = \Enil$の場合、<見つからなかった>になる。

(2)$k = t.\Fkey$の場合、<見つかった>になる。

この二つの場合は問題じゃない。問題は残りの二つだ。

(3)$k < t.\Fkey$の場合、$\textrm{SEARCH-SUBTREE}(t.\Fleft, k)$を実行する。

(4)それ以外の場合、$\textrm{SEARCH-SUBTREE}(t.\Fright, k)$を実行する。

これって《自分自身》を実行しているぞ……

「うーん……」

テトラ「……」

しばらく考えて、はようやくわかった。これは漸化式みたいなものか。

「わかったよ。List 47S7S9ではSEARCH-SUBTREEという《自分自身》を呼び出している。これって、漸化式みたいに考えればいいんだね。数学的帰納法みたいともいえるかな」

テトラ「そうです!」

「だよね。ちょうど数列の定義で、第n項を第n-1項で表すみたいに理解すればいいんだね、きっと。帰納的定義だ」

テトラ「はい、そういうことです。講師の先生は再帰的定義と表現なさっていました」

リサリカーシブ

テトラちゃんは、急に声を出したリサの方を振り向いた。

でも彼女は相変わらずノートブック・コンピュータの画面を見たまま、キーボードを叩いている。

テトラ「はい。自分自身を使って定義することを、再帰的定義……recursive definition(リカーシブ・デフィニション)と呼ぶんです」

「変数の値が切り替わるよね。つまり、SEARCH-SUBTREEに入力として与えられている$t$が何を指しているかは、呼ぶたびに決まるんだよね?」

テトラ「はい、そうなります。あたしはこのような図で理解しました。再帰的呼び出し、recursive call(リカーシブ・コール)です。SEARCH-SUBTREEの$t$は、呼び出しごとにメモリ上に別の変数として新たに作られ、呼び出したときの値で初期化されるんです」

再帰的呼び出し

「なるほど。SEARCH-SUBTREEの呼び出しごとに別の$t$が作られて、それぞれ別のノードを指しているんだね」

テトラ「そうなります。そのまま素直に読むこともできます」

「素直に読むって?」

テトラSEARCH-SUBTREEとは何かというと、$t$という二分探索木と、$k$という探索するキーが与えられたとき、そのキーが見つかるかどうかを返すものです。それはどうやって実現されるかというと……」

  • (1)$t = \Enil$の場合、<見つからなかった>を返せばいい。
  • (2)$k = t.\Fkey$の場合、<見つかった>を返せばいい。
  • (3)$k < t.\Fkey$の場合、左部分木に対してSEARCH-SUBTREEを行った結果を返せばいい。
  • (4)それ以外の場合、つまり$k > t.\Fkey$の場合、右部分木に対してSEARCH-SUBTREEを行った結果を返せばいい。

テトラ「(1)と(2)についてはその通りですよね。与えられた部分木がnilだったら<見つからなかった>わけですし、与えられた部分木の根が探しているキーを持っていたら<見つかった>わけです」

「そうだね」

テトラ「そして、(3)と(4)は、いま注目しているノードの左右の部分木に対するSEARCH-SUBTREEがうまく動くと信じることができれば、納得できます。探しているキーが、あるとしたら左部分木と右部分木のどちらにあるかは、二分探索木条件によって決まります。 どちらか片方だけ探索すれば十分ですし、どちらか片方だけ探索した結果が、自分自身の結果に等しくなります」

「なるほど……煙に巻かれたような気もするけれど、確かに素直に読めるなあ」

テトラ「あたし、思うんですが、先輩がおっしゃった《煙に巻かれた気持ち》って、数学的帰納法や漸化式を初めて見たときのあたしの気持ちと同じだと思います! あれ? それで本当にいいの? と感じました……」

「うん、似てるかもね!」

(第327回終わり。第328回へ続く)

二分探索アルゴリズムをさらに詳しく学びたい方はこちらの一冊!

ケイクス

この連載について

初回を読む
数学ガールの秘密ノート

結城浩

数学青春物語「数学ガール」の中高生たちが数学トークをする楽しい読み物です。中学生や高校生の数学を題材に、 数学のおもしろさと学ぶよろこびを味わいましょう。本シリーズはすでに14巻以上も書籍化されている大人気連載です。 (毎週金曜日更新)

この連載の人気記事

関連記事

関連キーワード

コメント

Lsdu2DalePerry う~む、今回の話は数学の言葉で言うと『大きい・小さい』でいいのかな?なんて考えたりして。 4日前 replyretweetfavorite

fall_twtr 「部分木」って言葉が説明なしで出てきたのがちょっと気になったかな。まぁ読んで字のごとくではあるし、すぐ下の図が説明になってるから大きな問題ではないけど 5日前 replyretweetfavorite

fall_twtr リサのセリフ数記録:二言! これで前半だけど、続きとしてはノードを追加したり削除したりするんだろうか。ソートとか計算量の話は…やらんだろうなぁ 5日前 replyretweetfavorite

hyuki 金曜日は『数学ガールの秘密ノート』の日。最新回は一週間無料で読めます。リツイートもお願いね。テトラちゃんからアルゴリズムを教わっている「僕」。今回はどんな問題かな? https://t.co/XmQjM3EcKy 5日前 replyretweetfavorite