이 글은 gogaegaebal, 코딩하는 지미님 블로그를 참고해 작성되었습니다. 사진을 누르면 각 사진의 출처로 이동합니다.

트라이

• 문자열을 트리 형식으로 만들어 진행되며 이진탐색 트리와 비슷한 원리로 진행되기 때문에 빠르게 문자열 검색이 가능한 자료구조이다.
• 문자 하나씩을 기준으로 트리의 자식으로 내려가며 탐색한다.
• 소요되는 시간은 O(m)이다. m은 문자열의 길이
• 자동완성, 검색어 추천 기능에 많이 사용된다.

코드구현

노드

class Node(object):
    def __init__(self, key, data=None):
        self.key=key        # 문자
        self.data=data      # 단말노드인 경우 문자저장
        self.children={}    # 자식노드

트라이

class Trie:
    # 트라이 초기화
    def __init__(self):
        self.head=Node(None)

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

        for char in string:
            if char not in current_node.children:
                current_node.children[char] = Node(char)
            current_node = current_node.children[char]
        current_node.data=string

    # 문자열 검색
    def search(self, string):
        current_node=self.head

        for char in string:
            if char in current_node.children:
                current_node = current_node.children[char]
            else:
                return False

        # 마지막까지 탐색했을때 그 단어가 단말노드면
        if current_node.data:
            return True
        else:
            return False

추천문제
BOJ 5052번 전화번호 목록