MIT Open course: Introduction to Algorithmsのまとめ(9～11回)

データ構造1、木

◆二分探索木　BST(Binary Search Tree)
◯特徴
各ノードに値をもち、その値が左の子ノードの値以上で、右の子ノードの値以下であるような2分木
・詳細はここで→binary search tree
・クイックソートと順番は異なるが同じ比較を行う。
◯計算時間
・walk　O(n)
・n挿入 ①常にΩ(nlogn) if lucky (balanced tree) ②O(n^2) if unlucky(already sorted)

◆ランダム2分探索木
◯特徴
・入力列をランダムに並び替えてから、BSTを作る
・ランダムクイックソートとほぼ同じ
◯計算時間
・E[探索計算量]=Θ(logn)←各ノードの深さの平均
・E[height of Rand.built BST]=Θ(logn)←Randバージョンでの木の高さ(w-c)の平均、証明略
→平均して、高さlognのBalanceのとれた木が完成する

◆Red Black Tree
◯特徴
・定義
①全てのノードは黒か赤のフィールドを持つ
②根と葉は黒
③赤ノードの親は黒ノード
④あるノードxの全ての末裔への黒のみの高さ(black-height(x))は共通
◯計算時間
・height<=Θ(logn)→worst caseでも常にO(logn)
（直感的な理解は、赤ノードを黒ノードにくっつけた木T'を考えれば、葉は全て同じ深さとなる。T'の高さh'は、③を考えれば元の高さhの半分以上で、葉の数(nくらい)は2^h'よりも大きい）
・クエリー(探索、最小、最大...)もアップデート(挿入、消去)もO(logn)
◯挿入
・普通に挿入し、ノードの色を赤にする
・③の矛盾を解決するために、①色変更(ほとんどこの操作)、②rotationを繰り返し実行

◆データ構造の作成←既存のデータ構造を利用して新しいデータ構造を設計する
◯方法論(一般)
1.元となるデータ構造を決定する
2.追加の情報を決定する
3.修正操作(insert等)によって特徴が保たれるかどうかを検証する
4.新しい操作を追加する
◯例1 ある配列が与えられたときに、「k番目に小さい値を返す」、「ある値xが何番目に小さいかを返す」のに都合の良いデータ構造を作りたい(Dynamic order statistics)
1.r-b tree
2.部分木のサイズをノードに持たせる(rankをもたせると修正が困難)
3.rotationしても、部分木のサイズの修正はO(1)で可能
4.OS-select, OS-rank
◯例2 たくさんの区間が与えられたときに、「ある区間x=[low[x],high[xがどの区間と交わるかを返す」のに都合のようデータ構造を作りたい
1.r-b tree
2.key=low[x],部分木の中で最大の値を情報としてもつ
3.rotationしても、部分木情報の修正はO(1)で可能
4.Interval-search

木について、初めてまともに勉強した。2-3-4treeやB-treeなど他にも色々とあるんだけどね。

基本的な木の構造は覚えて、直感的に計算量とかがイメージできるまで納得させることが第一。その上で、目的に応じて自分自身でデータ構造を作れるようになることが重要。

今回は自分で実装しなかったので、まだまだ腹に落ちてないな。
次回はデータ構造の続き。

Permalink | コメント(0) | トラックバック(0) | 15:41

トラックバック - http://d.hatena.ne.jp/J0__0K/20120114/1326523299

リンク元

		2012/01
日	月	火	水	木	金	土
1	2	3	4	5	6	7
8	9	10	11	12	13	14
15	16	17	18	19	20	21
22	23	24	25	26	27	28
29	30	31

J0__0Kの備忘録

2012-01-14

MIT Open course: Introduction to Algorithmsのまとめ(9～11回)