- Published on
[자료구조] javascript 트라이 (Trie)
- Authors
- Name
- piano cat
javascript 에서 트라이 자료구조에 대해서 알아보자
목차
- 트라이 자료구조란
- 트라이 자료구조 특징
- 트라이 구현
- 활용예시
트라이 자료구조란
트라이 자료구조는 문자열을 저장하고 검색하는 데 사용되는 특별한 트리 형태의 자료구조입니다. 이 자료구조는 각 문자마다 노드를 가지며, 문자열을 구성하는 문자들을 노드로 연결하여 저장합니다.
트라이 구조의 특징
트라이 자료구조의 주요 특징은 빠른 탐색 속도, 메모리 효율성, 그리고 문자열 검색에 용이하다는 것입니다. 각 문자마다 노드를 가지기 때문에 검색 과정에서 다음 문자로의 이동이 빠르고 효율적입니다. 또한 문자열이 겹치는 부분이 많아도 중복된 노드를 공유하여 메모리를 절약할 수 있습니다. 이러한 특징으로 인해 트라이 자료구조는 대용량의 문자열 데이터를 효율적으로 처리할 수 있습니다.
트라이 구현
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){
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;
for(const char of string){
if(!currentNode.children.has(char)){
return false;
}
currentNode = currentNode.children.get(char);
}
return true;
}
}
const trie = new Trie();
활용 예시
자동 완성 기능, 철자 검사 및 교정, 문자열 패턴 매칭 등
- 자동 완성 기능 : 사용자가 입력한 문자열에 대해 가능한 후보 단어를 빠르게 제공하여 사용자 경험을 향상시킵니다.
- 철자 검사 및 교정: 올바르지 않은 철자를 가진 문자열을 효율적으로 식별하고 교정할 수 있습니다.
- 문자열 패턴 매칭: 특정 패턴을 가진 문자열을 효율적으로 찾아내는 데에 사용됩니다.