스마트폰의 자동 완성 기능이 어떻게 동작하는가?

단어들 모두를 배열에 저장했다면 O(N)으로 느릴 것이고, 해시 테이블은 단어를 통째로 해싱해서 키로 삼아야 하므로 사용할 수 없다. 정렬된 배열을 사용한다면 O(logN)로 빨라질 것이다. 하지만 특수한 트리 기반 자료 구조를 사용하면 O(1)의 속도로 원하는 단어에 접근할 수 있다.

트라이는 자동 완성이나 자동 수정 같은 중요한 기능을 지원한다.

17.1 트라이

트리의 한 종류인 트라이는 자동 완성 같은 텍스트 기반 기능에 이상적이다.

트라이는 추출을 뜻하는 retrieval에서 왔으니 트리로 발음해야 옳지만, 트리라는 발음이 모든 트리 기반 자료 구조에 보편적으로 쓰이므로 혼동을 막고자 트라이라고 발음한다.

17.1.1 트라이 노드

대부분의 트리처럼 트라이도 다른 노드를 가리키는 노드들의 컬렉션이다. 하지만 트라이는 이진 트리가 아니어서 자식 노드 개수에 제한이 없다.

책에서는 텍스트 처리 애플리케이션을 구현한다. 이 구현에서는 각 트라이 노드마다 키는 알파벳이고 값은 트라이의 다른 노드로 하는 해시 테이블을 포함한다.

class TrieNode {
  constructor() {
    this.children = new Map();
  }
}

17.1.1 트라이 클래스

완벽하게 트라이를 생성하려면 루트 노드를 추적하는 Trie 클래스도 별도로 필요하다.

class Trie{
	constrictor(){
		this.root = new TrieNode();
	}
}

이 클래스는 새 Trie를 생성하면 빈 TrieNode가 루트가 된다.

17.2 단어 저장