登場人物紹介
僕:数学が好きな高校生。
テトラちゃん:僕の後輩。 好奇心旺盛で根気強い《元気少女》。言葉が大好き。
ミルカさん:数学が好きな高校生。 僕のクラスメート。長い黒髪の《饒舌才媛》。
リサ:自在にプログラミングを行う無口な女子。赤い髪の《コンピュータ少女》。
双倉図書館の一般講座《リンクとストラクチャー》でアルゴリズムを学んできたテトラちゃんは、 自分の理解のため、学んだことを僕に向けて《講義》している。 僕たちは、線形リスト、双方向リスト、そしてスタックとキューについて議論してきた。 いまは階段教室で二分探索木の議論をしているところ。
効果的に二分探索木を使うには、二分探索木がバランスしている必要がある。 そしてそのためには二分探索木にキーを挿入する順番が意味を持ってくるのだ。
僕たちが、キーの配列から二分探索木を作る手続きNEW-TREE-FROM-ARRAYについて議論していると、 ミルカさんもやってきた。
ミルカ「……NEW-TREE-FROM-ARRAYが作る二分探索木(第329回参照)でバランスを取りたいとき、 シンプルでしかも効果的な方法としてシャフリングがある。 テトラの《講義》ではまだ出てきてないとリサから聞いたが」
僕「シャフリング?」
テトラ「shufflingは、トランプのシャッフルのことですね?」
ミルカ「そう」
リサ「SHUFFLE-ARRAYを書いた」
List 55 SHUFFLE-ARRAY
入力
出力
※(Donald E. Knuth, "The Art of Computer Programming (2) 日本語版 Seminumerical algorithms"のAlgorithm Pより)
僕「List 55は、配列Aの要素をランダムに並べ替えるという手続きになるんだね?」
リサは僕の言葉に黙ってうなずく。
テトラ「これでうまくいくんですか……」
ミルカ「List 55のSHUFFLE-ARRAYの実行後、 配列Aの各要素は、元の配列の要素のどれにもなり得ることはすぐにわかる。 すべての順列が等確率で得られるかどうかはちゃんと解析する必要があるが」
僕「配列の要素をトランプの要素のようにシャッフルする。 そうしてから、INSERT-TREE-FROM-ARRAYを呼び出してやれば、 二分探索木がアンバランスにならないということなんだね」
ミルカ「そういうこと。もちろんこれも証明が必要な主張だけれど、 シャフリングによって平均的にバランスした二分探索木が作られそうだという予想はつく」
テトラ「シャフリングは、順番をぐちゃぐちゃにしてしまいますよね。 ぐちゃぐちゃにした方が効率的な探索ができるというのはおもしろいと思いますっ! 順番に、 整然と処理した方が効率がよさそうだと考えたくなりますから」
僕「確かにおもしろいね」
ミルカ「さて、問題はここからだ」
僕「?」
ミルカ「INSERT-TREE-FROM-ARRAYの場合はシャフリングでもいいのだが、 いつもこの方法が使えるとは限らない」
僕「それはどういう意味? 配列をシャッフルできない場合があるなんて想像できないんだけど」
ミルカ「配列からキーを二分探索木に挿入するというときには、 挿入したいすべてのキーがすでにまとまって存在している。 しかし、二分探索木に挿入したいキーが少しずつ与えられる場合はどうか」
僕「少しずつ?」
ミルカ「キーがストリームとして与えられるといってもいい」
僕「あまりピンと来ないなあ」
ミルカ「ふむ。二分探索木はたくさんのキーを保持していて、 SEARCH-TREEを使ってその中から目的のキーを探索することができる」
僕「そうだね」
ミルカ「二分探索木にINSERT-TREEを使ってキーを一つずつ入れていくその途中のどの時点でも、 二分探索木は、そこまでに挿入されたキーを保持しているし、 SEARCH-TREEを使ってキーを探索できる」
僕「そうか。 もしもキーをぽつんぽつんと挿入していくとしたら、 《まとめてシャッフル》はできないということ?」
ミルカ「そういうこと。 もちろん、シャッフルができないわけじゃない。 二分探索木にキーを入れるのと並行して、これまでに挿入したキーをどこかに確保した配列に入れておき、 適当なタイミングで配列をシャッフルして二分探索木を新たに作り直す……そんな手間を掛ければシャッフルはできる。 しかし、明らかにそれはずいぶん無駄な手間だ」
テトラ「ミルカさんがおっしゃってるのはこういうことですよね?」
ミルカ「その通り。これは自然な要求だ」
僕「いやいや、それは無茶だよ。だって、キーを挿入する順序で二分探索木の形は決まってしまうからね。 ぽつんぽつんとやってくるキーは大小関係によって、その二分探索木のどこに収まるかが一意に定まるはず。 だからこそ、二分探索木で探索できるわけだから。 キーを10,20,30,...のように小さい順で挿入しても、 キーを100,90,80,70,...のように大きい順で挿入しても、 ランダムな順で挿入しても、バランスした二分探索木にするなんて、無茶じゃないの?」
テトラ「先輩、先輩、でも、そうじゃないんです」
僕「え?」
無料で「試し読み」できるのはここまでです。 この続きをお読みになるには「読み放題プラン」へのご参加が必要です。
ひと月500円で「読み放題プラン」へご参加いただきますと、 434本すべての記事が読み放題になりますので、 ぜひ、ご参加ください。
参加済みの方/すぐに参加したい方はこちら
結城浩のメンバーシップで参加 結城浩のpixivFANBOXで参加(2021年7月2日)