[자료구조] 4-8. 트라이(Trie)

트라이란?

 

트라이는 문자열의 저장과 탐색을 효율적으로 하기 위한 k진 탐색 트리이다.

단어들이 공동으로 가지는 접두사들을 이용해서 문자열을 저장하고 탐색한다.

 

 

 

트라이의 특징

 

 

1. 트라이의 루트에는 빈 문자열을 나타내는 노드부터 시작한다. 루트 노드부서 시작해서 문자열의 접두사부터 따라가기 시작한다.

2. 각 노드는 문자와 자식 노드에 대한 포인터를 가지고 있다.

3. 종료 노드는 해당 문자열이 Trie에 존재함을 나타낸다.

4. 문자열 검색은 루트에서 시작하여 해당 문자열의 모든 문자를 따라 이동한다.(문자열의 접두사를 얻을 수 있다)

 

트라이의 시간복잡도는 O(n)(문자열의 길이만큼) 이다.트라이는 검색이나 사전 등에서 사용된다.

 

각 노드는 다음 자손의 포인터와 nil을 모두 포함하는 배열을 가지고 있다.

 

 

 

트라이의 탐색

문자열의 접두사부터 단계별로 탐색한다. 마지막으로 도착한 노드에서 단어의 끝에 온게 맞는지 확인한다.

DATA라는 문자열을 찾는다고 하면, D - A - T - A 순으로 탐색하고, 마지막으로 도착한 곳에서 문자열과 일치하는지 확인한다.

 

 

 

트라이의 삽입

 

트라이의 삽입 과정은 다음과 같다:

1. 순차적으로 탐색한다.

2. 더 탐색할 수 없다면, 남은 접두사들을 새로운 노드를 삽입해준다.

 

왼쪽 트리에 "TEAM"을 삽입하려면, T - E - A까지 탐색하고, 남은 E를 삽입해주면 된다.

 

 

 

트라이의 삭제

 

트라이의 삭제는 재귀적으로 발생한다:

1. 문자열의 마지막 노드에서 시작한다. 노드의 단어 여부를 False로 바꾼다.

2. 자식 노드가 있는지 확인한다.

3. 자식 노드가 있다면, 그 노드를 삭제할 수 없다. 삭제 과정을 끝낸다.(노드의 단어 여부만 비활성화하고 끝낸다).

    자식 노드가 없다면, 노드를 삭제한다그리고 부모 노드로 이동한다.

4. 2~3의 과정을 반복한다.

위 트라이에서 "DATE"를 없앤다고 하면, 맨 끝 노드인 E를 비활성화하고, 노드를 삭제할 수 있으니 없애준다.

그 뒤 부모노드인 T는 삭제할 수 없으므로 삭제 과정을 마친다.

 

이번에는 트라이에서 "TEA"를 삭제하는 과정이다. A를 삭제했다가는 TEAM도 쓸 수 없어지므로, A의 단어가 끝나는 여부만 삭제하여

"TEA"의 사용을 비활성화만 하고, 삭제 과정을 마친다.

 

Python 코드

class Node():
    def __init__(self):
        self.children = {}
        self.end = False

class Trie():
    def __init__(self):
        self.root = Node()
    
    def search(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                return False
            node = node.children[char]
        return node.end
    
    def insert(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = Node()
            node = node.children[char]
        node.end = True

    def delete(self, word):
        self.delete_helper(self.root, word, 0)

    def delete_helper(self, node, word, index):
        if index == len(word):
            if node.end:
                node.end = False
            return
        
        char = word[index]
        if char not in node.children:
            return
        
        child_node = node.children[char]
        self.delete_helper(child_node, word, index + 1)

        if not child_node.children and not child_node.end:
            del node.children[char]