<div id="readability-page-1" class="page"><div role="main" id="main-content"><div><h2>[TIL] 자바스크립트/자료구조 - 트라이(Trie)</h2></div><header><time>2022-03-11</time></header><ins data-ad-layout="in-article" data-ad-format="fluid" data-ad-client="ca-pub-6059434733081357" data-ad-slot="5099949480"></ins><article><div><ul><li>Retireval(탐색)에서 나온 단어 <ul><li>Radix tree, Prefix Tree 라고도 함 </li></ul></li><li>문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료구조</li><li>자동완성 검색에 주로 사용</li></ul><h2 id="트라이의-특징"><a href="#%ED%8A%B8%EB%9D%BC%EC%9D%B4%EC%9D%98-%ED%8A%B9%EC%A7%95" aria-label="트라이의 특징 permalink"></a>트라이의 특징</h2><h3 id="장점"><a href="#%EC%9E%A5%EC%A0%90" aria-label="장점 permalink"></a>장점</h3><ul><li>검색어 자동완성, 사전 찾기 등에 응용</li><li>문자열을 탐색할 때 단순하게 비교하는 것보다 효율적으로 찾을 수 있음 </li><li>시간복잡도: L이 문자열의 길이일 때 탐색, 삽입은 O(L)만큼 소요</li></ul><h3 id="단점"><a href="#%EB%8B%A8%EC%A0%90" aria-label="단점 permalink"></a>단점</h3><ul><li>각 정점이 자식에 대한 링크를 전부 가지고 있기에 저장 공간을 더 많이 사용함</li></ul><h2 id="트라이-구조"><a href="#%ED%8A%B8%EB%9D%BC%EC%9D%B4-%EA%B5%AC%EC%A1%B0" aria-label="트라이 구조 permalink"></a>트라이 구조</h2><img src="https://baek.dev/assets/images/til/data-structure-trie.png" alt="자료구조 트라이 예시"> <ul><li>루트는 비어 있음 </li><li>각 간선(링크)은 추가될 문자를 키로 가짐 </li><li>각 정점은 이전 정점의 값 + 간선의 키를 값으로 가짐 </li><li>해시 테이블과 연결 리스트를 이용하여 구현할 수 있음 </li></ul><h2 id="자바스크립트로-구현해본-트라이"><a href="#%EC%9E%90%EB%B0%94%EC%8A%A4%ED%81%AC%EB%A6%BD%ED%8A%B8%EB%A1%9C-%EA%B5%AC%ED%98%84%ED%95%B4%EB%B3%B8-%ED%8A%B8%EB%9D%BC%EC%9D%B4" aria-label="자바스크립트로 구현해본 트라이 permalink"></a>자바스크립트로 구현해본 트라이</h2><ul><li>문제 해결시에는 오브젝트, 배열을 사용하자 </li></ul><div data-language="javascript"><pre><code>
class Node {
 constructor(value = "") {
 this.value = value;
 this.children = new Map();
 }
}

class Trie {
 constructor() {
 this.root = new Node; // 루트 노드는 공백
 }

 insert(word) {
 let currentNode = this.root;

 // word = cat;
 for (const char of word) {
 console.log(`#### currentNode.children.has(${char}): ${currentNode.children.has(char)}`);
 if (!currentNode.children.has(char)) {
 currentNode.children.set(char, new Node(currentNode.value + char));

 Array.from(currentNode.children.keys()).forEach(([key]) =&gt; {
 console.log(`${key} : ${currentNode.children.get(key).value}`);
 });
 }

 currentNode = currentNode.children.get(char);
 }
 }

 has(word) {
 let currentNode = this.root;

 for (const char of word) {
 if (!currentNode.children.has(char)) {
 return false;
 }
 currentNode = currentNode.children.get(char);
 }
 return true;
 }
}


const trie = new Trie();
trie.insert('cat');
trie.insert('carry');
trie.insert('candy');
trie.insert('can');
trie.insert('cant');

console.log(trie.has('can')); // true
console.log(trie.has('candy')); // true
console.log(trie.has('con')); // false
</code></pre></div></div>쿠팡 파트너스 활동을 통해 일정액의 커미션을 제공받을 수 있습니다.</article><ins data-ad-layout="in-article" data-ad-format="fluid" data-ad-client="ca-pub-6059434733081357" data-ad-slot="5099949480"></ins></div></div>

아웃풋 트레이닝

BAEKDEV

트라이(Trie)란?
Retireval(탐색)에서 나온 단어  
Radix tree, Prefix Tree 라고도 함 
문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료구조
자동완성 검색에 주로 사용
트라이의 특징
장점
검색어 자동완성, 사전 찾기 등에 응용
문자열을 탐색할 때 단순하게 비교하는 것보다 효율적으로 찾을 수 있음  
시간복잡도: L이 문자열의 길이일 때 탐색, 삽입은 O(L)만큼 소요
단점
각 정점이 자식에 대한 링크를 전부 가지고 있기에 저장 공간을 더 많이 사용함
트라이 구조
  
루트는 비어 있음  
각 간선(링크)은 추가될 문자를 키로 가짐  
각 정점은 이전 정점의 값 + 간선의 키를 값으로 가짐  
해시 테이블과 연결 리스트를 이용하여 구현할 수 있음  
자바스크립트로 구현해본 트라이
문제 해결시에는 오브젝트, 배열을 사용하자  
class Node {
    constructor(value = "") {
        this.value = value;
        this.children = new Map();
    }
}
class Trie {
    constructor() {
        this.root = new Node; // 루트 노드는 공백
    }
    insert(word) {
        let currentNode = this.root;
        // word = cat;
        for (const char of word) {
            console.log(`#### currentNode.children.has(${char}): ${currentNode.children.has(char)}`);
            if (!currentNode.children.has(char)) {
                currentNode.children.set(char, new Node(currentNode.value + char));
                Array.from(currentNode.children.keys()).forEach(([key]) => {
                    console.log(`${key} : ${currentNode.children.get(key).value}`);
                });
            }
            currentNode = currentNode.children.get(char);
        }
    }
    has(word) {
        let currentNode = this.root;
        for (const char of word) {
            if (!currentNode.children.has(char)) {
                return false;
            }
            currentNode = currentNode.children.get(char);
        }
        return true;
    }
}
const trie = new Trie();
trie.insert('cat');
trie.insert('carry');
trie.insert('candy');
trie.insert('can');
trie.insert('cant');
console.log(trie.has('can'));   // true
console.log(trie.has('candy')); // true
console.log(trie.has('con'));   // false

자바스크립트/자료구조 - 트라이(Trie)

댓글