登場人物紹介
僕：数学が好きな高校生。
テトラちゃん：僕の後輩。 好奇心旺盛で根気強い《元気少女》。言葉が大好き。
リサ：自在にプログラミングを行う無口な女子。赤い髪の《コンピュータ少女》。
$ \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-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回参照）。そうか……僕もずいぶんプログラムの考え方に慣れてきたんだな」
この連載について
数学ガールの秘密ノート
数学青春物語「数学ガール」の中高生たちが数学トークをする楽しい読み物です。中学生や高校生の数学を題材に、 数学のおもしろさと学ぶよろこびを味わいましょう。本シリーズはすでに14巻以上も書籍化されている大人気連載です。 （毎週金曜日更新）
