#13 트라이(Trie) 구현

1. ADT 작성

Trie:
    Datas:
        __root : 트리의 루트노드
        __size : 트리의 크기

    Operations:
        insert(string) : 문자열 string 을 트라이에 삽입
        find(string) : 문자열 string이 트라이에 들어있다면 True, 아니라면 False 반환
        
Trie.__Node:
    Datas:
    	is_term : 해당 노드가 문자열의 마지막 문자를 나타내는지 여부
        next : 연결된 다음 문자 노드 리스트.  next[ord(key) - ord('a')] 가 None 이 아니라면
               다음 문자가 key인 문자열이 Trie 내에 존재한다는 의미가 된다.

    Operations:
    	get(key) : 문자 key 에 해당하는 다음 문자 노드를 반환
        set(key) : 문자 key 에 해당하는 다음 문자 노드를 설정

 

 

2. 구현 

class Trie:
    # 트라이의 노드 클래스
    class __Node:
        def __init__(self, is_term=False):
            self.next = [None] * 26
            self.is_term = is_term

        # key 에 해당하는 다음 문자 노드를 반환
        def get(self, key):
            return self.next[ord(key) - ord('a')]

        # key 에 해당하는 다음 문자 노드를 설정
        def set(self, key, node):
            self.next[ord(key) - ord('a')] = node

    def __init__(self):
        # 루트 노드
        self.__root = self.__Node()
        
        # 트라이의 크기
        self.__size = 0

    def __len__(self):
        return self.__size

    # 문자열 삽입
    def insert(self, string: str):
        # 루트 노드에서 탐색 시작
        cur = self.__root

        # 삽입할 문자열의 모든 문자를 소문자로 변환
        for c in string.lower():
            nxt = cur.get(c)
            # 문자 c에 해당하는 노드가 없다면 생성
            if not nxt:
                nxt = self.__Node()
                cur.set(c, nxt)

            # 문자 c에 해당하는 노드로 이동
            cur = nxt

        # 기존에 없었던 문자열이라면
        if not cur.is_term:
            # 문자열의 마지막 문자에 해당하는 노드에 is_term 값을 True 로 설정
            cur.is_term = True
        
            # 트리의 크기 1 증가
            self.__size += 1

    # 문자열 탐색
    def find(self, string):
        return True if self.__search(string) else False

    # 문자열의 마지막 문자에 해당하는 노드를 찾아 반환
    def __search(self, string: str):
        cur = self.__root
        for c in string.lower():
            cur = cur.get(c)
            if not cur:
                return None
        if cur.is_term:
            return cur
        return None