Trie 구조
Trie 구조는 검색을 뜻하는 retrieval (검색)에서 딴 이름이다. 사실 발음할 때는 [트리]라고 해야 맞지만 tree 구조와 헷갈릴 수 있어 [트라이]라고 부른다고 한다. 의미처럼 검색을 위한 자료구조이다. 단어를 검색할 때 주로 사용되는 건 dictionary 구조인데, dict 구조는 한번의 검색으로 바로 찾을 수 있어 (O(1)) 시간 복잡도에 유리함을 가지고 있지만 공간 복잡도가 불리하다. Trie 구조는 dictionary의 공간 복잡도 문제까지 해결하면서 시간 복잡도도 적당히 좋다.
단어 carry, car, cat, dog, dust가 있다고 해보자. 이에 대한 trie 구조는 다음과 같이 만든다.
해당 문자가 나오지 않을 때까지 줄기를 타고 내려가면 된다. 그리고 해당 문자가 나오지 않으면 새로운 가지를 치면 된다. car와 carry을 보면 요소가 겹쳐있기 때문에 하나의 가지에 포함되어 있다. 하지만 위의 그림처럼 tree을 그리면 do라는 단어를 검색할 때, 단어가 있다고 판단할 수 있다. 그래서 단어가 끝났다는 것을 표시하는 마크가 필요하다.
알파벳 밑에 *가 True이면 그 알파벳이 단어의 끝이라는 뜻이다. 정리하면,
- 검색을 할 때 해당 단어가 있는지
- 단어의 맨 마지막 알파벳 아래에 *가 True 인지
이 두가지를 검사해야한다.
class Trie:
def __init__(self):
self.head = {}
# s는 들어갈 string
def add(self, s):
now = self.head
for ss in s:
if ss not in now: # string에서 해당 알파벳이 없는 경우 dictionary를 추가
now[ss] = {}
now = now[ss] # 최신화
now['*'] = True
def search(self, s):
now = self.head
for ss in s:
if ss not in now:
return False # 단어 안에 있는 단어를 따라가다가 없는게 나오면 return False
now = now[ss]
if '*' in now: # 경로에 있는 단어가 아닌 실제 있는 단어라면 return True
return True
else:
return False # 경로에 있는 단어인 경우 return False
> trie = Trie()
> trie.add("carry")
> trie.add("car")
> trie.add("dog")
> trie.search("carry")
True
> trie.search("car")
True
> trie.search("care")
False
> trie.head
{'c': {'a': {'r': {'*': True, 'r': {'y': {'*': True}}}}},
'd': {'o': {'g': {'*': True}}}}