第329回シーズン33 エピソード9

二分探索木のバランス（前編）

登場人物紹介

僕：数学が好きな高校生。

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

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

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

階段教室にて

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

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

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

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

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

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

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

僕「例といえば、INSERT-TREEでExample 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回参照）。そうか……僕もずいぶんプログラムの考え方に慣れてきたんだな」

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

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

読み放題プランへのご参加について

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

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

（2021年6月25日）

記事の一覧

第329回 シーズン33 エピソード9 二分探索木のバランス（前編）

階段教室にて

結城浩（ゆうき・ひろし） @hyuki

第329回シーズン33 エピソード9

二分探索木のバランス（前編）