[Algorithm - Concept] 트라이 알고리즘 (Trie Algorithm)

[Algorithm - Concept] 트라이 알고리즘 (Trie Algorithm)

---

https://hackernoon.com/practical-data-structures-for-frontend-applications-when-to-use-tries-5428a565eba4

 

In computer science, a trie, also called digital tree, radix tree or prefix tree, is a kind of search tree—an ordered tree data structure used to store a dynamic set or associative array where the keys are usually strings. Unlike a binary search tree, no node in the tree stores the key associated with that node; instead, its position in the tree defines the key with which it is associated. All the descendants of a node have a common prefix of the string associated with that node, and the root is associated with the empty string. Keys tend to be associated with leaves, though some inner nodes may correspond to keys of interest. Hence, keys are not necessarily associated with every node.

 

컴퓨터 과학에서 디지털 트리, 기수 트리 또는 접두사 트리라고도하는 트리는 일종의 검색 트리로, 키가 일반적으로 문자열 인 동적 세트 ​​또는 연관 배열을 저장하는 데 사용되는 정렬 트리 데이터 구조입니다. 이진 검색 트리와 달리 트리의 노드는 해당 노드와 관련된 키를 저장하지 않습니다. 대신 트리에서의 위치는 연관된 키를 정의합니다. 노드의 모든 하위 항목에는 해당 노드와 연관된 문자열의 공통 접두사가 있으며 루트는 빈 문자열과 연관됩니다. 일부 내부 노드는 트리의 계층과 연관이 있는 키에 해당 할 수 있지만 키는 단말 노드와 연관되는 경향이 있습니다. 따라서 키가 반드시 모든 노드와 연관 될 필요는 없습니다.

 

💊 알고리즘 복잡도 (Algorithm Complcomplexity)

⏰ 시간 복잡도 (Time Complcomplexity)	O(M)
📦 공간 복잡도 (Space Complcomplexity)	O(N*M)

---

📄 [Algorithm] Trie Algorithm C++ Source Code

#define MAX_LEN 26
// 모든 단어는 알파벳 소문자로 구성된다.
#define TO_NUMBER(X) X - 'a'

typedef struct TriNode {

	int count = 0;              // 현재의 학습 된 문자가 몇개인지 알려주는 변수
	bool terminate = false;     // 문자의 끝을 알려주는 변수
	TriNode * child[MAX_LEN];

	TriNode() {
		memset(child, 0, sizeof(child));
	}

	~TriNode() {
		for (auto & node : child) {
			if (node) { delete node; }
		}
	}

	void insert(const char * key) {
        
        // 마지막 문자인 경우를 표시한다.
		if (*key == 0) { this->terminate = true; }
		else {
            // 소문자를 인덱스로 변환한다.
			const int next = TO_NUMBER(*key);
            
            // 현재 문자가 생성되어 있지 않은 경우 새로운 문자 인덱스 트리를 생성한다.
			if (child[next] == NULL) { child[next] = new TriNode(); }
            
            // 문자의 수를 증가시켜주며 다음 문자를 바탕으로 인덱스 트리를 생성한다.
			child[next]->count++;
			child[next]->insert(key + 1);
		}
	}
	
    // 입력 된 문자의 차이를 구하는 Find 함수
	int find(const char * key, const int cnt) {

		const int next = TO_NUMBER(*key);

        /* 
            해당 문자가 끝 문자인 경우에는 그 하나 전 단어만 입력하면 되기 때문에 현재 입력에서            하나를 빼어준다.
        */
		if (*key == 0 || child[next] == NULL) { return cnt - 1; }
		
        /* 
            해당 문자로 이어지는 문자열이 없는 경우 탐색을 종료한다. 왜냐하면 해당 문자로 시작하는 
            문자는 완전 다른 트리에 속하므로 다른 문자로 보아야 하기 때문이다.
            (이부분이 이해가 되지 않아서 많이 시간을 낭비함.)
        */
		if (child[next]->count == 1) { return cnt; }

		return child[next]->find(key + 1, cnt + 1);
	}

	/* 이 노드를 루트로 하는 Trie에 문자열 Key와 대응되는 노드를 찾고 없는경우 NULL을 반환한다. */
	TrieNode* find(const char * key) {
		if (*key == 0) { return this; }
		
		const int next = TO_NUMBER(*key);
		if (children[next] == NULL) { return NULL; } // 문자열 Key와 대응되는 노드를 찾기 못한 경우
		return children[next]->find(key + 1); // 문자열 Key와 대응되는 노드를 찾은 경우
	}
} Tri;

void printWord(string & contents, const Trie * node) {

	if (node->terminal) { cout << contents << endl; return; }

	for (int ii = 0; ii < MAX_LEN; ii++) {
		if (node->children[ii]) {
			contents.push_back(ii + 'A');
			printWord(contents, node->children[ii]);
			contents.pop_back();
		}
	}
}

---

🚀 REFERENCE

Trie - Wikipedia

Practical Data Structures for Frontend Applications: When to use Tries