Trie 나만의정리

Trie

• 트라이는 문자열 비교를 위해 필수적인 알고리즘이다. 특히 특정 긴 문장에서 임의의 단어를 찾기위해 효율적으로 쓰이는 자료구조이다.
• 문자열 비교를 할때 이진검색트리의 경우 한 레벨당 한문자씩 저장되므로 문자열의 최대길이 M을 곱한 시간복잡도 O(MlogN)이지만, 트라이를 이용할경우 O(M)의 시간복잡도를 갖는다.

아래는 Trie의 동작과정을 나타낸다.

chj, ckv, bq, ba의 문자열이 있다고 가정할때, 아래는 해당 문자열의 트리구조를 보여준다

Trie 코드

# 트라이 구조에 필요한 노드
class Node(object):
    def __init__(self, char, data=None):
        self.char = char
        self.data = data 
        self.children = {}

class Trie(object):
    # 노드가 필요할때마다 Node 클래스에서 새로운 Node를 생성
    def __init__(self):
        self.head = Node(None)

    # word의 모든 문자를 트리구조처럼 만드는 함수
    def add(self, word):
        cur_node = self.head
        for ch in word:                         # word는 내가 넣는 문자열
            if ch not in cur_node.children:          # cur에 문자가 존재x
                # 해당 노드에 다음 문자열이 없으면 등록한다.
                cur_node.children[ch] = Node(ch)
            # 다음 노드로 이동
            cur_node = cur_node.children[ch]

        # 단어의 마지막에 도달할때 data에 word를 할당
        cur_node.data = word

    # 만들어진 cur_node에서 단어를 찾기위한 함수 
    def search(self, word):
        cur_node = self.head                        # add 를 통해 만든 trie 구조를 담은 cur_node
        for ch in word:                             # 단어 한개씩 노드를 타고 내려감
            if ch in cur_node.children:             # 노드를 내려가다가 존재하면 해당 노드로 이동
                cur_node = cur_node.children[ch]    # 자식노드로 이동
            else:                                   # 없으면 False
                return False
        if (cur_node.data != None):                 # 맨 아래까지 도착하고, cur_node.data가 None이 아니라면 
            return True                             # return True