7 - 트라이 (trie) 자료구조

트라이(Trie)

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

• 트라이는 자동완성, 사전 찾기 등 문자열을 탐색하는 문제에 자주 사용된다.

• 문자열을 탐색할때 시간복잡도 측면에서 보다 효율적으로 찾을 수 있다.

  • 보통 문자열 탐색은 문자열의 갯수 * 각 문자열의 길이 만큼의 시간복잡도를 가지는데 트라이를 사용하면 찾는 문자열의 길이 즉 O(L) 만큼의 시간복잡도를 가진다.

• 따라서 빠르게 탐색할 수 있다는 장점이 있지만 각 노드가 자식에 대한 링크를 모두 저장해야 하기때문에 공간복잡도 측면에서는 비효율적이다.
  
  

트라이의 구조

• "abc" 를 추가해보자
  • 초기 trie 자료구조는 비어있는 상태이므로 head의 자식노드에 "a"를 추가한다.
  • "a"의 자식노드에 "b"를 추가한다.
  • "b"의 자식노드는 비어있기 때문에 "c"를 자식노드에 추가한다.
  • 모두 추가가 되면 마지막 노드에 "abc"를 표시한다.
    
    
• "ab" 를 추가해보자
  • head의 자식노드에 "a"가 이미 존재하기 때문에 생성하지 않고 "a"노드로 이동한다.
  • "b"노드로 이동한다.
  • 마지막 노드에 "ab"를 표시한다.
    
    
• "car" 를 추가해보자
  • head의 자식노드에 "c"는 존재하지 않기 때문에 자식노드에 "c"를 추가한다.
  • "c"의 자식노드에 "a"를 추가한다.
  • "a"의 자식노드에 "r"를 추가한다.
  • 마지막 노드에 "car"를 표시한다.

파이썬으로 트라이 구현해보기

• 초기 비어있는 트라이 자료구조
  
  
• "abc" 추가
  
  
• "ab" 추가
  
  
• "car" 추가
  
  

class Node:
    def __init__(self, data = ""):
        # self.key = key
        self.data = data
        self.children = {}
        
class Trie:
    def __init__(self):
        self.head = Node()
        
    def insert(self, string):
        curr_node = self.head
        
        for char in string:
            # 자식 node에 해당 문자가 없으면 새로운 node생성
            if char not in curr_node.children:
                curr_node.children[char] = Node(char)
            # 자식 node에 있으면 이동
            curr_node = curr_node.children[char]
        # 문자열이 끝난 지점의 노드의 data 값에 해당 문자열을 입력
        curr_node.data = string
        
    def check(self, string):
        curr_node = self.head
        
        for char in string:
            if char not in curr_node.children:
                return False
            curr_node = curr_node.children[char]
        
        if curr_node.data:
            return True

출처
youseop.github.io