「みんなのデータ構造」でプログラミングで使うデータ構造を学ぶ

「みんなのデータ構造」(Amazonリンク)とは、コンピュータ・サイエンスの基礎となるデータ構造の教科書「Open Data Structure」の日本語訳です。Introduction to Algorithmsといったアルゴリズムの名著への橋渡しになるような、実用的なテーマが丁寧に説明されています。

この本でデータ構造を学ぶ意義は、訳者まえがきで以下のように説かれています。

1. ソフトウェアのほとんどはシンプルなデータ構造の組み合わせでできている。
2. 「みんなのデータ構造の内容がだいたいわかれば、いいエンジニアになれる。

また、わからない部分は読み飛ばしていいとも書かれています。さらに嬉しいことに、この書籍の中でも実務や学術研究で頻繁に登場する内容がピックアップされています。

• 配列: ArrayStack・ArrayQueue・ArrayDeque
• 連結リスト: SLList(Singly-Linked List)・DLList(Doubly-Linked List)
• チェイン法を使ったハッシュテーブル: ChainedHashTable
• 二分木・二分探索木: BinaryTree・BinarySearchTree
• 赤黒木: RedBlackTree
• 二分ヒープ: BinaryHeap 👈 この記事
• ソート: MergeSort・QuickSort
• グラフの探索: 幅優先探索・深さ優先探索

書籍のサンプルコードはC++ですが、何か1つプログラミング言語を知っていれば問題なく読み進めることができます。

ヒープ

BinaryHeapは、優先度付きキューの実装方法の1つである。ヒープは特殊な二分木であり、「雑多に積まれたもの」という意味がある。高度に構造化された二分探索木とは対象である。

BinaryHeapは完全二分木をシミュレートするのに配列を使う。このヒープを使って整列アルゴリズムであるヒープソートを実装できる。ヒープソートは、ソートアルゴリズムの中でも最速なもののひとつである。

BinaryHeap: 二分木を間接的に表現する

BinaryHeapは、優先度付きキューのインターフェースを実装する。BinaryHeapはadd(x)とremove()をサポートする。resize()のコストを無視すると、いずれの操作の実行時間も $O(\log n)$ である。

根は配列の添字0、左の子は添字1、右の子は添字2という具合に、木のノードを幅優先順に配列に入れていくことで、完全二分木を表現できる。

そして、木と配列の関係には法則性があり、添字iに対して以下のような関係が成り立つ。

int left(int i) {
	return 2*i + 1;
}
int right(int i) {
	return  2*i + 2;
}
int parent(int i) {
	return  (i-1)/2;
}

対象のノードの添字がわかれば、上記の計算方法で左の子、右の子、親のindexを求めることができる。

BinaryHeapではn個の要素を配列aに格納する。

array<T> a;
int n;

add(x) - $O(\log n)$ 以下

add(x)の実装は簡単。他の配列ベースのデータ構造と同じく、a.length = nかを確認して、そうであればresize()（拡張）する。そして、xをa[n]に入れ、nを1増やす。あとは、xとその親を交換する操作をxが親以上になるまで再帰的に実行することで、ヒープ性を保てば良い。

bool add(T x) {
	if (n + 1 > a.length) resize();
	a[n] = x;
	n++;
	bubbleUp(n-1);
	return true;
}
void bubbleUp(int i) {
	int p = parent(i);
	while (i > 0 && compare(a[i], a[p]) < 0) {
		a.swap(i, p);
		i = p;
		p = parent(i);
	}
}

remove() - $O(\log n)$ 以下

remove()はヒープから最小の値を削除する。最小値は根の値である。

最小値を削除する簡単な方法は、根とa[n-1]を交換し、交換後にa[n-1]にある値（根の値）を削除して、nを1小さくする。次に、ヒープ性を保持するためには、a[0]にある値が隣接するノードの中で最小の値であることが必要である。このため、左右の子と値を比べて、もしa[0]の値が大きいのであればこれをした方向に動かしていく必要がある。

そして、新しくねとなった要素を2つのこと比較し、新しくねとなった要素の値が3つのうちで最小ならば処理を終了する。そうでないなら、2つの子のうち小さいものと入れ替え、同様の処理を繰り返す。

T remove() {
	T x = a[0];
	n--;
	a[0] = a[n];
	trickleDown(0);
	if (3*n < a.length) resize();
	return x;
}
void trickleDown(int i) {
	while (i >= 0) {
		int j = -1; // この関数内でiとjの場所を交換する
		int r = right(i);
		if (r < n && compare(a[r], a[i]) < 0) { // 右の子よりa[i]が大きい場合
			int l = left(i);
			if (compare(a[l], a[r]) < 0) { // 左の子と右の子を比べる
				j = l; // 左の子の方が小さいとき
			} else {
				j = r; // 右の子の方が小さいとき
			}
		} else {
			int l = left(i);
			if (l < n && compare(a[l], a[i]) < 0) {
				j = l;
			}
		}
		if (j >= 0) a.swap(i, j);
		i = j;
	}
}

add(x)、remove()の実行時間が $O(\log n)$ であるのには以下のような理由である。BinaryHeapは完全二分木であるので、木の高さをhとすると、少なくとも2^h個のノードがあるので、n >= 2^hが成り立つ。この両辺の対数を取ると、次の式が成り立つ。

$$h <= \log n$$

「みんなのデータ構造」でプログラミングで使うデータ構造を学ぶ

「みんなのデータ構造」(Amazonリンク)とは、コンピュータ・サイエンスの基礎となるデータ構造の教科書「Open Data Structure」の日本語訳です。Introduction to Algorithmsといったアルゴリズムの名著への橋渡しになるような、実用的なテーマが丁寧に説明されています。

この本でデータ構造を学ぶ意義は、訳者まえがきで以下のように説かれています。

1. ソフトウェアのほとんどはシンプルなデータ構造の組み合わせでできている。
2. 「みんなのデータ構造の内容がだいたいわかれば、いいエンジニアになれる。

また、わからない部分は読み飛ばしていいとも書かれています。さらに嬉しいことに、この書籍の中でも実務や学術研究で頻繁に登場する内容がピックアップされています。

• 配列: ArrayStack・ArrayQueue・ArrayDeque
• 連結リスト: SLList(Singly-Linked List)・DLList(Doubly-Linked List)
• チェイン法を使ったハッシュテーブル: ChainedHashTable
• 二分木・二分探索木: BinaryTree・BinarySearchTree
• 赤黒木: RedBlackTree 👈 この記事
• 二分ヒープ: BinaryHeap
• ソート: MergeSort・QuickSort
• グラフの探索: 幅優先探索・深さ優先探索

書籍のサンプルコードはC++ですが、何か1つプログラミング言語を知っていれば問題なく読み進めることができます。

RedBlackTree

赤黒木（red-black tree）は、木の高さが要素数の対数で抑えられる二分木である。赤黒木の性質は以下の通りである。

1. n個の要素を含む赤黒木の高さは $2\log n$ 以下である
2. add(x)およびremove(x)を最悪の場合でも $O(\log n)$ の時間で実行できる
3. add(x)およびremove(x)における回転の回数は、償却すると定数である

赤黒木は優れた性質を持つが、実装が複雑である。赤黒木を理解するために、まずは背景知識として2-4木を知る必要がある。

2-4木

2-4木の性質は以下である。

1. [高さ] 全ての葉の深さは等しい
2. [次数] 全ての内部ノードは2個以上4個以下の子ノードを持つ

また、n個の葉を持つ2-4木の高さは $\log n$ 以下である。

葉の追加 （$\log n$ 以下）

2-4木に葉を追加するのは簡単。親ノードwの子として葉uを追加したい時は、まず追加をする。その後、次数の制約に沿って処理を行う。wが4つの子を持っていれば、wを分割して子を2つ持つノードwと子を3つ持つノードw’とする。このとき、w’の親はwの親とする。そして、この処理を再帰的に繰り返す。

2-4木の高さは常に $\log n$ 以下なので、葉の追加は $\log n$ ステップ以下で完了する。

葉の削除 （$\log n$ 以下）

2-4木から葉を削除するためには、まず親wから葉uを削除する。そして、wの子が1つだけになれば、次数の制約を満たさなくなるので、修正の処理を加える。

つまり、wの兄弟w’を調べて、w’の子が3つまたは4つなら、そのうち1つをw’からwに移す。w’の子が2つなら、wとw’を併合して、子を3つ持つノードwとする。そして、w’をw’の親から取り除く。

この処理は自分自身w、もしくは兄弟w’が子を３つ以上持つようなノードuが見つかるか、根に到達したら終了する。

2-4木の高さは常に $\log n$ 以下なので、葉の削除も追加と同様に $\log n$ ステップ以下で完了する。

RedBlackTree: 2-4木をシミュレートする二分木

赤黒木は、各ノードuが赤か黒の色を持つ二分探索木である。赤ノードは0で、黒ノードは1で表現される。赤黒木の性質は以下である。

1. 葉から根への経路には、いずれも黒ノードが同じ数だけ含まれる。（黒の高さの性質。葉から根への経路について、色の総和は全て等しい）
2. 赤ノード同士は隣接しない（赤の辺の性質。赤の辺はないということ。根でない任意のノードuについて、 u.color + u.parent.color >= 1が成り立つ）

これらの性質は、根rがどちらの色であっても満たされる。以下では、根が黒であると仮定する。また、赤黒木を更新するアルゴリズムでは、根は黒のまま保たれるとする。なお、外部ノード(nil)は黒ノードとして扱う。

class RedBlackNode : public BSTNode<Node, T> {
	friend class RedBlackTree<Node, T>;
	char color;
}

int red = 0;
int black = 1;

赤黒木と2-4木

赤黒木は2-4木を二分木として効率的にシミュレートするように設計されている。

例えば、赤黒木Tに対して「全ての赤ノードを取り除き、uの2つの子を両方ともuの親（黒ノード）に接続する」という操作を実行すると、T’は黒ノードだけを持つ2-4木になるのである。

2-4木T’はn+1個の葉を持ち、各葉は赤黒木のn+1個の外部ノードと対応する。よって、この木の高さは $\log (n+1)$ 以下である。

黒ノードのみを持つ2-4木T’の高さは $\log (n+1)$ 以下なので、赤黒木Tの黒ノードの個数は $\log (n+1)$ 以下である。また、2つの内部ノードのうち、赤は1追加なので、赤ノードの個数は $\log (n+1) - 1$ 以下である。よって、n>=1について、根から任意の内部ノードへの経路のうちで最長のものの長さは、次の左辺の値以下である

$$2\log n+1 - 2 <= 2\log n$$

このことから、赤黒木の最も重要な性質を示せる。

3. n個のノードからなる赤黒木の高さは $2\log n$ 以下である

「みんなのデータ構造」でプログラミングで使うデータ構造を学ぶ

「みんなのデータ構造」(Amazonリンク)とは、コンピュータ・サイエンスの基礎となるデータ構造の教科書「Open Data Structure」の日本語訳です。Introduction to Algorithmsといったアルゴリズムの名著への橋渡しになるような、実用的なテーマが丁寧に説明されています。

この本でデータ構造を学ぶ意義は、訳者まえがきで以下のように説かれています。

1. ソフトウェアのほとんどはシンプルなデータ構造の組み合わせでできている。
2. 「みんなのデータ構造の内容がだいたいわかれば、いいエンジニアになれる。

また、わからない部分は読み飛ばしていいとも書かれています。さらに嬉しいことに、この書籍の中でも実務や学術研究で頻繁に登場する内容がピックアップされています。

• 配列: ArrayStack・ArrayQueue・ArrayDeque 👈 この記事
• 連結リスト: SLList(Singly-Linked List)・DLList(Doubly-Linked List)
• チェイン法を使ったハッシュテーブル: ChainedHashTable
• 二分木・二分探索木: BinaryTree・BinarySearchTree
• 赤黒木: RedBlackTree
• 二分ヒープ: BinaryHeap
• ソート: MergeSort・QuickSort
• グラフの探索: 幅優先探索・深さ優先探索

書籍のサンプルコードはC++ですが、何か1つプログラミング言語を知っていれば問題なく読み進めることができます。

この記事は、「ArrayStack、ArrayQueue、ArrayDeque」のまとめです。

関連記事

• SLList・DLList まとめ
• ChainedHashTable まとめ
• BinaryTree・BinarySearchTree まとめ

ArrayStack・ArrayQueue・ArrayDequeの感想・考察

• Stackはレジスタで使われるデータ構造。皿の積み重ねによく例えられる
• Queueはジョブの処理で使うデータ構造。店の行列によく例えられる
• 配列のresizeは隠れたコスト
• 要素をたくさん持つ配列の途中に要素の追加、削除をすると、計算量はO(1)ではなくO(1 + min{i, n-i})になるので、その際は別のデータ構造を使う方がベター（例えば後述のLinked-List）
• Rustで固定長の配列と可変長の配列が区別されていたのは、配列操作の計算量も関係あるんだな（動的言語ばかりやってると、固定長配列を意識できない）
• modである長さの中でindexを循環させるという発想は使えそう
• Dequeは幅優先探索、深さ優先探索で使えるので、基礎を知れてよかった。競技プログラミングではDequeを使えればStackやQueueとして扱える

コンピュータ・サイエンスの基礎を学びたい方や、競技プログラミングにチャレンジする方に「みんなのデータ構造」(Amazonリンク)はおすすめです。

Stack、Queueと言えば、会社の先輩が**「仕事で差し込みの案件をStackとして積んでいくと、最初のタスク完了までに時間がかかる。すると、先に進んでるかわからなくなってしまう。そんな時は差し込みタスクをQueueとしてFIFOで処理すると前進している実感が湧く」**と話していたのを思い出します。

配列を使ったリスト

ArrayStack: 配列を使った高速なスタック操作

ArrayStackは backing array を使ったListインターフェースを実装。

array<T> a;
int n;
int size() {
	return n;
}

get(i)/set(i, x) - O(1)

T get(int i) {
	return a[i];
}

T set(int i, T x) {
	T y = a[i];
	a[i] = x;
	return y;
}

add(i, x)/ remove(i) - O(1 + n - i)

addは、インデックスiの位置にxを追加する。

void add(int i, T x) {
	if (n + 1 > a.length) resize();
	for (int j = n; j > i; j--)
		a[j] = a[j - 1];

	a[i] = x;
	n++;
}

removeは、インデックスiの要素を削除する。

T remove(int i) {
	T x = a[i];
	for (int j = i; j < n - 1; j++)
		a[j] = a[j + 1];
	n--;
	if (a.length >= 3 * n) resize();
	return x;
}

空のArrayStackに対して、任意のm個のadd(i, x)およびremove(i)からなる操作の列を実行する。この時、resize()にかかる時間の合計はO(m)である。

void resize() {
	array<T> b(max(2 * n, 1));
	for (int i = 0; i < n; i++)
		b[i] = a[i];
	a = b;
}

resize()の実行にはO(n)の時間がかかる。

ArrayQueue: 配列を使ったキュー

ArrayQueueは、FIFO（先入れ先出し）キューを実装するデータ構造。

ArrayQueueは、FIFOのQueueインターフェースの実装である。resize()のコストを無視すると、ArrayQueueはadd(x)、remove()の実行時間はO(1)である。さらに、空のArrayQueueに対して長さmのadd(i, x)およびremove(i)からなる操作の列を実行するとき、resize()にかかる時間の合計はO(m)である。

jはqueueの先頭の位置。

array<T> a;
int j;
int n;

add(i, x)/ remove(i) - O(1)

FIFOなので、addは末尾に要素を追加する。

bool add(T x) {
	if (n+1 >= a.length) resize();
	a[(j+n) % a.length] = x;
	n++;
	return true;
}

removeは先頭の要素を削除する。

T remove() {
	T x = a[j]
	j = (j+1) % a.length;
	n--;
	if (a.length >= 3 * n) resize();
	return x;
}

resize()はArrayStackの実装に似ている。ただ、queueの先頭のインデックスjは0ではない点が異なる。

void resize() {
	array<T> b(max(2 * n, 1));
	for (int k = 0; k < n; k++)
		b[k] = a[(j+k) % a.length];
	a = b;
	j = 0;
}

ArrayDeque: 配列を使った高速な双方向キュー

Dequeは両端に対して追加と削除が効率的に実行できるデータ構造である。

ArrayDequeはListインターフェースを実装する。

• get(i)およびset(i, x)の実行時間はO(1)である
• add(i, x)およびremove(i)の実行時間はO(1 + min{i, n-i})である

array<T> a;
int j;
int n;

get(i)/set(i, x) - O(1)

get(i)、set(i, x)はシンプル。

T get(int i) {
	return a[(j+i) % a.length];
}

T set(int i, T x) {
	int k = (j+i) % a.length;
	T y = a[k];
	a[k] = x;
	return y;
}

add(i, x)/ remove(i) - O(1 + min{i, n - i})

add、removeは、i個の要素を左に、またはn-i個の要素を右にずらす。

resize()を無視すれば、計算量はO(1 + min{i, n - i})である。

void add(int i, T x) {
	if (n+1 >= a.length) resize();

	// a[0],...,a[i-1] を左に1つずつずらす
	if (i < n/2) {
		// jが0なら、indexが-1になってしまうため
		j = (j == 0) ? a.length - 1 : j - 1;
		for (int k = 0; k <= i-1; k++)
			a[(j+k) % a.length] = a[(j+k+1) % a.length];
	} else {
		// a[i],...a[n-1] を右に1つずつずらす
		for (int k = n; k > i; k--)
			a[(j+k) % a.length] = a[(j+k-1) % a.length];
	}

	a[(j+i) % a.length] = x;
	n++;
}

removeもaddと同様に実装できる。

T remove(int i) {
	T x = a[(j+i) % a.length];

	if (i < n/2) {
		for (int k = i; k > 0; k--)
			a[(j+k) % a.length] = a[(j+k-1) % a.length];
	} else {
		for (int k = i; k < n-1; k++)
			a[(j+k) % a.length] = a[(j+k+1) % a.length];
	}

	n--;
	if (3*n > a.length) resize();
	return x;
}

「みんなのデータ構造」でプログラミングで使うデータ構造を学ぶ

「みんなのデータ構造」(Amazonリンク)とは、コンピュータ・サイエンスの基礎となるデータ構造の教科書「Open Data Structure」の日本語訳です。Introduction to Algorithmsといったアルゴリズムの名著への橋渡しになるような、実用的なテーマが丁寧に説明されています。

この本でデータ構造を学ぶ意義は、訳者まえがきで以下のように説かれています。

1. ソフトウェアのほとんどはシンプルなデータ構造の組み合わせでできている。
2. 「みんなのデータ構造の内容がだいたいわかれば、いいエンジニアになれる。

また、わからない部分は読み飛ばしていいとも書かれています。さらに嬉しいことに、この書籍の中でも実務や学術研究で頻繁に登場する内容がピックアップされています。

• 配列: ArrayStack・ArrayQueue・ArrayDeque
• 連結リスト: SLList(Singly-Linked List)・DLList(Doubly-Linked List)
• チェイン法を使ったハッシュテーブル: ChainedHashTable
• 二分木・二分探索木: BinaryTree、BinarySearchTree 👈 この記事
• 赤黒木: RedBlackTree
• 二分ヒープ: BinaryHeap
• ソート: MergeSort・QuickSort
• グラフの探索: 幅優先探索・深さ優先探索

書籍のサンプルコードはC++ですが、何か1つプログラミング言語を知っていれば問題なく読み進めることができます。

BinaryTree・BinarySearchTreeの感想・考察

• 要素の取得、追加、削除は $O(\log n)$ のように思えるが、実施は違う
  • 最悪の場合、leaf以外の全てのノードが子ノードを1つしか持たないため、実行時間は $O(n)$ である
• BinarySearchTreeで、「値xより大きい値の中で最小の値」を $O(n)$ で取得できる

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つの場合がある。

1. x < u.x なら u.leftに進む
2. x > u.x なら u.rightに進む
3. 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を追加する手順は以下の通り。

1. xを検索して存在すれば、ノードを挿入しない
2. 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パターンある。

1. uが子を持たない（uが葉（leaf））なら、uを削除する
2. uが子を1つだけ持つなら、uの親と子をつなげる（u->parent->left = u->left）
3. 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;
	}
}

「みんなのデータ構造」でプログラミングで使うデータ構造を学ぶ

「みんなのデータ構造」(Amazonリンク)とは、コンピュータ・サイエンスの基礎となるデータ構造の教科書「Open Data Structure」の日本語訳です。Introduction to Algorithmsといったアルゴリズムの名著への橋渡しになるような、実用的なテーマが丁寧に説明されています。

この本でデータ構造を学ぶ意義は、訳者まえがきで以下のように説かれています。

1. ソフトウェアのほとんどはシンプルなデータ構造の組み合わせでできている。
2. 「みんなのデータ構造の内容がだいたいわかれば、いいエンジニアになれる。

また、わからない部分は読み飛ばしていいとも書かれています。さらに嬉しいことに、この書籍の中でも実務や学術研究で頻繁に登場する内容がピックアップされています。

• 配列: ArrayStack・ArrayQueue・ArrayDeque
• 連結リスト: SLList(Singly-Linked List)・DLList(Doubly-Linked List)
• チェイン法を使ったハッシュテーブル: ChainedHashTable 👈 この記事
• 二分木・二分探索木: BinaryTree・BinarySearchTree
• 赤黒木: RedBlackTree
• 二分ヒープ: BinaryHeap
• ソート: MergeSort・QuickSort
• グラフの探索: 幅優先探索・深さ優先探索

書籍のサンプルコードはC++ですが、何か1つプログラミング言語を知っていれば問題なく読み進めることができます。

この記事は、「ArrayStack、ArrayQueue、ArrayDeque」のまとめです。

ChainedHashTableの感想・考察

• Hashという単語は「不可逆的な潰し方をする」イメージ（ex. ハッシュドポテトはジャガイモを潰して揚げる料理）
  • ある値をHash関数で別の値に変換する
• Hash関数の性能が優れていると、追加、取得、削除はO(1)になる。
  • 逆に、性能が悪いと最悪O(n)になりうる
  • このため、効率的なHash関数について研究がされている
• Mapはキーとバリューが1対1に対応するデータ構造
  • MapとChainedHashTableの関係は、ChainedHashTableはMap（USetインターフェース）の実装方法の1つ
  • 実際、JavaのChainedHashtableクラスはMapインターフェースを実装している

コンピュータ・サイエンスの基礎を学びたい方や、競技プログラミングにチャレンジする方に「みんなのデータ構造」(Amazonリンク)はおすすめです。

ChainedHashTableの定理

ChainedHashTableはUSetインターフェースを実装する。resize()のコストを無視すると、ChainedHashTableにおけるadd(x)、remove(x)、find(x)の期待実行時間はO(1)である。

array<List> t;
int n;

• xのハッシュ値はhash(x)
• リストt[i]は n <= t.length を満たす

add - O(1)

xをリストt[i]に追加する。

bool add(T x) {
  // 同じ値があったらfalseを返す
  if (find(x) != null) return false;
  // リストが満杯だったらリストをresizeする
  if (n+1 > t.length) resize();

  t[hash(x)].add(x);
  n++;
  return true;
}

remove - $O(n_{hash(x)})$

要素の削除。リストの長さをt[i]とすると計算量は$O(n_{hash(x)})$である。

T remove(T x) {
  int j = hash(x);

  for (int i = 0; i < t[j].size(); i++) {
  	T y = t[j].get(i);
  	if (x == y) {
  		t[j].remove(i);
  		n--;
  		return y;
  	}
  }

  return null;
}

find - $O(n_{hash(x)})$

t[hash(x)]を線形に探索する。

T find(T x) {
	int j = hash(x);

	for (int i = 0; i < t[j].size(); i++) {
		if (x == t[j].get(i)) {
			return t[j].get(i);
		}
	}

	return null;
}

計算量

優れたhash関数は、ハッシュテーブルの計算量をO(n/t.length) = O(1)にする。