C言語でTreeMapを実装する。
はじめに
C 言語でのツリーマップ（TreeMap）の設計と実装について詳しく説明します。コードは細かく説明しています。
TreeMap とは
TreeMap とは、キーバリュー形式のデータ構造です。追加、検索、削除の計算量が O(log(n)) という特徴を持ちます。
TreeMap は二分探索木を使って実装されます。二分探索木は、各ノードにおいて、親ノードよりも小さい値を持つノードは左に、大きい値を持つノードは右に配置される木構造です。こうすることで、ルートノードから任意のノードまでの探索が O(log(n)) で行えます。
仕組み
TreeMap は、与えられたキーに対して二分木を構築し、高速なアクセスを実現します。二分木の各ノードは、左の子ノードよりも小さく、右の子ノードよりも大きい値を持ちます。二分木の高さが log(n) であるため、追加、検索、削除の計算量が O(log(n)) になります。
データ構造
TreeMap のデータ構造は以下です。
typedef struct Node Node;
struct Node {
char *key;
char *value;
Node *left;
Node *right;
};
typedef struct TreeMap TreeMap;
struct TreeMap {
Node *root;
};
Node は二分木のノードを表します。root には二分木の根が入ります。
初期化
TreeMap の初期化は以下のように実装します。
TreeMap *newTreeMap() {
TreeMap *treeMap = malloc(sizeof(TreeMap));
treeMap->root = NULL;
return treeMap;
}
root は NULL で初期化します。
追加
TreeMap にキーと値を追加する関数を以下に示します。
Node **findNode(Node **cur, const char *key) {
while (*cur) {
if (strcmp(key, (*cur)->key) > 0) {
cur = &((*cur)->right);
} else if (strcmp(key, (*cur)->key) < 0) {
cur = &((*cur)->left);
} else {
break;
}
}
return cur;
}
static Node *newNode(const char *key, const char *value) {
Node *node = malloc(sizeof(Node));
node->key = strdup(key);
node->value = strdup(value);
node->left = NULL;
node->right = NULL;
return node;
}
void insertToTreeMap(TreeMap *treemap, const char *key, const char *value) {
Node **node = findNode(&(treemap->root), key);
if (*node != NULL) {
free((*node)->value);
(*node)->value = strdup(value);
return;
}
*node = newNode(key, value);
}
追加はポインタのポインタを使って再帰を使わずに実装します。ポインタのポインタはC言語の最難関の一つですが、理解すると非常に強力なテクニックです。
検索
TreeMap からキーに対応する値を取得する関数を以下に示します。
Node *searchNode(Node *cur, const char *key) {
while (cur) {
if (strcmp(key, cur->key) > 0) {
cur = cur->right;
} else if (strcmp(key, cur->key) < 0) {
cur = cur->left;
} else {
break;
}
}
return cur;
}
char *getValueFromTreeMap(const TreeMap *treemap, const char *key) {
Node *node = searchNode(treemap->root, key);
if (node == NULL) return NULL;
return node->value;
}
検索は二分木を辿りながらキーを比較していき、一致したら値を返します。
使ってみる
TreeMap を使ってみます。
int main() {
TreeMap *treeMap = newTreeMap();
insertToTreeMap(treeMap, "key2", "value2");
insertToTreeMap(treeMap, "key1", "value1");
insertToTreeMap(treeMap, "key3", "value3");
char *s = getValueFromTreeMap(treeMap, "key1");
printf("%s\n", s); // value1
s = getValueFromTreeMap(treeMap, "key2");
printf("%s\n", s); // value2
s = getValueFromTreeMap(treeMap, "key3");
printf("%s\n", s); // value3
return 0;
}
TreeMap にキーと値を追加し、検索して値を取得します。普通に使うことができます。
最悪ケース
この実装では、最悪ケースで二分木がリストになるため、計算量が O(n) になります。最悪ケースは、キーを追加する順番が昇順または降順の場合で、以下のような入力が最悪ケースになります。
insertToTreeMap(treeMap, "key1", "value1");
insertToTreeMap(treeMap, "key2", "value2");
insertToTreeMap(treeMap, "key3", "value3");
この場合、二分木がリストになり、計算量が O(n) になります。この問題を解決するためには、平衡二分木を使う必要があります。
メモリの解放
メモリ解放を実装します。
static void freeComponents(Node *node) {
if (node == NULL) return;
free(node->key);
free(node->value);
}
static void freeNodeAndComponents(Node *node) {
if (node == NULL) return;
freeComponents(node);
free(node);
}
static void freeNode(Node *node) {
if (node == NULL) return;
freeNode(node->left);
freeNode(node->right);
freeNodeAndComponents(node);
}
void freeTreeMap(TreeMap *treemap) {
freeNode(treemap->root);
free(treemap);
}
再帰関数を利用しています。
要素の削除
要素の削除を実装します。
static Node **findMinNode(Node **cur) {
while ((*cur)->left) cur = &((*cur)->left);
return cur;
}
int removeFromTreeMap(TreeMap *treemap, const char *key) {
Node **node = findNode(&(treemap->root), key);
if (*node == NULL) return -1;
Node *tmp = *node;
if ((*node)->left == NULL) {
*node = (*node)->right;
freeNodeAndComponents(tmp);
return 0;
}
if ((*node)->right == NULL) {
*node = (*node)->left;
freeNodeAndComponents(tmp);
return 0;
}
Node **min = findMinNode(&((*node)->right));
freeComponents(*node);
(*node)->key = strdup((*min)->key);
(*node)->value = strdup((*min)->value);
Node *tmp2 = *min;
*min = (*min)->right;
freeNodeAndComponents(tmp2);
return 0;
}
要素の削除は、削除するノードが子を持たない場合、または片方の子を持つ場合、削除するノードを削除するだけです。削除するノードが両方の子を持つ場合、右の子の最小ノードを削除するノードに移動させ、右の子の最小ノードを削除します。慎重にメモリを解放する必要があります。
まとめ
C 言語で TreeMap を実装する方法について説明しました。TreeMap はキーと値を追加、検索、削除する際に O(log(n)) の計算量で高速に処理できます。ただ、今回の単純な実装では最悪ケースで O(n) になります。発展課題として、平衡二分木を使うことで最悪ケースでも O(log(n)) にすることができます。平衡二分木の実装は別で説明します。
コードは以下にあります。
Discussion