Dot Algo∙ DS/자료구조
2021. 9. 8.
트라이(Trie) 문자열 탐색 트리 개념 정리 (Java)
트라이(Trie) 트라이(Trie)란 문자열의 집합을 표현하는 트리 자료 구조로, 문자열 특화 자료 구조의 대표적인 예이다. 트라이(Trie)를 왜 사용할까? 정수나 실수형 변수는 그 크기가 항상 정해져 있기 때문에 비교에 상수 시간O(1)이 걸린다고 가정해도 되는 반면, 문자열 변수는 비교하는 데는 최악의 경우 문자열의 길이에 비례하는 시간이 걸린다. 그렇기 때문에 정수나 실수 키에 대해서는 훌륭하게 동작하는 탐색 자료 구조들도 문자열을 키로 사용할 때는 시간이 너무 오래 걸릴 수 있다. 원소 간의 비교를 상수 시간에 할 수 있을 때는 N개의 원소를 갖는 이진 검색 트리에서 원하는 원소를 찾으려면 O(lgN)번의 비교를 할 수 있지만 문자열의 비교에는 그 길이에 비례하는 시간이 걸리므로 문자열 최대 길..
