Trie 트라이

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

#define ARRAY_SIZE(a) sizeof(a)/sizeof(a[0])
#define ALPHABET_SIZE 26
#define CHAR_TO_INDEX(c) ((int)c - (int)'a')

typedef struct trie_node trie_node_t;
struct trie_node {
	int value;	// 끝나는지 안 끝나는지
	trie_node_t *children[ALPHABET_SIZE];
};

typedef struct trie trie_t;
struct trie{
	trie_node_t *root;	// root는 빈 노드
	int count;
};

// 모두 NULL로 초기화되어있는 새로운 trie node 반환
trie_node_t *getNode(void) {
	trie_node_t *pNode = NULL;
	pNode = (trie_node_t *)malloc(sizeof(trie_node_t));
	if (pNode) {
		int i;
		pNode->value = 0;
		for (int i = 0; i < ALPHABET_SIZE; i++) {
			pNode->children[i] = NULL;
		}
	}
	return pNode;
}

// 트라이 초기화
void init(trie_t *pTrie) {
	pTrie->root = getNode();
	pTrie->count = 0;
}

// 원래 없던 경우는 만들어짐
// 이미 있던 경우는 leaf node 체크가 됨
// ex) "BET"가 있는데 "BE"가 들어오는 경우
void insert(trie_t *pTrie, char key[]) {	// key는 문자열
	int level;
	int length = strlen(key);
	int index;
	trie_node_t *pCrawl;

	pTrie->count++;
	pCrawl = pTrie->root;

	for (level = 0; level < length; level++) {
		index = CHAR_TO_INDEX(key[level]);
		if (!pCrawl->children[index]) {
			pCrawl->children[index] = getNode();
		}
		pCrawl = pCrawl->children[index];
	}
	// 들어온 key 값의 마지막 단어에는 끝이라는 표시를 위해
	pCrawl->value = pTrie->count;
}

// 없으면 0반환
int search(trie_t *pTrie, const char key[]) {
	int level;
	int length = strlen(key);
	int index;
	trie_node_t *pCrawl;
	pCrawl = pTrie->root;

	for (level = 0; level < length; level++) {
		index = CHAR_TO_INDEX(key[level]);
		if (!pCrawl->children[index]) {
			return 0;
		}
		pCrawl = pCrawl->children[index];
	}
	return (0 != pCrawl && pCrawl->value);
}

int main() {
	
	char keys[][8] = { "the", "a", "there", "answer", "any", "by", "bye", "their" };
	trie_t trie;

	char output[][32] = { "Not present in trie", "Present in trie" };

	init(&trie);

	for (int i = 0; i < ARRAY_SIZE(keys); i++) {
		insert(&trie, keys[i]);
	}

	printf("%s --- %s\n", "the", output[search(&trie, "the")]);
	printf("%s --- %s\n", "these", output[search(&trie, "these")]);
	printf("%s --- %s\n", "their", output[search(&trie, "their")]);
	printf("%s --- %s\n", "thaw", output[search(&trie, "thaw")]);

	return 0;
}