登場人物紹介
僕：数学が好きな高校生。
テトラちゃん：僕の後輩。 好奇心旺盛で根気強い《元気少女》。言葉が大好き。
ミルカさん：数学が好きな高校生。 僕のクラスメート。長い黒髪の《饒舌才媛》。
リサ：自在にプログラミングを行う無口な女子。赤い髪の《コンピュータ少女》。
【お休みのお知らせ】
結城浩です。いつもご愛読ありがとうございます。 おかげさまでこのWeb連載も今回で第330回を迎えました！
みなさまの応援に感謝します。
さて、たいへん恐れ入りますが、さらなるパワーアップをはかるため、 このWeb連載の更新を2021年8月13日までお休みさせてください。
日程は以下の通りです。ご迷惑をおかけしますが、よろしくお願いいたします。
Web連載「数学ガールの秘密ノート」予定
・2021年7月2日（金）第330回更新
・2021年7月9日〜2021年8月13日 お休み
・2021年8月20日（金）第331回更新
・（以後、毎週金曜日更新）
階段教室にて
双倉図書館の一般講座《リンクとストラクチャー》でアルゴリズムを学んできたテトラちゃんは、 自分の理解のため、学んだことを僕に向けて《講義》している。 僕たちは、線形リスト、双方向リスト、そしてスタックとキューについて議論してきた。 いまは階段教室で二分探索木の議論をしているところ。
効果的に二分探索木を使うには、二分探索木がバランスしている必要がある。 そしてそのためには二分探索木にキーを挿入する順番が意味を持ってくるのだ。
僕たちが、キーの配列から二分探索木を作る手続きNEW-TREE-FROM-ARRAYについて議論していると、 ミルカさんもやってきた。
ミルカ「……NEW-TREE-FROM-ARRAYが作る二分探索木（第329回参照）でバランスを取りたいとき、シンプルでしかも効果的な方法としてシャフリングがある。 テトラの《講義》ではまだ出てきてないとリサから聞いたが」
僕「シャフリング？」
テトラ「shufflingは、トランプのシャッフルのことですね？」
ミルカ「そう」
リサ「SHUFFLE-ARRAYを書いた」
List 55 SHUFFLE-ARRAY
入力
- A: 整数の配列
- n: 配列Aの要素数
出力
- なし（シャッフルした結果は配列Aに反映される）
※（Donald E. Knuth, "The Art of Computer Programming (2) 日本語版 Seminumerical algorithms"のAlgorithm Pより）
僕「List 55は、配列Aの要素をランダムに並べ替えるという手続きになるんだね？」
リサは僕の言葉に黙ってうなずく。
テトラ「これでうまくいくんですか……」
- jの値はnから1ずつ減っていきます。そのそれぞれのjに対して……
- 1以上j以下のランダムな整数をkに代入して、A[j]とA[k]を交換します。
ミルカ「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,...のように大きい順で挿入しても、 ランダムな順で挿入しても、バランスした二分探索木にするなんて、無茶じゃないの？」
テトラ「先輩、先輩、でも、そうじゃないんです」
僕「え？」
この連載について
数学ガールの秘密ノート
数学青春物語「数学ガール」の中高生たちが数学トークをする楽しい読み物です。中学生や高校生の数学を題材に、 数学のおもしろさと学ぶよろこびを味わいましょう。本シリーズはすでに14巻以上も書籍化されている大人気連載です。 （毎週金曜日更新）
