プログラミング 4 木構造とヒープ.

Presentation on theme: "プログラミング 4 木構造とヒープ."— Presentation transcript:

1 プログラミング 4 木構造とヒープ

2 木構造 データを入れたノード （node；節点）とノード を結ぶリンク（link；枝） からなる
ノードはリンクによって （複数の）子ノードを持 ち，木のような構造をし ている 木は「根」上にして書く 一番上のノードを根ノード 子のないノードを葉ノード

3 二分木 木構造は，1 つのノードが最大いくつの子ノードを持 てるかによって大別される
二分木，三分木，……，n 分木（3 以上は多分木という） この授業では特に重要な二分木（binary tree）を扱 う 以降，データとして整数を保持する二分木を扱う

4 二分探索木 二分木の中で，ノードの結び方に規則があるもののひ とつ
左の部分木には自分より小さい値，右の部分木には自 分より大きい値を持つノード 下の図では B < A < C A B C

5 二分探索木を作る 31，41，59，26，53，58，97，93 31 41

6 二分探索木を作る 31，41，59，26，53，58，97，93 31 41 59

7 二分探索木を作る 31，41，59，26，53，58，97，93 31 26 41 59

8 二分探索木を作る 31，41，59，26，53，58，97，93 31 26 41 59 53 58

9 二分探索木を作る 31，41，59，26，53，58，97，93 31 26 41 59 53 97 58 93

10 二分木の実現 ノードは構造体で作る struct node { int val; /* 値 */ struct node *left; /* 左子ノード */ struct node *right; /* 右子ノード */ }; 以降， typedef struct node Node; として話を進める 根ノードを指すポインタを root とする

11 二分探索木の探索(1) 大小関係を使って探索する（x を探索する） Node *search(int x) { Node *p = root; while (p != NULL) { if (p->val == x) return p; if (p->val > x) { p = p->left; } else { p = p->right; } } return NULL; }

12 二分探索木の探索(2) ノード数 n の二分探索 木の探索の計算量
木の高さは，二分探索木が うまく作られていれば O(log n) →探索の平均計算量は O(log n) 木がうまく作られていない 場合は木の高さは O(n) →探索の最悪計算量は O(n)

13 二分探索木の作成(1) 同じ値のノードの重複は許さないものとする
探索してノードを新しく作る場所が見つかったら生成 void addnode(int x) { Node *p, *q, *r; p = (Node *)malloc(sizeof(Node)); p->val = x; p->left = NULL; p->right = NULL; if (root == NULL) { root = p; } else { q = root; r = NULL; while (1) { r = q; if (x < r->val) { q = q->left; if (q == NULL) { r->left = p; return; } } else { q = q->right; if (q == NULL) { r->right = p; return; } } } } }

14 二分探索木の生成(2) ノード数 n の二分探索木の生成の計算量
うまく作れていれば木の高さは O(log n) →1 回のノードの追加の計算量は O(log n) これを n 回行うから，平均計算量は O(log n)×O(n) → O(n log n) うまく作れていなければ木の高さは O(n) →1 回のノードの追加の計算量は O(n) これを n 回行うから，最悪計算量は O(n)×O(n) → O(n2)

15 二分探索木をたどる 左の部分木→ノードを出力→右の部分木の順でたどれ ば昇順に出力できる void travtree(Node *p) { if (p == NULL) return; travtree(p->left); printf(“- %d ”, p->val); travtree(p->right); } 再帰呼び出しを使って記述する

16 二分木を解体する 左右の部分木を解体したあと，自身を解放する
順序に注意 void destroytree(Node *p) { if (p == NULL) return; destroytree(p->left); destroytree(p->right); free(p); return; }

17 その他の二分木の処理 ノードを数える 左の部分木のノード数＋1＋右の部分木のノード数
ノードを数える 左の部分木のノード数＋1＋右の部分木のノード数 高さを調べる 左の部分木と右の部分木の高さの高いほう＋1 葉ノードを数える 右も左も子ノードがないノードの数を数える

18 ヒープ(1) 親ノードがつねに子ノードより大きく（小さく）なら ない二分木をヒープ（heap）という ヒープは配列で実装されることが多い ？
9 8 4 7 2 1 3 6 5 ？ 9 8 4 7 3 2 1 6 5

19 ヒープ(2) ノード i について，親ノードは i/2，子ノードは i*2 および i*2+1 ？ 9 8 4 7 3 2 1 6 5 9

20 ヒープを作る ヒープの配列を a[] とし，データ数を n とする
新しく x を追加するときは，x をいったん配列の末尾に入 れて，親ノードと比較して大きかったら入れ替える void insnode(int x) { int i, j, t; n++; a[n] = x; i = n; while (i > 1) { j = i / 2; if (a[i] < a[j]) return; t = a[i]; a[i] = a[j]; a[j] = t; i = j; } return; }

21 ヒープから取り出す 根ノードを取り出すと最大値（最小値）になる
末尾のノードを根ノードに移し，ヒープを再構成する int extnode(void) { int i, j, t; a[0] = a[1]; a[1] = a[n]; n--; i = 1; while (i * 2 <= n) { j = i * 2; if (a[j] <= a[j + 1]) j++; if (a[i] < a[j]) return a[0]; t = a[i]; a[i] = a[j]; a[j] = t; i = j; } return a[0]; }

22 ヒープソート ヒープに一度データを全部追加し，順に全部取り出せ ば整列ができる→ヒープソート（heap sort）
ヒープの生成に O(n log n)，ヒープからデータを取 り出すのに O(n log n) の計算量 → O(n log n)+O(n log n) → O(n log n)