트라이
ex) 자동완성, 사전 찾기
L이 문자열의 길이일 때 탐색, 삽입은 O(L) 만큼 걸림
정점이 자식에 대한 링크를 전부 가지고 있어 공간 많이 사용
- 루트: 비어있음
- 각 간선(링크)는 추가될 문자를 키로 가진다.
- 각 정점은 이전 정점의 값 + 간선의 키를 값으로 가진다.
- 해시 테이블과 연결 리스트를 이용해 구현한다.
코드로 구현
트라이 구성
// 트리 자료구조 -> 노드 필요
// 인접 리스트 형태로 구현
class Node {
constructor(value = "") {
this.value = value;
this.children = new Map();
}
}
// 트라이 생성하는 루트로 빈 노드 생성
class Trie {
constructor() {
this.root = new Node();
}
// 문자열 추가 -> 탐색 위해 루트부터 시작
insert(string) {
let currentNode = this.root;
// 문자열을 앞부터 하나씩 자르며 순회
for (const char of string) {
let currentNode = this.root;
// 가지고 있지 않은 문자열은 새로운 노드 추가
for (const char of string) {
if (!currentNode.children.has(char)) {
currentNode.children.set(
char,
new Node(currentNode.value + char)
);
}
// 다음 정점으로 이동
currentNode = currentNode.children.get(char);
}
}
// 문자열 전부 요소로 추가 완료
// 문자열이 존재하는지 체크하는 함수
has(string) {
let currentNode = this.root;
// 문자열 순회, 없으면 false 리턴
for (const char of string) {
if (!currentNOde.children.has(char)) {
return false;
}
currentNode = currentNode.children.get(char);
}
return true;
}
}
const trie = new Trie();
trie.insert("cat");
trie.insert("can");
console.log(trie.has("cat")); // true
console.log(trie.has("can")); // true
console.log(trie.has("cap")); // false