[자료구조] 트라이(Trie)
·
Python 활용하기
트라이(Trie)란? 문자열을 빠르게 탐색할 수 있는 자료구조 길이가 L인 문자열을 이진탐색하면 O(LlogN)이지만, 트라이 구조를 활용하면 O(M)로 더 효율적이다. 트라이(Trie) 구현 Node 구현 key : 입력될 값 data : 문자열의 종료 표시 (문자열 전체) child : 자식 노드 class Node(object): def __init__(self, key, data=None): self.key = key self.data = data self.child = {} Trie 구현 class 초기화 비어있는 node 생성 class Trie: def __init__(self): self.head = Node(None) 삽입(insert) 구현 문자열을 한 글자씩 child에 저장하고, 마..