17장 트라이(trie)해 보는 것도 나쁘지 않다

• 스마트폰의 자동 완성 기능은 어떻게 동작할까?
• 특수한 트리 기반 자료 구조를 사용하면 O(1)의 속도로 원하는 단어에 접근할 수 있다.(!)
• 트라이는 자동 완성이나 자동 수정 같은 중요한 기능을 지원한다.

1. 트라이

• 트라이는 프리픽스 트리Prefix tree 혹은 디지털Digital tree 트리라고도 부른다.
• 트라이는 명쾌하게 설명되지 않는다.
• 교재마다, 설명마다 트라이를 조금씩 다르게 구현한다.

1.1 트라이 노드

• 트라이도 다른 노드를 가리키는 노드들의 컬렉션이다.
• 트라이 노드는 이진 트리와 다르게 자식 노드 개수에 제한이 없다.
• 이 교재의 구현에서는 각 트라이 노드마다 해시 테이블을 포함하며, 해시 테이블에서 키는 알파벳이고 값은 트라이의 다른 노드다.
• 즉, 해시 테이블에서 키는 개개 문자열이고 값은 다른 TrieNode 인스턴스다.

1.2 트라이 클래스

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

2. 단어 저장

• 트라이는 각 단어의 각 문자를 각각의 트라이 노드로 바꿔 세 개의 단어를 저장한다.
• 트라이에서, 각 단어들의 마지막 문자에도 자식 노드가 있다. 이는 단어의 끝을 나타낸다.
• 마지막 문자의 자식 노드의 키는 *이다.

2.1 별표(asterisk)의 필요성

• bat과 batter를 트라이에 저장하고 싶다고 가정하자.
• batter가 bat을 포함할 때, 굳이 “bat”을 두 번 저장해야 할 필요가 있을까?
• *은 단어의 일부도 단어일 수 있음을 나타내는 데 꼭 필요하다.

3. 트라이 검색

• 검색은 가장 대표적인 트라이 연산으로서 트라이에 어떤 문자열이 있는지 알아내는 것이다.
  • 검색의 목적은 크게 두 가지가 있다.
    1. 문자열이 완전한 단어인지 알아내는 것
    2. 문자열이 최소한 어떤 단어의 접두사인지 알아내는 것
  • 접두사를 찾다 보면 완전한 단어도 자연스레 찾을 수 있다.
• 접두사 검색 알고리즘은 다음과 같은 단계를 수행한다.
  1. currentNode라는 변수를 만든다. 알고리즘을 시작할 때 이 변수는 루트 노드를 가리킨다.
  2. 검색 문자열의 각 문자를 순회한다.
  3. 검색 문자열의 각 문자를 가리키며 currentNode에 그 문자를 키로 하는 자식이 있는지 본다.
  4. 자식이 없으면 검색 문자열이 트라이에 없다는 뜻이니 None을 반환한다.
  5. currentNode에 현재 문자를 키로 하는 자식이 있으면 currentNode를 그 자식 노드로 업데이트한다. 이어서 2단계로 돌아가 검색 문자열 내 각 문자를 계속 순회한다.
  6. 검색 문자열을 끝까지 순회했다면 검색 문자열을 찾았다는 뜻이다.

4. 트라이 검색의 효율성

• 트라이 검색의 장점은 엄청난 효율성이다.
• 앞선 알고리즘은 검색 문자열의 각 문자를 한 번에 하나씩 살펴본다. 그러면서 각 노드의 해시 테이블을 사용해 한 단계만에 적절한 자식 노드를 찾는다. 따라서 알고리즘은 검색 문자열 내 문자 수만큼의 연산 횟수가 필요하다.
• 이는 정렬된 배열에 이진 검색을 수행하는 것보다 훨씬 빠르다.
• N이 사전 내 단어 수일 때 이진 검색은 O(logN)이다.
• 트라이 검색은 검색하려는 단어 내 문자 개수만큼의 단계만 필요하다. 즉 “cat”은 3단계만 필요하다.
• 따라서 시간 복잡도를 빅 오 표기법으로 나타내기가 약간 까다롭다.
• 단계 수가 검색 문자열의 길이에 따라 달라지기 때문에 상수가 아니며, O(1)이라 말할 수 없다.
• O(N)에서 N은 일반적으로 자료구조 내 데이터 양을 말하기 때문에 오해의 소지가 있다.
• 많은 교재에서 이 복잡도를 O(K)라고 부른다. K는 검색 문자열 내 문자 수다.
• 검색 문자열마다 길이가 다르므로 O(K)가 상수는 아니지만, 한 가지 면에서 상수 시간과 비슷하다.
• 상수가 아닌 알고리즘은 대부분 처리해야 할 데이터양에 따라 실행 시간이 좌우된다. 즉, N이 커질수록 알고리즘이 느려진다.
• 하지만 O(K) 알고리즘에서는 트라이가 엄청나게 커지더라도 검색 속도에 영향이 없다.
• 알고리즘 속도에 영향을 미치는 요인은 사용 가능한 전체 데이터가 아니라 입력 크기뿐이다. 그래서 O(K) 알고리즘이 효율적인 것이다.

5. 트라이 삽입

• 트라이에 새 단어를 삽입하는 과정은 기존 단어를 검색하는 과정과 비슷하다.
• 삽입 알고리즘은 다음과 같다.

1. currentNode라는 변수를 만든다. 알고리즘을 시작할 때 이 변수는 루트 노드를 가리킨다.
2. 검색 문자열의 각 문자를 순회한다.
3. 검색 문자열의 각 문자를 가리키며 currentNode에 그 문자를 키로 하는 자식이 있는지 본다.
4. 자식이 있으면 currentNode를 그 자식 노드로 업데이트하고 2단계로 돌아가 검색 문자열 내 다음 문자로 넘어간다.
5. currentNode에 현재 문자와 일치하는 자식 노드가 없으면 자식 노드를 생성하고 currentNode를 이 새 노드로 업데이트한다. 이어서 2단계로 돌아가 검색 문자열 내 다음 문자로 넘어간다.
6. 삽입할 단어의 마지막 문자까지 삽입했으면 마지막 노드에 “*”자식을 추가해 단어가 끝났음을 알린다.

9. 마무리

• 지금까지 이진 탐색 트리, 힙, 트라이라는 세 종류의 트리를 살펴봤다. 이 밖에 AVL 트리, RB트리, 2-3-4 트리 등 많은 종류의 트리가 있다.
• 각 트리마다 특정 상황에 유용하게 쓰일 만한 고유한 성질과 동작을 지닌다.