Trie 구조

# Trie 란?

 

- 문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료구조다.

- 검색할 때의 자동완성 기능, 사전 검색 등 문자열을 탐색하는 데 특화되어 있는 자료구조이다.

- retrieval tree 가 어원이며, radix tree, prefix tree 라고도 불린다. 

 

 

# 장단점

- 문자열 검색을 빠르게 한다. 

- 문자열 탐색을 할 때, 전부 비교하는 것보다 시간복잡도 측면에서 훨씬 더 효율적이다. 

- 각 노드에서 자식들에 대한 포인터들을 모두 저장하고 있다는 점에서, 메모리 측면에서는 비효율적이다. 

 

 

 

# 예제

 

1. 'abc' 에 삽입

• 초기에 트라이 자료구조 내에는 아무것도 없으므로 Head의 자식노드에 'a'를 추가해준다.
• 'a' 노드에도 현재 자식이 하나도 없으므로, 'a'의 자식노드에 'b'를 추가해준다.
• 'c'도 마찬가지로 'b'의 자식노드로 추가해준다.
• 'abc' 단어가 여기서 끝남을 알리기 위해 현재 노드에 abc 라고 표시한다. 

 

 

2. 'ab' 트라이 삽입

- 현재 Head 의 자식노드로 'a'가 이미 존재한다. 따라서 'a' 노드를 추가하지 않고, 기존에 있는 'a' 노드로 이동한다.

- 'b'도 'a'의 자식노드로 이미 존재하므로 'b' 노드로 이동한다.

- 'ab' 단어가 여기서 끝이므로 현재 노드에 ab를 표시한다. (Data)

 

 

3. 'car' 삽입

- Head의 자식노드로 'a'만 존재하고, 'c'는 존재하지 않는다. 따라서 'c'를 자식노드로 추가한다.

- 'c'의 자식노드가 없으므로 마찬가지로 'a'를 추가한다.

- 'a'의 자식노드가 없으므로 마찬가지로 'r'을 추가한다.

- 'car' 단어가 여기서 끝이므로 현재 노드에 car를 표시한다.

 

 

 

 

# 트라이 (Trie) 구현

먼저, Node 클래스를 아래와 같이 생성한다.

Node

- key 에는 해당 노드의 문자가 들어가고, child 에는 자식노드가 포함된다.
- data에는 문자열이 끝나는 위치를 알려주는 역할을 한다. 
    → 'car' 가 'r'에서 끝날 때, 'r'을 key로 가지는 노드의 data에 'car'을 입력한다.
- 해당 노드에서 끝나는 문자열이 없을 경우에는 그대로 None 으로 놔둔다.

class Node(object):
    def __init__(self, key, data=None):
        self.key = key
        self.data = data
        self.children = {}
        

 

 

두 번째, Dictionary 자료형을 이용하여 트라이(Trie)를 구현해보자.

class Node(object):
    def __init__(self, key, data=None):
        self.key = key
        self.data = data
        self.children = {}


class Trie(object):
    def __init__(self):
        self.head = Node(None)


    # 문자열 삽입
    def insert(self, string):
        cur_node = self.head

        # 삽입할 String 각각의 문자에 대해 자식 Node를 만들며 내려간다
        for char in string:
            # 자식 Node 들 중 같은 문자가 없으면 Node 새로 생성
            if char not in cur_node.children:
                cur_node.children[char] = Node(char)

            # 같은 문자가 있으면 노드를 따로 생성하지 않고, 해당 노드로 이동
            cur_node = cur_node.children[char]

        # 문자열이 끝난 지점의 노드의 data 값에 해당 문자열을 표시
        cur_node.data = string


    # 문자열이 존재하는지 탐색
    def search(self, string):
        # 가장 아래에 있는 노드에서부터 탐색을 시작한다.
        cur_node = self.head
        
        for char in string:
            if char in cur_node.children:
                cur_node = cur_node.children[char]
            else:
                return False
        
        # 탐색이 끝난 후에 해당 노드의 data 값이 존재한다면 문자가 있다는 뜻
        if cur_node.data is not None:
            return True

 

 

 

# 시간복잡도

- 제일 긴 문자열의 길이를 L이라고 하고, 총 문자열의 수를 M이라고 할 때, 

  생성 시간 복잡도는 O(M * L), 탐색 시간 복잡도는 O(L) 이다.