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

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

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

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

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

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

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

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

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

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

二分探索木の探索(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; }

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

二分探索木の作成(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; } } } } }

二分探索木の生成(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)

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

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

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

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

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

ヒープを作る ヒープの配列を 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; }

ヒープから取り出す 根ノードを取り出すと最大値（最小値）になる 末尾のノードを根ノードに移し，ヒープを再構成する 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]; }

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