zeomzzz

zeomzzz의 TIL


Trie


Trie란?


  • 문자열 검색을 빠르게 해주는 트리 구조
  • 정수형 자료에 대해 이진트리로 검색하면 O(log n)이지만 문자열을 검색하면 문자열 최대 길이가 M일 때, O(M log n)
    • 노드에 들어가서 매번 문자열의 길이만큼 비교해야 함
  • 문자열 한 자가 한 노드에 가도록 저장
  • 빠르게 탐색 가능하지만 각 노드에서 자식들에 대한 포인터들을 배열로 모두 저장하고 있어서 저장 공간의 크기가 큼
  • 활용 : 자동 완성 및 검색어 추천



시간복잡도


가장 긴 문자열의 길이가 m, 문자열의 개수 n일 때

  • 생성 : O(m*n)
  • 삽입 : O(m)
  • 검색 : O(m)



구현


  • Node를 이용한 Tree 형태
  • 문자열의 끝임을 알려주는 flag 존재


1) Node

class Node(object):
    def __init__(self, key, data=None):
        self.key = key # 노드에 입력할 문자 (값)
        self.data = data # 문자열의 종료를 알리는 flag
        self.children = {} # 자식 노드


2) Trie

class Trie:
    # 빈 노드를 헤드로 초기화
    def __init__(self):
        self.head = Node(None)

    # insert : 트리 생성
    def insert(self, string):
        cur_node = self.head # head에서 시작
        
        for char in string: # 문자열의 문자를 하나씩 확인
            # 현재 노드의 자식 중에 문자가 없다면 자식 노드에 추가
            if char not in current_node.children:
                cur_node.children[char] = Node(char)
            # 자식 중에 있다면 cur_node를 자식 노드로 변경
            cur_node = cur_node.children[char]
        
        # 문자열을 끝까지 탐색했다면 마지막 노드에 data추가
        cur_node.data = string
    
    # string 검색
    def search(self, string):
        cur_node = self.head # head에서 시작
        
        for char in string : # 문자열의 문자를 하나씩 확인
            # 현재 노드의 자식 중 문자에 해당하는 노드가 존재한다면 cur_node를 자식 노드로 변경
            if char in cur_node.children:
                cur_node = cur_node.children[char]
            # 현재 노드의 자식 중 문자에 해당하는 노드가 없다면 False
            else:
                return False
        # 문자열 끝까지 탐색하여 마지막 노드에 데이터가 존재한다면 True
        if cur_node.data :
            return True
        # 문자열 끝까지 탐색하여 마지막 노드에 데이터가 없다면 False
        else:
            return False



관련 문제



참고 자료




Leave a comment

You may also enjoy