트라이는 자료구조의 탐색트리의 일종으로 문자열 탐색을 아주 빠르게 해주는 자료구조이다.
트리의 루트부터 자식들을 따라가며 생성한 문자열로 이루어 지며, 하나의 단어가 되면 끝을 표시하는 변수 end mark를 저장하여 단어의 끝을 구분할 수 있다.
장점 : 단순 리스트 저장해서 문자열을 비교하면서 탐색하는것에 비해 탐색의 시간복잡도가 매우 좋다.
단점 : 각 노드에 대한 자식에 대한 포인터를 배열로 저장하므로 공간 복잡도가 높다.
사용 : 검색어 자동완성, 사전 찾기, 문자열 검사 등에 사용됨
사진 출처 : https://twpower.github.io/187-trie-concept-and-basic-problem
트라이는 사진처럼 문자열 리스트를 각 알파벳 단위로 쪼개고 객체를 만들어 분류한다 예를 들면 [app, application]이 있다면 이 문자열들을 각각 쪼개어 객체 트리 형태로 만든다고 할때
a : {
p : {
p : {
//단어 한개가 끝났으니 표시하기 위해, end mark로 * : '해당 단어' 형태로 만들었다
* : "app",
l : {
i : {
c : {
a : {
t : {
i : {
o : {
n : {
* : "application",
}
}
}
}
}
}
}
}
}
}
}
위와 같은 구조가 트라이이다. 알파벳을 쪼개어 객체에 넣어주고, 단어가 끝나면 end mark 형태로 개발자 원하는 형태로 표시해두면 된다.
그리고 target 되는 즉 찾아야 하는 string 문자열이 들어 오면, 그걸 쪼개어 아래 trie에 검색해주면 해당하는 객체 depts 부터 가져올수 있는데, 그 객체를 갖고와서 dfs 탐색 알고리즘 사용하면 자식 노드로 깊게 들어가면서 탐색하게 된다. 탐색하면서 key 값이 "*" 문자열일때 array에 push해서 출력해주면 된다.
const list = ["cat", "cats", "dog", "dogs", "app", "application"];
const trie = {};
const solution = (list) => {
const newTrie = buildTrie(list);
};
const searchDFS = (target) => {
//여기서도 trie를 레퍼런스 참조 변수에 넘긴다.
let rootDict = trie;
const result = [];
//찾아야 하는 문자가 있으면 trie에서 깊이로 들어간다
for (let i = 0; i < target.length; i++) {
const curTargetChar = target[i];
if (!rootDict[curTargetChar]) return [];
rootDict = rootDict[curTargetChar];
}
//찾아야하는 문자 총 길이까지 깊이로 들어가고, 그 이상의 깊이는 DFSAlg()함수에 넣어준다. 즉 DFSAlg함수에서 단어의 end mark *를 찾아서 list에 push해서 리턴해주면 답이 된다.
DFSAlg(rootDict, result);
return result;
};
const DFSAlg = (curRoot, result) => {
// console.log(curRoot);
for (let [key, val] of Object.entries(curRoot)) {
if (key === "*") {
result.push(val);
continue;
}
DFSAlg(val, result);
}
};
//Trie를 만들어주는 함수다.
const buildTrie = (list) => {
if (!list.length) return {};
for (let l = 0; l < list.length; l++) {
const currentWord = list[l];
//trie를 사용하기 편하게 레퍼런스 참조변수를 만들어준다.
let currentRoot = trie;
for (let c = 0; c < currentWord.length; c++) {
//선택한 단어를 각 문자 단위로 선택한다.
const curChar = currentWord[c];
//trie에 선택한 문자 단위가 없으면, 문자단위를 키로 value={} 로 만들어 준다.
if (!currentRoot[curChar]) {
currentRoot[curChar] = {};
}
//문자 단위가 있으면 해당 위치를 currentRoot에 할당해준다.
currentRoot = currentRoot[curChar];
}
//단어가 끝나면 * :{ } 형태로 만들어준다.
currentRoot["*"] = currentWord;
}
};
solution(list);
//찾아야 할 문자열을 아래 target에 넣어주면된다.
searchDFS(target);