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