TRIE (동적 메모리로 구현)

이번에는 TRIE를 동적 메모리를 이용하여 만들어 보겠습니다.

C++언어를 이용한 방법은 다른곳에서 쉬게 찾을 수 있으므로 여기에서는 C언어를 이용한 구현 코드를 소개합니다.

정적 메모리로 구현한 코드와 큰 차이는 없으며, 다만 메모리 해제하는 부분을 주의 깊게 봐야합니다. C++ 언어에서 클래스의 소멸자를 쓰면 되지만 순수하게  C언어 문법으로 구현한 부분이라 DFS 순회를 통한 메모리 해제를 하도록 구현 하였습니다.

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

#define ALPHA 26

typedef struct trie_type_s{
	struct trie_type_s *child[ALPHA];
	int done;
}trie_type;

trie_type trie;

void dfs_free(trie_type *node)
{
	int i;
	trie_type *cur_node = node;
	trie_type *child_node;
	for(i=0;i<ALPHA;i++){
		child_node = cur_node->child[i];
		if( child_node != 0 ){
			dfs_free(child_node);
		}
	}
	if( &trie==cur_node ){
		for(i=0;i<ALPHA;i++){
			cur_node->child[i] = 0;
		}
		cur_node->done = 0;
	}else{
		free(cur_node);
	}
}

int init()
{
	dfs_free(&trie);
	return 0;
}

void trie_insert(const char data[])
{
	int i;
	trie_type *cur_node = &trie;
	trie_type *next_node;
	for(i=0;;i++){
		if (data[i]==0) break;
		
		next_node = cur_node->child[data[i]-'a'];
		if( next_node == 0 ){
			// empty child need to add
			trie_type *new_node = (trie_type *)malloc(sizeof(trie_type));
			cur_node->child[data[i]-'a'] = new_node;
			for(int j=0;j<ALPHA;j++){
				new_node->child[j]=0;
			}
			new_node->done = 0;
			cur_node = new_node;
		}else{
			cur_node = next_node;
		}
	}
	if(cur_node!=&trie){
		// string end
		cur_node->done = 1;
	}
}

int trie_search(const char data[])
{
	int i;
	trie_type *cur_node = &trie;
	trie_type *next_node;
	for(i=0;;i++){
		if (data[i]==0) break;
		
		next_node = cur_node->child[data[i]-'a'];
		if( next_node == 0 ){
			// empty child 
			return 0;
		}else{
			cur_node = next_node;
		}
	}
	if(cur_node!=&trie){
		if (cur_node->done==1) return 1;
	}
	return 0;
}

int main()
{
	init();
	trie_insert("abc");
	trie_insert("ksg");
	trie_insert("abefg");
	trie_insert("tg");
	
	printf("%d\n",trie_search("abf"));//0
	printf("%d\n",trie_search("ksg"));//1
	printf("%d\n",trie_search("abdfg"));//0
	printf("%d\n",trie_search("abefg"));//1
	printf("%d\n",trie_search("ab"));//0
	
	init();
	trie_insert("abcadfae");
	trie_insert("ksasdfg");
	trie_insert("abadfefg");
	trie_insert("tgadf");
	
	printf("%d\n",trie_search("abf"));//0
	printf("%d\n",trie_search("ksasdfg"));//1
	printf("%d\n",trie_search("abdfg"));//0
	printf("%d\n",trie_search("abadfefg"));//1
	printf("%d\n",trie_search("ab"));//0
	
	init();
}

코드 설명

dfs_free 함수에서는 자식들이 있는지 먼저 확인한뒤 재귀 호출로 자식들의 메모리 해제를 요청하게 됩니다.

	for(i=0;i<ALPHA;i++){
		child_node = cur_node->child[i];
		if( child_node != 0 ){
			dfs_free(child_node);
		}
	}

현재 노드의 메모리는 다음 줄에서 해제가 됩니다.

	if( &trie==cur_node ){
		for(i=0;i<ALPHA;i++){
			cur_node->child[i] = 0;
		}
		cur_node->done = 0;
	}else{
		free(cur_node);
	}

최상위 노드는 root node로 해제를 하지 않습니다. 다만 자식들을 가리키고 있던 포인터만 초기화 합니다.

최상위 노드가 아니라면 실제 메모리를 해제하고 return하게 됩니다.