[logo] Web連載「数学ガールの秘密ノート」
Share

第330回 シーズン33 エピソード10
二分探索木のバランス(後編)

登場人物紹介

:数学が好きな高校生。

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

ミルカさん:数学が好きな高校生。 のクラスメート。長い黒髪の《饒舌才媛》。

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

$ \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{\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{\Fpriority}{\textrm{priority}} \newcommand{\Fup}{\textrm{up}} \newcommand{\Fkey}{\textrm{key}} \newcommand{\LNOT}{\lnot} $

階段教室にて

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

効果的に二分探索木を使うには、二分探索木がバランスしている必要がある。 そしてそのためには二分探索木にキーを挿入する順番が意味を持ってくるのだ。

僕たちが、キーの配列から二分探索木を作る手続き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 55SHUFFLE-ARRAYの実行後、 配列Aの各要素は、元の配列の要素のどれにもなり得ることはすぐにわかる。 すべての順列が等確率で得られるかどうかはちゃんと解析する必要があるが」

「配列の要素をトランプの要素のようにシャッフルする。 そうしてから、INSERT-TREE-FROM-ARRAYを呼び出してやれば、 二分探索木がアンバランスにならないということなんだね」

ミルカ「そういうこと。もちろんこれも証明が必要な主張だけれど、 シャフリングによって平均的にバランスした二分探索木が作られそうだという予想はつく」

テトラ「シャフリングは、順番をぐちゃぐちゃにしてしまいますよね。 ぐちゃぐちゃにした方が効率的な探索ができるというのはおもしろいと思いますっ! 順番に、 整然と処理した方が効率がよさそうだと考えたくなりますから」

「確かにおもしろいね」

ミルカ「さて、問題はここからだ」

「?」

新たな問題

ミルカINSERT-TREE-FROM-ARRAYの場合はシャフリングでもいいのだが、 いつもこの方法が使えるとは限らない」

「それはどういう意味? 配列をシャッフルできない場合があるなんて想像できないんだけど」

ミルカ「配列からキーを二分探索木に挿入するというときには、 挿入したいすべてのキーがすでにまとまって存在している。 しかし、二分探索木に挿入したいキーが少しずつ与えられる場合はどうか」

「少しずつ?」

ミルカ「キーがストリームとして与えられるといってもいい」

「あまりピンと来ないなあ」

ミルカ「ふむ。二分探索木はたくさんのキーを保持していて、 SEARCH-TREEを使ってその中から目的のキーを探索することができる」

「そうだね」

ミルカ「二分探索木にINSERT-TREEを使ってキーを一つずつ入れていくその途中のどの時点でも、 二分探索木は、そこまでに挿入されたキーを保持しているし、 SEARCH-TREEを使ってキーを探索できる」

「そうか。 もしもキーをぽつんぽつんと挿入していくとしたら、 《まとめてシャッフル》はできないということ?」

ミルカ「そういうこと。 もちろん、シャッフルができないわけじゃない。 二分探索木にキーを入れるのと並行して、これまでに挿入したキーをどこかに確保した配列に入れておき、 適当なタイミングで配列をシャッフルして二分探索木を新たに作り直す……そんな手間を掛ければシャッフルはできる。 しかし、明らかにそれはずいぶん無駄な手間だ」

テトラ「ミルカさんがおっしゃってるのはこういうことですよね?」

  • 二分探索木にキーを挿入していきます。
  • ただし、二分探索木に保持したいキーが出てきたタイミングで、キーをそのつど挿入していくことにします。
  • しかも、挿入するキーが大小関係において、どういう順番でやってくるかはわからないとします。
  • それにも関わらず、キーを挿入した各時点で、二分探索木ができるだけバランスしているようにしましょう……

ミルカ「その通り。これは自然な要求だ」

「いやいや、それは無茶だよ。だって、キーを挿入する順序で二分探索木の形は決まってしまうからね。 ぽつんぽつんとやってくるキーは大小関係によって、その二分探索木のどこに収まるかが一意に定まるはず。 だからこそ、二分探索木で探索できるわけだから。 キーを10,20,30,...のように小さい順で挿入しても、 キーを100,90,80,70,...のように大きい順で挿入しても、 ランダムな順で挿入しても、バランスした二分探索木にするなんて、無茶じゃないの?」

テトラ「先輩、先輩、でも、そうじゃないんです」

「え?」

無料で「試し読み」できるのはここまでです。 この続きをお読みになるには「読み放題プラン」へのご参加が必要です。

ひと月500円で「読み放題プラン」へご参加いただきますと、 420本すべての記事が読み放題になりますので、 ぜひ、ご参加ください。


参加済みの方/すぐに参加したい方はこちら

結城浩のメンバーシップで参加 結城浩のpixivFANBOXで参加

(2021年7月2日)

[icon]

結城浩(ゆうき・ひろし) @hyuki


『数学ガール』作者。 結城メルマガWeb連載を毎週書いてます。 文章書きとプログラミングが好きなクリスチャン。2014年日本数学会出版賞受賞。

Twitter note 結城メルマガ Mastodon Bluesky Threads Home