第329回 二分探索木のバランス(前編)

「二分探索木」を解説するテトラちゃん。二分探索木が持つ危険性とは? 単純なアルゴリズムに隠れた秘密を探る!

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

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

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

登場人物紹介

:数学が好きな高校生。

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

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

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

階段教室にて

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

二分探索木で、目的のキーを探索するまでに調べなくてはならないノードの個数を増やせば、正しく探索できるキーの個数は指数関数的に増えることがわかった(第328回参照)。 少ない手間でたくさん探索できるということだから、これはうれしいことだ。

ただし、効果的に二分探索木を使うには、二分探索木がバランスしている必要がある。

僕たちは二分探索木をSEARCH-TREE探索するだけではなく、 二分探索木を構築するためのINSERT-TREEという手続きを作ったところ(第328回参照)。


テトラwhileの繰り返しを使ったループ版と、再帰呼び出しを使ったリカーシブ版。 それからleftとrightのどちらに代入するかを判断するためにフラグを使う版、使わない版。 いろんな版のINSERT-TREEが実装できましたね!」

「それで……二分探索木をバランスさせるのはなかなか難しいという話だったと思うんだけど」

テトラ「はい、そうです。実際にいろいろ試すと具体的によくわかります。《例示は理解の試金石》ですから!」

「例といえば、INSERT-TREEExample Treeに45を挿入する例は確かめたよね(第328回参照)」

Example Treeに45を挿入する

テトラ「それはそうなんですが、でもそこではExample Treeがすでに存在したとして、 その上で45を入れました」

「つまり、これからは、二分探索木を何もないところから構築しようという話?」

テトラ「ですです。NEW-TREEを呼び出せば、空の二分探索木が作れます。そこでINSERT-TREEを繰り返し呼び出して、必要なキーを持った二分探索木を作れますよね。 これが問題13です!」

問題13 配列から二分探索木を作る(NEW-TREE-FROM-ARRAY)

与えられた配列の要素をキーに持つ二分探索木を作る手続きNEW-TREE-FROM-ARRAYを作ってください。

入力

  • 要素としてキーを表す数が格納された配列$A = \LLRR{a_1,a_2,\ldots,a_n}$(ただし、配列の要素はすべて異なった値を持つとする)
  • 配列に格納されている要素数$n$

出力

  • キーとして$a_1,a_2,\ldots,a_n$を持っている二分探索木

使うことができる手続き

  • NEW-TREE() は空の二分探索木を作って返す手続き
  • INSERT-TREE(t, k) は二分探索木tにキーkを挿入する手続き


「これはすぐにできるね。たとえばList 53のようにすればいい。《繰り返しのパターン》そのままだ(第324回参照)。そうか……僕もずいぶんプログラムの考え方に慣れてきたんだな」

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

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

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

人気の連載

おすすめ記事

確率分布を考えたアルゴリズムの解析、その一歩はこの本から!

ケイクス

この連載について

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

結城浩

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

この連載の人気記事

関連記事

関連キーワード

コメント

asangi_a4ac そこにもABACABAが出てくるのか https://t.co/CHIXpOWZqv 3ヶ月前 replyretweetfavorite

fall_twtr 2週前にこんなこと言ってたけど、今回でソートやらの話になった。よく考えたら2話で1つの話題… https://t.co/bGHa2Kz1AG 3ヶ月前 replyretweetfavorite

fall_twtr ミルカさん!! ミルカさんもリサ(ちゃん)も「ビットレートが高い」けど、数単語のやり取りって結城先生の中で内容の想定があったりするんだろうか 3ヶ月前 replyretweetfavorite

fall_twtr 中断やや上の「たとえば10,20,30だと三通りある」は、五通りかな? 3ヶ月前 replyretweetfavorite