14장 트라이(Trie)[PYTHON]

목차
1. 트라이
2. 그림으로 이해
3. 코드 구현
4. 느낀점

트라이

트라이 자료구조는 문자열을 빠르고 쉽게 탐색하고 검색할 수 있게 해주는 자료구조이다.
입력되는 문자열을 트리 형태로 입력받아 저장한 후 탐색할 때 트리의 특징을 이용하여 탐색한다.
트라이 자료구조를 이용하면 길이가 M인 문자열이 들어왔을 때 검색하는 시간 복잡도는 O(M)으로 효율적이다.

그림으로 이해

즉, 트라이 자료구조를 이용하여 'ABC','ABDE', 'ACFKD'라는 문자열을 저장하면 다음과 같이 된다.

코드 구현

트라이를 코드로 구현하면 다음과 같다.

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

    def starts_with(self, prefix):
        current_node = self.head
        words = []

        for p in prefix:
            if p in current_node.children:
                current_node = current_node.children[p]
            else:
                return None

        current_node = [current_node]
        next_node = []
        while True:
            for node in current_node:
                if node.data:
                    words.append(node.data)
                next_node.extend(list(node.children.values()))
            if len(next_node) != 0:
                current_node = next_node
                next_node = []
            else:
                break

        return words

이 코드는 내가 구현한 코드는 아니다.
아직 나의 파이썬 지식이 부족해서일까 트라이 자료구조 구현 코드를 이해하기에는 부족한듯 하다.
다시 공부해본 뒤 나만의 코드로 다시 써볼 예정이다.
이 코드 출처는 다음과 같다.
파이썬 Trie 알고리즘

느낀점

개념자체는 어렵지 않은 것 같지만 코드를 구현하는 부분에 있어서 내가 너무 부족하다고 느꼈다.
class라는 개념에 더 익숙해지도록 노력해야겠다.