[자료구조] 트라이(Trie)

트라이(Trie)

• 여러 개의 문자열을 효율적으로 저장, 탐색 및 삭제 할 수 있는 자료구조 
• Retrieval tree에서 "Trie"를 도출한 이름
• 사전 순 정렬이 자동으로 되며, 해시 충돌이 없기 때문에 해시 테이블보다 stable함
• 자동 완성(검색어 추천 기능), 사전 구현, 문자열 패턴 매칭 등에서 사용됨 

 

구조

• 트라이는 루트 노드(root node)를 가지고 있으며, 각 노드는 알파벳(혹은 문자)별로 자식 노드를 가질 수 있음
• finish(또는 isEndOfWord) 변수를 두어 문자열의 끝을 나타냄

(root)
  ├── C
  │   ├── A
  │   │   ├── T (finish=true)
  │   │   ├── N (finish=true)

 

위 예제에선 "CAT"과 "CAN"이 저장되어 있으며, T와 N 노드에서 finish를 true로 설정하여 단어가 끝난다는 표시를 함

 

연산

(1) 삽입 (Insert)

트라이에 문자열을 삽입하는 함수

void insert(const char* key) {
	if (*key == '\0') { // 문자열 끝 도달
		finish = true;
		return;
	}
	int curr = *key - 'A'; // 현재 문자 위치 계산
	if (next[curr] == NULL) // 노드가 없으면 생성
		next[curr] = new Trie();
	next[curr]->insert(key + 1); // 다음 문자로 이동
}

• 한 글자씩 탐색하며 자식 노드가 없으면 새로 추가하는 방식
• 문자열 끝에 도달하면 finish에 true를 주어 단어가 끝났다는 표시를 함

 

(2) 탐색 (Find/Search)

 

트라이에서 특정 문자열이 존재하는지 확인하는 함수

Trie* find(const char* key) {
    if (*key == '\0') return this; // 문자열 끝이면 현재 노드 반환
    int curr = *key - 'A';
    if (next[curr] == NULL) return NULL; // 존재하지 않는 경우 NULL 반환
    return next[curr]->find(key + 1); // 다음 문자 탐색
}

• 문자열 끝이면 현재 노드의 포인터 값을 반환하여 특정 문자열이 존재함을 알림
• 존재하지 않는 경우 NULL 반환 

(3) 삭제 (Delete)

트라이에서 특정 문자열을 삭제하는 함수

void remove(const char* key) {
    if (*key == '\0') {
        finish = false; // 단어 끝 표시 해제
        return;
    }
    int curr = *key - 'A';
    if (next[curr] != NULL)
        next[curr]->remove(key + 1);
}

• 단어 끝 표시(finish)를 해제하여 단어를 삭제

다음과 같이 재귀적으로 하위 노드를 탐색하면 필요없는 노드를 삭제함으로써 메모리를 아낄 수 있음 

bool remove(const char* key) {
    if (*key == '\0') { // 문자열 끝 도달
        if (!finish) return false; // 단어가 존재하지 않음
        finish = false; // 단어 끝 표시 해제
        return isEmpty(); // 현재 노드가 비었는지 반환
    }
    int curr = *key - 'A';
    if (next[curr] == NULL) return false; // 해당 문자가 없으면 삭제 불가능
    
    bool shouldDelete = next[curr]->remove(key + 1);
    if (shouldDelete) { // 자식 노드가 필요 없다면 삭제
        delete next[curr];
        next[curr] = NULL;
    }
    return isEmpty() && !finish;
}

bool isEmpty() {
    for (int i = 0; i < 26; i++) {
        if (next[i] != NULL) return false;
    }
    return true;
}

 

 

코드

struct Trie {
	bool finish;  // 단어의 끝 여부
	Trie* next[26]; // 알파벳(a-z) 저장을 위한 배열

	Trie() : finish(false) {
		memset(next, 0, sizeof(next)); // 모든 포인터를 NULL로 초기화
	}

	void insert(const char* key) {
		if (*key == '\0') { // 문자열 끝 도달
			finish = true;
			return;
		}
		int curr = *key - 'A'; // 현재 문자 위치 계산
		if (next[curr] == NULL) // 노드가 없으면 생성
			next[curr] = new Trie();
		next[curr]->insert(key + 1); // 다음 문자로 이동
	}

	Trie* find(const char* key) {
		if (*key == '\0') return this; // 문자열 끝이면 현재 노드 반환
		int curr = *key - 'A';
		if (next[curr] == NULL) return NULL; // 존재하지 않는 경우 NULL 반환
		return next[curr]->find(key + 1); // 다음 문자 탐색
	}

	void remove(const char* key) {
		if (*key == '\0') {
			finish = false; // 단어 끝 표시 해제
			return;
		}
		int curr = *key - 'A';
		if (next[curr] != NULL)
			next[curr]->remove(key + 1);
	}
};

 

 

시간 복잡도

문자열 길이를 기준으로 문자열 길이를 L이라 했을 때 삽입, 탐색, 삭제 모두 O(L) 만에 가능하다.

 

공간 복잡도

최종 메모리는 O(포인터 크기 * 포인터 배열 개수 * 총 노드의 수)가 되며 총 노드의 수가 저장된 문자열 길이에 비례하므로 문자열 길이(L)에 비례한다.