prefix tree1 [Python] Trie 자료구조 Trie(트라이) 자료구조는 문자열 집합에서 키를 효율적으로 저장하고 조회하는데 사용된다. 스펠 체커나 자동완성 기능에서 사용된다. 파이썬에서는 딕셔너리 자료구조를 이용해 쉽게 구현할 수 있다. insert (단어 삽입) 단어의 키(문자)가 커서에 존재하지 않는 경우 해당 키로 딕셔너리를 생성하고, 커서 위치를 업데이트 해준다. 단어 삽입이 완료되면 * 키를 생성해서 끝임을 표기한다. search (단어 조회) 단어의 키(문자)가 커서에 존재하지 않는 경우 False를 반환하고, 커서 위치를 업데이트 해준다. 단어 순회가 완료되었을 때 * 키가 커서에 있을 경우 True를 반환하고 없을 경우 False를 반환한다. startswith (접두어 조회) 단어의 키(문자)가 커서에 존재하지 않는 경우 Fals.. 2021. 10. 10. 이전 1 다음 728x90 반응형