JavaScript Trie: Unicode 접두사 검색과 안전한 삭제 구현

여기부터는 필요한 기능을 골라 읽는 참고 영역입니다. 새로운 파일로 전체 코드를 실행할 때는 아래 Node.js 실행 안내를 따르세요. 앞쪽의 작은 브라우저 실습과 전체 파일을 한 콘솔에 이어 붙이지 마세요. 기능별 입력 조건과 반환 형식은 아래 설명을 기준으로 합니다.

문제 상황과 API 계약

별칭 “가”, “가방”, “가방끈”을 Set에 저장하면 정확한 이름 조회는 간단합니다. 하지만 “가방으로 시작하는 별칭이 몇 개인가?”를 매번 묻는다면 모든 문자열을 훑어야 합니다. Trie는 공통 접두사를 한 경로로 묶어 접두사 끝 노드에서 답을 얻습니다. 빈번한 접두사 질의가 이 구조를 선택하는 이유입니다.

이 구현은 중복을 저장하지 않는 문자열 집합입니다. insert는 새 단어일 때 true, delete는 실제 삭제했을 때 true입니다. has는 단어 전체가 등록되었는지, countPrefix는 해당 접두사로 시작하는 서로 다른 단어 수를 반환합니다. startsWith는 그 수가 0보다 큰지 확인합니다. 비어 있는 Trie에서 startsWith("")는 false라는 계약을 정했습니다.

문자열은 […word]로 순회합니다. 이는 UTF-16 코드 유닛 인덱싱 대신 JavaScript 문자열 반복자의 코드포인트 단위를 사용합니다. 😀는 한 간선이지만 가족 이모지나 결합 문자는 여러 간선일 수 있습니다. 사용자에게 보이는 한 글자와 동일하지 않으며 NFC 정규화도 하지 않습니다. 완성형 é와 e 뒤에 결합 악센트를 붙인 표현은 별개 키이고 대소문자도 구분합니다. 고립된 surrogate가 들어온 비정상 문자열을 별도로 거부하는 기능은 없습니다.

정확성을 지키는 불변식

각 노드의 children은 다음 코드포인트에서 자식 노드로 가는 Map입니다. end는 “여기에서 정확히 끝나는 단어가 있는가”를 나타냅니다. pass는 이 노드 아래에서 끝나는 서로 다른 단어 수이며, 해당 노드의 end가 true인 경우 자신도 포함합니다. root.pass는 전체 단어 수입니다.

insert는 먼저 경로를 만들고 마지막 노드의 end를 확인합니다. 이미 true이면 어떤 pass도 증가시키지 않습니다. 새 단어이면 root부터 끝 노드까지 pass를 1 올립니다. 빈 문자열은 간선을 만들지 않고 root.end만 바꾸므로 별도의 특수 노드를 만들 필요가 없습니다.

delete는 끝까지 경로가 있고 end도 true인 경우에만 변경합니다. end를 끄고 경로의 pass를 1 줄인 뒤 아래에서 위로 pass===0인 자식만 제거합니다. 짧은 단어를 지웠다고 children 전체를 지우면 “가” 삭제가 “가방”까지 날리는 오류가 생깁니다. 반대로 빈 경로를 계속 남기면 등록·삭제가 반복될수록 쓸모없는 노드가 쌓입니다.

전체 구현과 실행

Node.js 24의 CommonJS 환경을 기준으로 합니다. 아래 전체 코드를 trie.cjs로 저장하고 파일이 있는 폴더에서 node trie.cjs를 실행하세요. 외부 패키지는 필요하지 않습니다. module.exports는 다른 파일에서 가져올 때 사용하며 require.main 조건 안의 호출은 직접 실행할 때만 작동합니다.

class TrieNode {
  constructor() {
    this.children = new Map();
    this.end = false;
    this.pass = 0;
  }
}
class Trie {
  constructor() { this.root = new TrieNode(); }
  chars(word) {
    if (typeof word !== 'string') throw new TypeError('문자열이 필요합니다.');
    return [...word];
  }
  walk(word) {
    let node = this.root;
    for (const ch of this.chars(word)) {
      node = node.children.get(ch);
      if (!node) return null;
    }
    return node;
  }
  insert(word) {
    let node = this.root;
    const path = [node];
    for (const ch of this.chars(word)) {
      if (!node.children.has(ch)) node.children.set(ch, new TrieNode());
      node = node.children.get(ch);
      path.push(node);
    }
    if (node.end) return false;
    node.end = true;
    for (const item of path) item.pass++;
    return true;
  }
  has(word) { return this.walk(word)?.end ?? false; }
  countPrefix(prefix) { return this.walk(prefix)?.pass ?? 0; }
  startsWith(prefix) { return this.countPrefix(prefix) > 0; }
  delete(word) {
    const chars = this.chars(word);
    let node = this.root;
    const path = [node];
    for (const ch of chars) {
      node = node.children.get(ch);
      if (!node) return false;
      path.push(node);
    }
    if (!node.end) return false;
    node.end = false;
    for (const item of path) item.pass--;
    for (let i = chars.length - 1; i >= 0; i--) {
      if (path[i + 1].pass !== 0) break;
      path[i].children.delete(chars[i]);
    }
    return true;
  }
}

module.exports = { Trie };

if (require.main === module) {
  const t = new Trie();
  ['가', '가방', '가', '😀빛'].forEach(word => t.insert(word));
  t.delete('가');
  console.log(JSON.stringify({ exact: t.has('가'), prefix: t.countPrefix('가'), emoji: t.has('😀빛') }));
}

직접 실행 출력:

{"exact":false,"prefix":1,"emoji":true}

walk는 정확 검색과 접두사 집계가 공유하는 경로 탐색입니다. 중간 자식이 없으면 null을 반환합니다. 경로가 있다고 단어가 등록된 것은 아니므로 has는 반드시 end를 읽고, countPrefix는 pass를 읽습니다.

삽입과 삭제에서 path 배열을 유지하면 재귀 없이 조상의 집계값을 한 번씩 갱신할 수 있습니다. 삭제 때 chars[i]는 path[i]가 가진 간선 이름이고 path[i+1]이 그 간선의 자식입니다. 인덱스를 뒤집어 부모의 pass로 제거 여부를 판단하면 다른 단어의 경로를 지울 수 있습니다.

예제에서 “가”를 지워도 “가방”은 남으므로 exact는 false, prefix는 1입니다. 이모지로 시작하는 문자열도 같은 순회 규칙으로 들어갔으므로 emoji는 true입니다. 접두사 결과 나열이나 자동완성 순위 정렬은 구현 범위에 포함하지 않았습니다.

상태 변화 따라가기

복잡도와 적용하지 말아야 할 경우

Map 접근이 노드당 M 시간이라면 경로 연산은 O(L·M)입니다. 해시 테이블을 기대하고 쓰는 O(L)을 JavaScript 명세의 최악 시간 보장으로 바꾸면 안 됩니다. 알파벳이 고정되어 작다면 고정 배열 자식으로 더 명확한 시간 상한을 얻을 수 있지만 메모리 사용은 달라집니다.

정확한 문자열 포함 여부만 필요하면 Set이 더 간단합니다. 접두사 목록이 정적이라면 정렬 배열에서 접두사 범위를 이진 탐색하는 대안도 있습니다. 문자열이 길고 공통 접두사가 드물면 Trie의 노드 객체와 Map 오버헤드가 커집니다.

텍스트 정규화, 검색 언어의 대소문자 규칙, 사용자가 보는 글자 단위 분할이 요구되면 입력 정책을 먼저 정해야 합니다. 문자열을 일부에서만 normalize하면 삽입한 키를 삭제하지 못합니다. 이 코드의 pass는 빈 문자열도 포함한 집합 개수이며 출현 빈도 카운터가 아닙니다.

연습으로 확인하기

등록과 삭제가 섞인 별칭 목록에서 접두사별 서로 다른 항목 수를 반환해 보세요. 전체 목록을 나열하지 않고 pass만 읽는 이유를 확인할 수 있습니다.

[창작 문제] 전시 별칭 관리대장의 접두사 수

LeetCode 208 – Implement Trie (Prefix Tree) — 기본 삽입·정확 검색·접두사 검색을 연습하는 공식 문제입니다. 여기의 빈 문자열·Unicode·삭제 계약은 그 문제와 별도로 정한 확장입니다.

공식 자료

공식 자료 확인일: 2026년 9월 10일. 구현은 이 글의 JavaScript 계약에 맞춰 독립적으로 작성했습니다. 다른 언어 라이브러리의 API와 숫자 범위가 그대로 적용되는 것은 아닙니다.

• MDN 문자열 반복자: 코드포인트 순회
• MDN Map: 접근 성능과 키 의미
• LeetCode 208 – Implement Trie (Prefix Tree)