第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です!」

この続きは有料会員登録をすると
読むことができます。
cakes会員の方はここからログイン

1週間無料のお試し購読する

cakesは定額読み放題のコンテンツ配信サイトです。簡単なお手続きで、サイト内のすべての記事を読むことができます。cakesには他にも以下のような記事があります。

人気の連載

おすすめ記事

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

ケイクス

この連載について

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

結城浩

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

この連載の人気記事

関連記事

関連キーワード

コメント

ikumikeita https://t.co/VLnNia4ksO あれ、しまった、先週の回は読み損ねていたみたい。 4ヶ月前 replyretweetfavorite

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

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

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