Trie(트라이) 자료구조란?

문자열 탐색을 효율적으로 수행하기 위한 Tree 기반 자료구조이다. 문자열 검색, 자동완성, 사전 구현 등에 사용된다.

1. Trie 기본구조

각 노드가 한개의 문자를 저장하는 트리 구조이다. 루트 노드는 공백이고, 각 간선은 문자를 나타낸다. 문자열이 삽입될 때, 각 문자의 경로를 따라 노드를 생성하고, 문자열의 끝을 나타내는 flag를 사용해 특정 단어가 저장되었음을 나타낸다.

Trie 기본 구조 (be,bee,can,cat,cd를 insert한 구조)

• Node : 개별 문자를 저장하고 여러 개의 자식 노드를 가질 수 있음
• Edge : 부모 노드와 자식 노드 간의 연결을 의미하고 특정 문자를 나타냄
• Root : 공백 상태이고 모든 문자열이 시작하는 Root(Node)
• Flag : 특정 노드가 하나의 단어의 끝임을 표시함

2. Trie 기본 연산

다음과 같은 연산을 지원한다.

Insert

기존 Trie 자료구조에 bed 단어 삽입

• 문자열을 Trie 자료구조에 추가할 때, 각 문자에 해당하는 노드를 따라가며 없는 경우 새로운 노드를 생성하며 추가한다.
• 문자열 끝을 표시하기 위해 마지막 노드에 단어 끝 Flag를 설정한다.

Search

• 루트에서 시작해서 주어진 문자열의 문자 하나씩 Node를 따라 이동한다.
• 마지막 문자의 노드가 존재하고, 단어 끝 Flag 설정 되어있으면 존재하는 단어로 판단한다.

3. Trie pros, cons

Pros

• 빠른 검색 : 길이가 L인 문자열 찾을 때 최악의 경우여도 O(L)의 시간이 소요된다.
• 공유 구조 활용 : 같은 prefix를 공유하는 문자열들이 노드를 공유하기에 중복 저장을 방지한다.
• 문자열 관련 연산 지원 : 자동 완성, 사전 구축, 패턴 매칭 등의 연산에 용이하다.

Cons

• 메모리 사용량이 큼 : 각 문자마다 노드가 필요하기 때문에 해시맵 기반 자료구조보다 메모리 사용 많이 할 수 있다.
• 구현 복잡성 : 단순 배열이나 해시맵보다 구현이 복잡하다.

Trie 예제코드 (class)

# Trie 자료구조
class Node(object):
    def __init__(self,key,data=None):
        self.key=key
        self.data=data
        self.child={}

class Trie(object):
    def __init__(self):
        self.head=Node(None) # key가 None인 Head 초기화

    def insert(self,string):
        curr_node=self.head # curr_node는 Node 클래스의 객체

        for char in string:
            if char not in curr_node.child: # string의 글자들이 child에 있는지 확인하기
                curr_node.child[char]=Node(char) # char 문자를 key로 가지는 노드 생성(curr_node의 child로)

            # curr_node의 child에 char가 있으면 해당 node로 이동!
            curr_node=curr_node.child[char]

        # 끝까지 이동한 이후 curr_node의 data에 string값 넣어줌
        curr_node.data=string

    def search(self,string):
        curr_node=self.head
        for char in string:
            if char in curr_node.child:
                curr_node=curr_node.child[char]
            else:
                return False
            
        if curr_node.data is not None: # 탐색이 모두 종료된 이후에 data에 값이 들어있으면 탐색 완료!
            return True
        else:
            return False
        

trie=Trie()

trie.insert('abc')
trie.insert('car')

print(trie.search('ab'))
print(trie.search('car'))