{% include head.html %}
日本語で説明する場合も、ステップごとに分けた方が読みやすい。
二分探索木
-
$T$ の根の要素を$c$ とする。 -
$p<c$ であれば、c の左側の木$T_1$ に p を挿入する。$c<p$ であれば、右側の木$T_2$ に p を挿入する。
なお、$p=c$ であれば、要素 p が既に二分探索木に含まれているので、操作を終了する。 - 選択した
$T_i$ が末端の葉$l$ である場合、$p,l$ の大小関係に応じて、$p$ を$l$ の左または右の子として挿入する。 - 選択した
$T_i$ が葉でない1場合、$T_i$ に対し、今回定義している$p$ の挿入を再帰的に行う。
二分探索木
- まず、通常の二分探索を行い、$p$ の位置まで移動する2。
-
$p$ が$T$ の葉である場合、$p$ を削除する。 -
$p$ が葉でなく、左側に$p$ より小さい要素の木$T_1$ を持つ場合、$T_1$ の最大の要素を削除し、$p$ の位置に移動させる。
また、このような$T_1$ を持たないとき、$p$ は自身より大きい要素のみからなる木$T_2$ を右側にもつ。この場合は、$T_2$ の最小の要素を削除し、$p$ の位置に移動させる。
参考：ブログ
今回の問題で登場した文字列の出現検知手法をTrie木という。
Trie木は、文字列の効率的な検索（retrieval）のために使われるデータ構造。現在の位置から始まる文字列が、それ以前にも出現しているかを True or False で検知する。
アルファバットの種類の総数を a[i:i+4] と表すことにする。
文字列を前から走査していき、どのアルファベットでもない空の文字
- はじめに
i=1とする。 a[i:i+4]の文字に対応する位置にノードを挿入する。
なお、途中まで同じ文字列がすでに木構造に存在する場合、そこから枝分かれする形でノードを挿入し、検知結果としてTrueを出力する。
途中まで同じ文字列が存在しない場合、Falseを出力する。i=i+1としてこの作業を文字列の終わりまで繰り返すと、各文字列a[i:i+4]の部分文字列がそれ以前に出現しているかを調べることができる。。
B-tree（B木）は、データを格納するための木構造の１種であり、$O(\log n)$ の計算量3で目的のデータに辿り着くことができる。
B木の最大の特徴は、各ノードに複数のデータを格納できることであり、データの挿入や削除をする際に操作を工夫することで、木構造が以下の条件を常に満たすようにしている。
- 葉ノード以外は常に２つ以上の以上の子ノードを持つ
-
$M$ 個のキー（データ）を持つノードは$M+1$ 個の子ノードを持つ - 葉ノードはすべて同じレベル（高さ）である
- 各キーにおいて、左の子ノードには小さい値、右の子ノードには大きい値が入る4
B-tree を関係データベースに特化させた木構造を B+ 木と呼ぶ。B+ 木では、B-tree の葉のみにデータを格納し、２段目以上の部分を索引（インデックス）として利用する。
値の検索・挿入・削除の方法は通常の B-tree と同様であるが、B+ 木では葉のノード間にもポインタが用意されている。これにより、関係データベースで多用される 値の範囲検索 を高速化することができる。ただし、データを葉ノードに格納するため、挿入コストは大きくなる。
また、B-tree をファイルシステムに応用した B*木がある。
“B-tree” の名前の由来は、考案者の1人Bayer の頭文字, 考案した時の関係会社 Boeing の頭文字, または Balanced の頭文字等、諸説のうち第1説が有 力だが,本人の釈明もないので、本文では単に B-tree と呼ぶことにする
（Googleより）
(1)〜(4)：各8点
(5)〜(6)：各9点
（50点満点）
{% include foot.html %}