하나의 노드는 다음과 같이 구성된다.
현재 문자를 담을, 혹은 현재까지의 문자열을 저장할 value
,
현재 문자에서 끝나는 문자열이 있는지를 저장할 end
,
더 이어지는 문자열이 있다면, 해당 노드를 저장하는 children
으로 구성된다.
자바스크립트 코드로 나타내면 다음과 같다.
class Node {
constructor(value = "") {
this.value = value; // 현재까지의 문자열을 저장.
this.end = false; // 해당 노드에서 끝나는 문자열이 있는지.
this.children = {}; // 더 연결되는 문자열들의 노드를 저장.
}
}
go
, gone
, guild
를 차례로 담아보자.
우선 root
노드부터 시작해서 g
, o
순으로 연결하게 된다.
기존에 go
와 o
가 없기 때문에 노드를 생성해서 연결한다.
다음으로, gone
과 guild
를 넣으면
value
는 위와 같이 현재까지의 문자열을 저장하기도 하고, 각 원소를 저장하기도 하는 것 같다.
현재 상황에서 더 참조하기 쉬운 형태로 저장하면 될 것 같다.
위와 같은 구조를 자바스크립트로 구현해보자.
class Trie {
constructor() {
this.root = new Node() // root는 빈 노드를 하나 만든다.
}
// 새 단어 추가
insert(string) {
let curNode = this.root; // root노드를 시작으로 현재까지의 문자열과 일치하는 노드가 존재하는 지 확인하며 삽입한다.
for (let i=0; i<string.length; i++) {
const currentChar = string[i];
if (curNode.children[currentChar] === undefined) {
curNode.children[currentChar] = new Node(curNode.value + currentChar);
// curNode.child[currentChar] = new Node(currentChar); -> 각 자리 요소만 저장하는 경우.
}
curNode = curNode.children[currentChar];
}
currentNode.end = true; // 마지막 원소까지 저장한 후에는 끝나는 단어가 생긴 것이므로 true로 변경
}
// 단어 존재 여부 확인
search(string) {
let curNode = this.root;
for (let i=0; i<string.length; i++) {
let currentChar = string[i];
if (curNode.children[currentChar]) {
curNode = curNode.children[currentChar];
} else {
return false;
}
}
// 문자열을 순차적으로 모두 도는데 성공한 경우
return true;
}
}
문자열 검색이나, 자동완성 등을 구현할 때에 이를 적용하면,
문자열 집합의 개수와 상관없이 찾고자 하는 문자열의 길이가 n
이라면 시간복잡도도 O(n)
이라고 한다.
따라서, 다른 구조보다 빠르게 문자열을 찾을 수 있다.
위키백과 트라이 (컴퓨팅)
Implementing a Trie in JavaScript Part 1
teihong93님의 자바스크립트를 이용한 Trie 구현