[자료구조] 트라이(Trie) 이해🥵

🗃️트라이(Trie)

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

🗃️에시

👉“ab”, “abc”, “car”을 저장한다고 가정

• "abc"를 살펴보면 첫 번째 문자는 "a", 초기에 Trie 자료구조에는 아무것도 추가되지 않았으므로 Head의 자식 노드에 "a"를 넣는다.
• "a"의 자식 노드로 "b"를 추가한다.
• "b"의 자식 노드로 "c"를 추가한다.
• "ab"를 살펴보면 첫 번째 문자 "a"는 이미 존재한다. "b"노드로 이동하면 "b" 역시 존재하므로 끝
• "car"를 살펴보면 Head의 자식 노드는 현재 "a"만 있으므로 "c"를 자식 노드로 추가한다.
• "c"의 자식 노드가 없으므로 "a"를 자식 노드로 추가한다.
• "a"의 자식 노드가 없으므로 "r"를 자식 노드로 추가한다.

🗃️트라이 자료구조(딕셔너리 활용)

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

class Trie:
    def __init__(self):
        self.head = Node(None)
        
    def insert(self, string):
        curr = self.head
        for char in string:
            if char not in curr.children:
                curr.children[char] = Node(char)
            curr = curr.children[char]
        curr.data = string
    
    def search(self, string):
        curr = self.head
        for char in string:
            if char not in curr.children:
                return False
            else:
                curr = curr.children[char]
        if curr.data != None:
            return True