트라이

트라이

[출처] : https://www.medianet.cs.kent.edu/surveys/IAD06S-p2psearch-alok/index.html

트라이(Trie), ‘접두어 트리’로 불리며
일련의 ‘키-값’을 저장하는 트리 기반 자료구조이다

‘N진 트리’의 방식이며,
‘문자열 검색’에서 유용한 시간 복잡도를 제공한다

• 사전, 자동완성 및 검색 엔진 등에 아주 유용하다
• 노드의 ‘위치’ 자체가 ‘키’를 정의
• 노드가 ‘키’의 모든 데이터를 저장하진 않음

해시 테이블 대신 고려가 가능한 알고리즘
-> 충돌이 없으며, ‘최악’의 경우에 더 빠르다
(최악 hash : O(n)(n은 데이터의 길이),
최악 trie : O(k)(k는 key의 길이))

다만 유의할 점은

• 메모리를 많이 차지한다(탐색 속도가 빠른 대가)
• 평균 O(1)은 아닌 점은 유의
• ‘key’값으로 사용하기 어려운 데이터형 존재 (ex : float)

작동 방식

• 검색 : 루트노드부터, ‘키’의 문자를 나타내는 노드로
  이동하며, 검색 중인 ‘키’를 찾을때까지 반복
  -> 시간복잡도는 O(K) (K : ‘키’의 길이)

• 삽입,삭제 : 해당하는 위치로 이동하여 삭제,삽입 -> 시간복잡도는 O(K) (K : ‘키’의 길이)

• 생성(모든 문자열 넣기) : 모든 문자열을 n, k를 가장 긴 문자열 길이라
  하면 O(kn)

예시 코드(Python)

from typing import Any,Type

class Node():
    # 일단 Any를 사용하였지만, Key에 float 같은걸 집어넣긴...
    def __init__(self,key : Any,data : Any = None) -> None:
        self.key = key
        self.data = data
        # n진 트리이기에, 자식으로 들어올 '문자'를 저장하기 위함
        # dict 사용
        self.children = {}

# 문자열 용도로 작성
class Trie():
    def __init__(self) -> None:
        self.root = Node(None) # head라고 표현할 수도

    # 문자열 삽입
    def insert(self,string):
        curr_node = self.root

        # string 각각의 문자에 대해 자식 Node를 따라가거나 만들어가며 내려감
        for char in string:
            # 자식 Node 중 같은 문자가 없으면 Node 새로 생성
            if char not in curr_node.children:
                curr_node.children[char] = Node(char)
            
            # 해당하는 Node로 이동
            curr_node = curr_node.children[char]
        
        # 문자열이 끝난 지점의 노드의 data 값에 해당 문자열 표시하기
        curr_node.data = string

    # 문자열 탐색
    def search(self,string):
        curr_node = self.root

        # 검색중
        for char in string:
            if char in curr_node.children:
                # 있다면 그 자식으로
                curr_node = curr_node.children[char]
            else: # 없네?
                return False
            
        # 데이터 비워져있다면 false
        if curr_node is None:
            return False
        
        return True