目次
「みんなのデータ構造」でプログラミングで使うデータ構造を学ぶ
「みんなのデータ構造」(Amazonリンク)とは、コンピュータ・サイエンスの基礎となるデータ構造の教科書「Open Data Structure」の日本語訳です。Introduction to Algorithmsといったアルゴリズムの名著への橋渡しになるような、実用的なテーマが丁寧に説明されています。
この本でデータ構造を学ぶ意義は、訳者まえがきで以下のように説かれています。
- ソフトウェアのほとんどはシンプルなデータ構造の組み合わせでできている。
- 「みんなのデータ構造の内容がだいたいわかれば、いいエンジニアになれる。
また、わからない部分は読み飛ばしていいとも書かれています。さらに嬉しいことに、この書籍の中でも実務や学術研究で頻繁に登場する内容がピックアップされています。
- 配列: ArrayStack・ArrayQueue・ArrayDeque
- 連結リスト: SLList(Singly-Linked List)・DLList(Doubly-Linked List)
- チェイン法を使ったハッシュテーブル: ChainedHashTable
- 二分木・二分探索木: BinaryTree、BinarySearchTree 👈 この記事
- 赤黒木: RedBlackTree
- 二分ヒープ: BinaryHeap
- ソート: MergeSort・QuickSort
- グラフの探索: 幅優先探索・深さ優先探索
書籍のサンプルコードはC++ですが、何か1つプログラミング言語を知っていれば問題なく読み進めることができます。
弁護士ドットコムでは、エンジニア有志で本書の輪読会をしています。この本の内容をマスターして、競技プログラミングに挑戦するぞ！
BinaryTree・BinarySearchTreeの感想・考察
-
要素の取得、追加、削除は のように思えるが、実施は違う
- 最悪の場合、leaf以外の全てのノードが子ノードを1つしか持たないため、実行時間は である
- BinarySearchTreeで、「値xより大きい値の中で最小の値」を で取得できる
BinaryTreeとは
二分木は、連結（connected）な有限無向グラフであり、閉路（cycle）を持たず、すべての頂点の次数（degree）が3以下の木である。これはコンピュータサイエンスで現れる基本的なデータ構造。
- rootと呼ばれる特殊なノードrを持つ（rooted）。次数は2以下
- ノードuからrに向かう1つ目のノードはuの親（parent）と呼ぶ
- uに隣接する親以外のノードを子（child）と呼ぶ
- ノードuの高さ（height）は、uからuの子孫への経路の長さの最大値
- ノードuが子を持たない場合、uは葉（leaf）という
また、木を考えるとき、外部ノード（external node）で拡張すると便利なことがある。 n >= 1 このノードを持つ二分木は、n+1個の外部ノードを持つことができる。
BinaryTree: 基本的な二分木
ノードuは、uに隣接するノードを明示的に保持するように表現する。
class BTNode {
N *left;
N *right;
N *parent;
BTNode() {
left = right = parent = NULL;
}
}rootノードのparentは常にNullである。
Node *r;ノードuの深さは、uから親を辿って根に辿り着くまでのステップ数である。
int depth(Node *u) {
int d = 0;
while (u != r) {
u = u->parent;
d++;
}
return d;
}再帰的なアルゴリズム
uを根とする二分木のノードの数（サイズ）は、左の子と右の子を再帰的に辿るステップ数に1（root自身の数）を足して求める。
int size(Node *u) {
if (u == nil) return 0;
return 1 + size(u->left) + size(u->right);
}二分木の走査
二分木を再帰的に操作するコードは下記のように書ける。traverseは「走査する」という意味。ASTを辿る場面や、デザインパターンのVisitorパターンで使われる単語。どちらも扱うデータは木構造であるため。
二分木の走査の方法は3通りある。
- 再帰で辿る
- loopで左の子から右の子へ辿る
- 幅優先探索で同じ深さのノードを左から右に辿る
void traverse(Node *u) {
if (u == nil) return;
traverse(u->left);
traverse(u->right);
}しかし、ノードが多すぎると、スタックオーバーフローを起こしてしまう。再帰を用いずにtraverseを実装する。
void traverse2() {
Node *u = r, *prev = nil, *next;
// 次に辿るnodeがないとき、u == nilになる
while (u != nil) {
if (prev == u->parent) { // 親から降りていく（下方向）
// 次に辿るノードをnextに格納する
if (u->left != nil) next = u->left;
else if (u->right != nil) next = u->right;
else next = u->parent;
} else if (prev == u->left) { // 左の子から上に登る（上方向）
// 左は走査済みなので、右の子か親にしか進まない
if (u->right != nil) next = u->right;
else next = u->parent;
} else { // 右の子から上に登る（上方向）
// 上に上がるだけ
next = u->parent;
}
prev = u;
u = next;
}
}木のサイズを計算するためには、rootからノードを下に辿っていく回数をカウントすればいい。
int size2() {
Node *u = r, *prev = nil, *next;
int n = 0;
// 次に辿るnodeがないとき、u == nilになる
while (u != nil) {
if (prev == u->parent) { // 親から降りていく（下方向）
n++;
// 次に辿るノードをnextに格納する
if (u->left != nil) next = u->left;
else if (u->right != nil) next = u->right;
else next = u->parent;
} else if (prev == u->left) { // 左の子から上に登る（上方向）
// 左は走査済みなので、右の子か親にしか進まない
if (u->right != nil) next = u->right;
else next = u->parent;
} else { // 右の子から上に登る（上方向）
// 上に上がるだけ
next = u->parent;
}
prev = u;
u = next;
}
return n;
}ListかStackを使うと、二分木でparentを使わない実装が可能。
また、別の操作方法としてキューを使った幅優先探索がある。
キューqは、初期状態は根だけを含む。各ステップでは、qから次のノードuを取り出し、u.left, u.rightを（nilでなければ）qに追加する。幅優先探索は、各深さの左から右に訪問する。
下記はDequeを使った実装。
void bfTraverse() {
ArrayDeque<Node> q;
if (r != nil) q.add(q.size(), r);
while (q.size() > 0) {
Node *u = q.remove(q.size() - 1);
if (u->left != nil) q.add(q.size(), u->left);
if (u->right != nil) q.add(q.size(), u->right);
}
}BinarySearchTree: バランスされていない二分探索木
BinarySearchTreeはSSetインターフェースの実装であって、add(x)、remove(x)、find(x)の実行時間はO(n)である。
最悪の場合、二分探索木がアンバランスであり、ほとんどのノードが子を1つだけ持ち、n個のノードからなる長い鎖のような見た目になるかもしれない。
BinarySearchTreeは、次の性質を持つ。
- ノードuについて、u.leftを根とする部分木のデータはすべてu.xより小さい
- 同様に、u.leftの部分木のデータはすべてu.xより大きい
探索 - O(n)
xの値を探す。根rからノードuを訪問している時、次の3つの場合がある。
- x < u.x なら u.leftに進む
- x > u.x なら u.rightに進む
- x = u.x なら値が x であるノード u を見つけた
また、u = nil なら探索を終了し、探している値xが木に含まれていないとする。
T findEQ(T x) {
Node *w = r;
while (w != nil) {
int comp = compare(x, w->x);
if (comp < 0) {
w = w->left;
} else if (comp > 0) {
w = w->right;
} else {
return w->x;
}
}
return null;
}x以上の値のうちで最小のものを返すためには、最後に探索したノードの値を変数zに記録しておけば良い。
T find(T x) {
Node *w = r, *z = nil;
while (w != nil) {
int comp = compare(x, w->x);
if (comp < 0) {
z = w; w = w->left;
} else if (comp > 0) {
w = w->right;
} else {
return w->x;
}
}
return z == nil ? null : z->x;}（スニペット中のハイライトは関数findEQとの差分）
追加 - O(n)
値xを追加する手順は以下の通り。
- xを検索して存在すれば、ノードを挿入しない
- xが存在しなければ、探索で最後に出会ったノードpの子とする
xをノードpの子とするとき、右の子か左の子か、p.xとの比較によって決める。
bool add(T x) {
Node *p = findLast(x);
Node *u = new Node;
u->x = x;
return addChild(p, u);
}Node* findLast(T x) {
Node *w = r, *prev = nil;
while (w != nil) {
prev = w; int comp = compare(x, w->x);
if (comp < 0) {
w = w->left;
} else if (comp > 0) {
w = w->right;
} else {
return w;
}
}
return prev;}（スニペット中のハイライトは関数findEQとの差分）
// pは最後に見つかった要素、つまりuの親
bool addChild(Node *p, Node *u) {
if (p == nil) { // r == nil、つまりn == 0のとき
r = u;
} else {
int comp = compare(u->x, p->x);
if (comp < 0) {
p->left = u;
} else if (comp > 0) {
p->right = u;
} else { // u.xはすでに木に存在している
return false;
}
u->parent = p;
}
n++;
return true;
}削除 - O(n)
ノードuの削除は3パターンある。
- uが子を持たない（uが葉（leaf））なら、uを削除する
- uが子を1つだけ持つなら、uの親と子をつなげる（u->parent->left = u->left）
- uが子を2つ持つなら、子の数が1以下のノードwで w.x >= u.x を満たす最小のwで埋める
spliceは、uが子を持たない、または子を1つだけ持つ場合に、ノードuの親と子を繋ぐ関数。spliceは英語で「継ぎ合わせる」という意味。
void splice(Node *u) {
// 削除するノードの子（またはnil）をs、親をpとする
Node *s, *p;
if (u->left == nil) {
s = u->right; // 子を持たない場合
} else {
s = u->left; // 子を1つ持つ場合
}
if (u == r) { // 削除するノードがrootである場合
r = s;
p = nil;
} else {
p = u->paretnt;
if (p->left == u) {
p->left = s; // uが親から見て左の子の場合
} else {
p->right = s; // uが親から見て右の子の場合
}
}
if (s != nil) {
s->parent = p;
}
n--;
}uが子を2つ持つパターンがややこしいが、「uを根とする部分木の右側の最小の値をuの位置に移動させる」と考えれば処理自体はシンプルである。
removeのelse以下で対応する。
void remove(Node *u) {
if (u->left == nil | u->right == nil) {
splice(u);
delete u;
} else {
// 部分木の右側の最小の値を探す
Node *w = u->right;
while (w->left != nil)
w = w->left;
u->x = w->x;
// 最小の要素を削除する
splice(w);
delete w;
}
}