[자료구조] Trie 구조

Trie 자료구조에 대해서 설명드리겠습니다.

Trie란

• Trie는 문자열을 저장하고 효율적으로 검색하기 위해 사용되는 자료구조입니다.
• 트리구조로 되있으며 루트 노드부터 시작해서 자식들을 따라가면서 생성된 문자열들이 저장되있는 구조이다.
• 대신 저장된 문자열의 끝을 나타내는 변수가 필수이다.
• 사진에 나와있는 구조를 검색해보면 to, tea, ted, ten, A, i, in, inn 임을 알 수 있다.

좀 더 단순한 그림으로 본다면 다음과 같다.

구현

위키에 나와있는 파이썬 코드로 설명하겠습니다.

class Node:
   def __init__(self) -> None:
       # Note that using a dictionary for children (as in this implementation)
       # would not by default lexicographically sort the children, which is
       # required by the lexicographic sorting mentioned in the next section
       # (Sorting).
       self.children: Dict[str, Node] = {}  # mapping from character to Node
       self.value: Optional[Any] = None

children변수는 노드가 가지는 자식 노드이고 value는 현재 노드가 갖고 있는 문자열이라 생각하면 된다. terminal을 설정해서 마지막 문자열임을 설정해야 한다.

def find(node: Node, key: str) -> Optional[Any]:
    """Find value by key in node."""
    for char in key:
        if char in node.children:
            node = node.children[char]
        else:
            return None
    return node.value

Find는 입력 받은 key값이 존재한다면 그 노드를 리턴해주고 아니면 그 자식 노드로 들어간다.

def insert(node: Node, key: str, value: Any) -> None:
    """Insert key/value pair into node."""
    for char in key:
        if char not in node.children:
            node.children[char] = Node()
        node = node.children[char]
    node.value = value

삽입은 Terminal인지 확인하고 더 추가되면 터미널을 업데이트 하면 된다.

시간복잡도

Find는 키 문자열의 값을 반환하고 Insert은 키(문자열)와 값을 트라이에 삽입합니다. 삽입 및 찾기는 O ( m ) 시간으로 실행되며 , 여기서 m은 키(문자열)의 길이입니다.

사용 목적

trie의 일반적인 응용 프로그램은 휴대 전화 에서 발견되는 것과 같은 예측 텍스트 또는 자동 완성 사전을 저장하는 것입니다.

• 문자열을 탐색할 때
• 전화번호 탐색할 때 (중복 확인)

장점

• 한 트라이 내에서 키 충돌은 일어나지 않는다.
• 모든 검색과 삽입이 O(N) 으로 가능하다. (매우 빠르다.)
• 알파벳 순서로 항목을 제공할 수 있다.

단점

• 해시테이블 조회보다 느릴 수 있다.
  이 부분에 대해서 위키에 나와있는 말을 인용해본다면

  데이터가 하드 디스크 드라이브 또는 주 메모리에 비해 임의 액세스 시간이 높은 다른 보조 저장 장치에서 직접 액세스하는 경우에 느릴 수 있다.

• 이 외에도 의미가없는 긴 체인과 접두사를 초래할 수 있다는 단점도 존재하지만 크게 걱정 안해도 된다.

Reference

https://en.wikipedia.org/wiki/Trie

Summary

• 위키보고 해석하면서 한거라 제대로된 정보가 아닐 수 있습니다 ㅠㅠ
• 잘못된 정보는 댓글 달아주세요!