第328回 二分探索木(後編)

「二分探索木」をさらに研究する「僕」とテトラちゃん。単純なアルゴリズムに隠れた秘密を探る!

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

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

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

登場人物紹介

:数学が好きな高校生。

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

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

$ \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} $

階段教室にて

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

いまは階段教室で二分探索木の議論をしているところ(第327回参照)。


「テトラちゃんが書いてくれたSEARCH-SUBTREE再帰呼び出しについてはよくわかったと思うよ。 確かに《素直に読める》かもしれない」

テトラ「講師の先生は《再帰的な構造》と《再帰的なコード》が呼応しているとおっしゃっていました」

「構造とコード?」

テトラ「はい。二分探索木は《再帰的な構造》を持っています。どういうことかというと、二分探索木の《根》となるノードはkeyというフィールドとleft, rightというフィールドを持ちます」

「そうだね」

テトラ「そしてleftとrightフィールドの先には、二分探索木の《根》となるノードがリンクされています。言い換えますと、《二分探索木は二分探索木で作られている》ことになります。 《再帰的な構造》です!」

「自分自身を使って作っているからだね。なるほど」

テトラ「コード……つまりプログラムも同じように再帰的に作られています。先ほど(第327回参照)のSEARCH-SUBTREEでは、 入力としてtとkが与えられていますよね。そして……」

「そうか。テトラ先生! 僕が言ってもいいでしょうか?」

テトラ「はい、どうぞ!」

SEARCH-SUBTREEには探索対象となる二分探索木の《根》がtとして与えられている。そして、kの値の大きさに応じて、t.leftを探索対象にするか、t.rightを探索対象にするかを選んだ上でSEARCH-SUBTREEを呼び出している。 言い換えると、《SEARCH-SUBTREESEARCH-SUBTREEで作られている》ことになる。 《再帰的なコード》なんだね」

テトラ「そういうことですね。《素直に読める》というのは決して感覚的なものではなくて、 構造とコードが呼応していることを意味しているんです!」

「おもしろい! おもしろいなあ……」

テトラ「おもしろいですよね」

二分探索木を考える理由

テトラ「……ところで先輩、ここでクイズです! どうしてわざわざ二分探索木などというものを考えるか、その理由はわかりますか?」

「理由……」

は考える。

そもそもノード同士をリンクを使ってつなぐというのは、 大量のデータを出し入れするときに、 メモリ上で動かさずにすむというメリットがあった。工学的理由ともいえる(第322回参照)。

二分探索木でもリンクを使っている。 でもここではまだ、データの出し入れについては何も考えていない。 単にキーの値を《探索》しているだけだ。

二分探索木を使うメリットが何か。大小比較で部分木を進んでいくメリット……

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

「改めて考えると難しいね。二分探索木を使うメリットが何かあるんだろうけど、大小比較して探索していくというのは当たり前じゃないのかなあ?」

テトラ「存在するならば探索していけば見つかるから、大小比較して探索するのは当たり前ということですか?」

「そうそう」

テトラ手間はいかがでしょう」

「手間? ああ、そうか。たぶん、わかったと思う。これは目的のキーが見つかるかどうかじゃなくて、 手間を掛けずにすばやく見つけられるかがポイントなんだね?」

テトラ「そうです!」

「二分探索木では、比較するたびに左部分木か右部分木かのどちらかに進んでいく。目的のキーを順番に一つずつ探していく方法とは違って、 探す対象をすばやく絞り込んでいくことができるんだ」

リサリニアサーチバイナリサーチ

急にリサが声を出したので、僕たちはびっくりした。

リサがいることをすっかり忘れていた。

でもリサは解説を加えるでもなく、こちらを見もせずにタイプを続けている。彼女はタイピングも無音なのだ。

テトラ「……線形リストに10,20,30,40,50,60,70という7個の値があったとして、もしも端から順番に探していく探索アルゴリズムである《リニアサーチ》を使うなら、 50を見つけるまでにノードを5個調べることになります」

線形リストの10,20,30,40,50,60,70から《リニアサーチ》で50を探索

「うん」

テトラ「でも、二分探索木を使った探索アルゴリズムである《バイナリサーチ》を使うなら、Example Treeで50を見つけるまでにノードを3個調べるだけですみます」

Example Treeの10,20,30,40,50,60,70から《バイナリサーチ》で50を探索

「……」

テトラ「50を見つける場合だけじゃありません。《ノードを3個調べる》という手間をゆるすならば、 10,20,30,40,50,60,70という7個のキーのどれでも見つけることができますし、 もしもキーがExample Treeにないなら、それも調べることができます」

「……確かに、確かに」

テトラ「ここで、もしも」

「あー、ちょっと待って待ってテトラちゃん。そこから先は自分で考えたい!」

テトラ「あっ、あっ、はいはいっ!」

は、あわてて手を挙げてテトラちゃんの解説をストップしてもらった。

なるほどなあ……テトラちゃんはよく手を挙げての説明をストップするけれど、 あの気持ちがよくわかる。

《先生》であるテトラちゃんに、どんどん先に話を進められても困る。

いくらおもしろい話だとしても、話をぜんぶ聞いてしまったらおもしろさは激減してしまう。 自分で考える楽しみが大きく損なわれてしまうからだ。

わかるにせよ、わからないにせよ、提示された情報を自分で吟味する時間がほしくなる。

そして、説明をいますぐストップしてほしい!と伝えるためには、即座のアクションが必要になる。

「……」

テトラ「……先輩?」

「うん。テトラちゃんは『《ノードを3個調べる》という手間をゆるすならば』と言ったけど、調べるノードの個数を1個増やして、 《ノードを4個調べる》という手間をゆるすならば、 こんな二分探索木を作っておけば、15個のキーから見つけることができるよね」

テトラ「はい……その通りです。まさにその話をしようと思っていました……」

「そして、そこまで考えたら一般化できると思った。こういう問題11が自然に浮かび上がる。 そして、これは、数列の漸化式(ぜんかしき)として考えられる!」

問題11(二分探索木)

二分探索木で《ノードをn個調べる》という手間をゆるしたときに、 最大でK(n)個のキーから正しく探索できるとする。

K(n)をnで表せ。

テトラ「はい、そうですね。これを解くのは難しくはありません。なぜなら……」


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

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

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

人気の連載

おすすめ記事

再帰的定義をもっと学ぶにはこの一冊!

プログラマの数学第2版

結城 浩
SBクリエイティブ; 第2版
2018-01-17

ケイクス

この連載について

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

結城浩

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

この連載の人気記事

関連記事

関連キーワード

コメント

TkBohz "でも、ここはしっかり守らなければ。知ってしまったら、知らない状態に戻れないんだから。" 3ヶ月前 replyretweetfavorite

hyuki 森を抜けて仕事場へ。と書きつつ今日も自宅作業。毎週金曜日更新のWeb連載「数学ガールの秘密ノート」を書く一日です。なお最新回は無料で読めますのでぜひどうぞ!アルゴリズムのシーズンは早くも終盤です! https://t.co/PbJy8sD3HC 3ヶ月前 replyretweetfavorite

fall_twtr 話の流れ的に、「僕」がINSE 3ヶ月前 replyretweetfavorite

fall_twtr 先週こんなこと言っちゃったがちゃんと計算量出てきたな。「手間」という表現で、計算量を抑える観点から逆転… https://t.co/3esCtJUmQK 3ヶ月前 replyretweetfavorite