Trie 자료구조

작성일:2026.04.11|조회수:14

Javascript번역 및 정리#자료구조#trie
Trie 자료구조

문자열 데이터를 다룰 때 단순히 “이 단어가 있나?”만으로는 부족한 순간이 있다. 자동 완성처럼 특정 접두사로 시작하는 후보를 모아야 할 때도 있고, 어떤 키에 값을 두고 빠르게 찾고 싶을 때도 있다. 이럴 때 가장 자연스럽게 떠올릴 수 있는 자료구조가 바로 Trie이다.

Trie는 무엇인가

Trie는 보통 Prefix Tree라고도 부르는데, 이 자료구조의 핵심 아이디어는 단순하다. 문자열 전체를 한 덩어리 키로 저장하는 대신, 문자 하나하나를 노드로 이어 붙여 경로로 저장하는 것이다.

예를 들어 cat, car, dog를 저장한다고 해보자. 그러면 cat과 car는 c -> a까지는 같은 경로를 공유하고, 마지막에서만 t와 r로 갈라진다. 즉, 공통 접두사를 가진 문자열은 구조를 공유하게 되는 것이다. 이 구조가 주는 장점은 다음과 같다.

1. 접두사 탐색이 빠르다. ca로 시작하는 단어가 있는지 확인하려면 c -> a 경로만 따라가면 된다.

2. 문자열 길이에 비례해 동작한다. 검색 성능이 전체 원소 수보다 검색 문자열 길이에 더 직접적으로 묶인다.

3. 자동 완성, 사전 검색, 라우팅 테이블 같은 문제와 잘 맞는다.

당연하게도 단점도 있다. 일반적인 Set이나 Map보다 구현이 복잡하고, 문자 단위 노드를 많이 만들어야 하기 때문에 데이터 특성에 따라 메모리를 더 먹기도 한다. 그러니 Trie는 “문자열 접두사 문제”가 있을 때에 한정하여 사용할 수 있는 카드라고 생각하는 편이 좋을 것 같다.

공통 TrieNode 설계

Trie에서 각 노드는 자식 문자로 이어지는 children과 현재 지점이 하나의 키 끝인지 나타내는 플래그를 가진다. TrieMap<V>까지 생각하면 값 저장 여부도 관리해야 하므로, 아래처럼 조금 일반화해 두는 편이 좋다.

TS
class TrieNode<V> {
  public readonly children = new Map<string, TrieNode<V>>();
  public isTerminal = false;
  public hasValue = false;
  public value: V | undefined = undefined;
}

여기서 hasValue를 따로 둔 이유는 TrieMap<V>에서 값 타입 V가 undefined를 허용할 수도 있기 때문이다. 단순히 value !== undefined만으로는 “값이 실제로 저장되었는지”를 구분할 수 없기 때문에 값의 존재 여부와 값 그 자체를 분리해 두는 편이 타입적으로 더 안전하다.

반대로 기본 Trie는 값을 저장하지 않으므로 TrieNode<never>를 사용해 “이 노드에는 값이 없다”는 의도를 타입 수준에서도 드러낼 수 있다.

이제 이 노드를 바탕으로 가장 기본이 되는 자료 구조인 Trie와 TrieSet, TrieMap<V> 을 구현해보자.

Trie

먼저 가장 직관적인 기본형 자료구조 Trie이다. 이 버전은 “문자열을 저장하고, 존재 여부를 확인하고, 접두사를 검사하고, 삭제하고, 순회한다”에 집중한다. Set처럼 친숙하게 느껴지도록 add, has, delete, clear, size, [Symbol.iterator]()를 넣어서 구현했다.

TS
class Trie implements Iterable<string> {
  private root = new TrieNode<never>();
  private _size = 0;

  get size(): number {
    return this._size;
  }

  add(word: string): this {
    if (word.length === 0) {
      throw new Error("Trie는 빈 문자열을 허용하지 않습니다.");
    }

    let node = this.root;

    for (const char of word) {
      let next = node.children.get(char);

      if (!next) {
        next = new TrieNode<never>();
        node.children.set(char, next);
      }

      node = next;
    }

    if (!node.isTerminal) {
      node.isTerminal = true;
      this._size += 1;
    }

    return this;
  }

  has(word: string): boolean {
    const node = this.findNode(word);
    return node !== null && node.isTerminal;
  }

  startsWith(prefix: string): boolean {
    return this.findNode(prefix) !== null;
  }

  delete(word: string): boolean {
    const path: Array<{ parent: TrieNode<never>; char: string }> = [];
    let node = this.root;

    for (const char of word) {
      const next = node.children.get(char);
      if (!next) {
        return false;
      }

      path.push({ parent: node, char });
      node = next;
    }

    if (!node.isTerminal) {
      return false;
    }

    node.isTerminal = false;
    this._size -= 1;

    for (let i = path.length - 1; i >= 0; i -= 1) {
      const { parent, char } = path[i];
      const child = parent.children.get(char);

      if (!child) {
        break;
      }

      if (child.isTerminal || child.children.size > 0) {
        break;
      }

      parent.children.delete(char);
    }

    return true;
  }

  clear(): void {
    this.root = new TrieNode<never>();
    this._size = 0;
  }

  *words(): Generator<string> {
    yield* this.walk(this.root, "");
  }

  [Symbol.iterator](): Iterator<string> {
    return this.words();
  }

  private findNode(text: string): TrieNode<never> | null {
    let node = this.root;

    for (const char of text) {
      const next = node.children.get(char);
      if (!next) {
        return null;
      }
      node = next;
    }

    return node;
  }

  private *walk(node: TrieNode<never>, prefix: string): Generator<string> {
    if (node.isTerminal) {
      yield prefix;
    }

    for (const [char, child] of node.children) {
      yield* this.walk(child, prefix + char);
    }
  }
}

이 자료구조를 사용하는 예시는 아래와 같다.

TS
const trie = new Trie();

trie.add("cat").add("car").add("dog");

console.log(trie.size); // 3
console.log(trie.has("cat")); // true
console.log(trie.has("can")); // false
console.log(trie.startsWith("ca")); // true
console.log(trie.startsWith("do")); // true
console.log(trie.startsWith("z")); // false

console.log([...trie]); // 예: ["cat", "car", "dog"]

trie.delete("car");

console.log(trie.has("car")); // false
console.log(trie.has("cat")); // true
console.log(trie.startsWith("ca")); // true

여기서 중요한 포인트는 delete("car")를 해도 cat이 살아 있으면 c -> a 경로는 그대로 유지된다는 점이다. 즉, Trie는 문자열을 독립된 객체처럼 저장하는 것이 아니라 공유 경로를 중심으로 저장한다.

TrieSet

위 Trie도 사실상 집합처럼 동작하지만 “이건 완전히 문자열 전용 집합이다”라는 의도를 더 분명히 드러내고 싶을 수 있습니다. 그런 경우 TrieSet이라는 이름을 주고, Set과 유사한 API를 조금 더 강조해서 만들 수 있다. new Set(["cat", "car"]) 같은 느낌을 살리고 싶어서 이번에는 이번에는 생성자에서 초깃값을 받을 수 있게 구현해보았다.

TS
class TrieSet implements Iterable<string> {
  private readonly trie: Trie;

  constructor(values?: Iterable<string>) {
    this.trie = new Trie();

    if (values) {
      for (const value of values) {
        this.add(value);
      }
    }
  }

  get size(): number {
    return this.trie.size;
  }

  add(value: string): this {
    this.trie.add(value);
    return this;
  }

  has(value: string): boolean {
    return this.trie.has(value);
  }

  startsWith(prefix: string): boolean {
    return this.trie.startsWith(prefix);
  }

  delete(value: string): boolean {
    return this.trie.delete(value);
  }

  clear(): void {
    this.trie.clear();
  }

  values(): IterableIterator<string> {
    return this.trie[Symbol.iterator]();
  }

  keys(): IterableIterator<string> {
    return this.values();
  }

  entries(): IterableIterator<[string, string]> {
    return this.entryGenerator();
  }

  [Symbol.iterator](): IterableIterator<string> {
    return this.values();
  }

  private *entryGenerator(): Generator<[string, string]> {
    for (const value of this.trie) {
      yield [value, value];
    }
  }
}

이 자료구조를 사용하는 예시는 아래와 같다.

TS
const keywords = new TrieSet(["class", "const", "continue"]);

keywords.add("catch").add("case");

console.log(keywords.has("const")); // true
console.log(keywords.has("console")); // false
console.log(keywords.size); // 5

for (const keyword of keywords) {
  console.log(keyword);
}

console.log([...keywords.entries()]);
// 예: [["class", "class"], ["const", "const"], ...]

이 구현의 장점은 두 가지이다. 첫째로, 사용자 입장에서 매우 읽기 쉽다. 이름만 봐도 “문자열 전용 집합이구나”라는 의도가 드러난다. 둘째로, 내부 구현은 Trie에 위임하므로 중복 코드가 줄어든다. 즉, Trie는 핵심 엔진이고, TrieSet은 좀 더 표준 컬렉션처럼 보이게 만든 래퍼라고 이해할 수 있다.

TrieMap<V>

이제 가장 실용적인 버전으로 넘어가보자. 자동 완성 기능을 생각해 보면, 단순히 단어만 저장해서는 부족할 수가 있다. 예를 들어 각 단어 별로 아래와 같은 데이터가 필요할 수 있다. 이럴 때는 Map처럼 문자열 키에 값을 연결할 수 있는 TrieMap<V>가 훨씬 유용하다.

TS
class TrieMap<V> implements Iterable<[string, V]> {
  private root = new TrieNode<V>();
  private _size = 0;

  get size(): number {
    return this._size;
  }

  set(key: string, value: V): this {
    if (key.length === 0) {
      throw new Error("TrieMap은 빈 문자열 키를 허용하지 않습니다.");
    }

    let node = this.root;

    for (const char of key) {
      let next = node.children.get(char);

      if (!next) {
        next = new TrieNode<V>();
        node.children.set(char, next);
      }

      node = next;
    }

    if (!node.hasValue) {
      this._size += 1;
    }

    node.isTerminal = true;
    node.hasValue = true;
    node.value = value;

    return this;
  }

  get(key: string): V | undefined {
    const node = this.findNode(key);
    if (!node || !node.hasValue) {
      return undefined;
    }

    return node.value;
  }

  has(key: string): boolean {
    const node = this.findNode(key);
    return node !== null && node.hasValue;
  }

  startsWith(prefix: string): boolean {
    return this.findNode(prefix) !== null;
  }

  delete(key: string): boolean {
    const path: Array<{ parent: TrieNode<V>; char: string }> = [];
    let node = this.root;

    for (const char of key) {
      const next = node.children.get(char);
      if (!next) {
        return false;
      }

      path.push({ parent: node, char });
      node = next;
    }

    if (!node.hasValue) {
      return false;
    }

    node.hasValue = false;
    node.isTerminal = false;
    node.value = undefined;
    this._size -= 1;

    for (let i = path.length - 1; i >= 0; i -= 1) {
      const { parent, char } = path[i];
      const child = parent.children.get(char);

      if (!child) {
        break;
      }

      if (child.hasValue || child.children.size > 0) {
        break;
      }

      parent.children.delete(char);
    }

    return true;
  }

  clear(): void {
    this.root = new TrieNode<V>();
    this._size = 0;
  }

  findEntriesWithPrefix(prefix: string): Array<[string, V]> {
    const start = this.findNode(prefix);
    if (!start) {
      return [];
    }

    return [...this.collect(start, prefix)];
  }

  keys(): IterableIterator<string> {
    return this.keyGenerator();
  }

  values(): IterableIterator<V> {
    return this.valueGenerator();
  }

  entries(): IterableIterator<[string, V]> {
    return this.entryGenerator();
  }

  [Symbol.iterator](): IterableIterator<[string, V]> {
    return this.entries();
  }

  private findNode(text: string): TrieNode<V> | null {
    let node = this.root;

    for (const char of text) {
      const next = node.children.get(char);
      if (!next) {
        return null;
      }
      node = next;
    }

    return node;
  }

  private *collect(node: TrieNode<V>, prefix: string): Generator<[string, V]> {
    if (node.hasValue) {
      yield [prefix, this.requireValue(node)];
    }

    for (const [char, child] of node.children) {
      yield* this.collect(child, prefix + char);
    }
  }

  private requireValue(node: TrieNode<V>): V {
    if (!node.hasValue) {
      throw new Error("값이 없는 노드입니다.");
    }

    return node.value as V;
  }

  private *keyGenerator(): Generator<string> {
    for (const [key] of this.collect(this.root, "")) {
      yield key;
    }
  }

  private *valueGenerator(): Generator<V> {
    for (const [, value] of this.collect(this.root, "")) {
      yield value;
    }
  }

  private *entryGenerator(): Generator<[string, V]> {
    yield* this.collect(this.root, "");
  }
}

TrieMap<V>을 사용하는 방식은 여러 가지가 있는데, 다음과 같이 검색 횟수를 저장할 수도 있다.

TS
const searchCounts = new TrieMap<number>();

searchCounts
  .set("react", 128)
  .set("redis", 64)
  .set("relay", 12)
  .set("rust", 77);

console.log(searchCounts.get("react")); // 128
console.log(searchCounts.get("vue")); // undefined
console.log(searchCounts.has("redis")); // true
console.log(searchCounts.startsWith("re")); // true
console.log(searchCounts.findEntriesWithPrefix("re"));
// 예: [["react", 128], ["redis", 64], ["relay", 12]]

혹은 자동 완성 후보 객체를 저장할 때도 유용합니다.

TS
type Suggestion = {
  label: string;
  score: number;
  category: 'language' | 'framework' | 'database';
};

const suggestions = new TrieMap<Suggestion>();

suggestions
  .set('typescript', {
    label: 'TypeScript',
    score: 98,
    category: 'language',
  })
  .set('tsup', {
    label: 'tsup',
    score: 72,
    category: 'framework',
  })
  .set('typeorm', {
    label: 'TypeORM',
    score: 60,
    category: 'database',
  });

const tsMatches = suggestions.findEntriesWithPrefix('ts');

for (const [key, item] of tsMatches) {
  console.log(key, item.label, item.score);
}

TrieMap<V>는 단순 문자열 집합을 넘어, 문자열 경로 끝에 비즈니스 데이터를 연결할 수 있다. 이 구현에서는 hasValue를 기준으로 실제 엔트리 존재 여부를 판단하고, isTerminal은 “이 경로가 하나의 완성된 키 지점인가”라는 구조적 의미를 함께 남겨둔다. 지금 예제에서는 hasValue만으로도 충분히 동작하지만, 두 상태를 분리해 두면 이후 prefix only 노드나 추가 메타데이터를 붙일 때 설계를 확장하기 쉬워진다.

시간 복잡도와 공간 복잡도

Trie를 이야기할 때 흔히 “빠르다”라고만 말하고 넘어가지만, 정확히는 문자열 길이에 비례해 빠르다고 이해하는 편이 좋다. 아래의 리스트에서 L은 문자열 길이를 나타낸다. 전체 데이터 개수가 아무리 커져도, 적어도 개별 연산의 핵심 경로는 문자열 길이에 의해 결정된다.

공간 복잡도는 데이터 특성에 따라 달라진다. 공통 접두사가 많으면 경로를 많이 공유하므로 효율적일 수 있지만, 겹치는 부분이 거의 없으면 노드 수가 빠르게 늘어난다. 즉, Trie는 언제나 무조건 이득인 자료구조가 아니라, 접두사 공유가 실제로 의미 있는 문제에서 강해지는 자료구조이다.

Trie가 특히 잘 맞는 상황

실무에서 Trie가 빛나는 대표적인 사례는 아래와 같다.

자동 완성

사용자가 rea까지 입력했을 때 react, reason, ready 같은 후보를 보여 주고 싶다면 Trie는 아주 좋은 선택지가 된다. 접두사 지점까지 한 번 내려간 뒤 하위 노드만 순회하면 되기 때문이다.

금칙어 / 사전 매칭

텍스트 편집기나 검증기에서 특정 패턴 사전을 빠르게 매칭해야 할 때도 유용하다.

문자열 키 기반 라우팅

URL 세그먼트, 명령어, 토큰 사전처럼 “문자열 구조 자체”가 중요한 데이터에 잘 어울린다.

반대로, 접두사 탐색이 전혀 필요 없고 단순 exact match만 필요하다면 기본 Map이나 Set이 훨씬 간단하고 메모리 측면에서도 나을 가능성이 크다.

마무리

이번 글에서 만든 세 가지를 다시 요약하면 이렇습니다.

자료구조를 직접 구현해 보는 일은 단순히 코딩 연습을 넘어서, “좋은 API는 어떤 느낌인가”, “내부 표현을 외부 사용성과 어떻게 분리할 것인가”를 계속 고민하게 한다. 만약 Trie에 흥미를 느끼고 다음 단계로 확장해 보고 싶다면, 이후에는 prefixSearch(limit), longestPrefixOf, 대소문자 정규화, 유니코드 처리, 빈도 기반 정렬까지 추가해 보면 훨씬 실전적인 Trie 컬렉션이 되지 않을까 싶다.

더 읽어보기

  • 2026.03.13

    Streams API 2. 상태와 백프레셔의 의미론

    Javascript#streams-api

    스트림을 처음 배울 때는 읽고 쓰는 예제가 꽤 단순해 보인다. getReader()로 읽고, getWriter()로 쓰고, pipeTo()로 연결하면 끝나는 것처럼 느껴진다. 실제로 짧은 데모는 이 정도만 알아도 돌아간다. 그러나 실무에서 스트림 코드를 망가뜨리는 원인은 거의 언제나 더…

  • 2026.03.13

    Streams API 1. 읽기와 쓰기의 출발점

    Javascript#streams-api

    자바스크립트에서 비동기를 배울 때 우리는 대개 Promise와 async, await부터 익힌다. 이 조합은 한 번의 결과를 기다리는 문제에는 매우 강력하다. 그러나 데이터가 한 번에 끝나지 않고 계속 흘러들어오는 상황에서는 이야기가 달라진다. 네트워크 응답이 길게 이어지거나, 큰 파일…

  • 2026.03.01

    함수, 펑터, 그리고 모나드

    번역 및 정리#functional

    복잡한 버그는 대개 거대한 기능이 아니라 사소한 데이터 변환 구간에서 시작된다. 문자열을 한 번 다듬고, 숫자를 한 번 바꾸고, 그 결과를 다음 단계로 넘기는 단순한 흐름이다. 그런데 조건이 조금씩 추가되는 순간 로직은 빠르게 복잡해진다. 값만 바꾸던 코드가 어느새 값의 부재, 비동기…

댓글

댓글을 불러오는 중...