#13 트라이(Trie) 구현

#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

from http://scala0114.tistory.com/141 by ccl(A) rewrite - 2021-10-25 17:01:02