트라이

트라이란

 트라이란 문자열 검색을 빠르게 할 수 있는 자료구조 입니다. 문자열을 특정 키 값으로 변환해서 그 값으로 찾는 방법인 해시 테이블을 대체하기 위해 트라이를 사용할 수 있습니다. 불완전한 해시 테이블의 최악 검색 속도는 모든 데이터를 다 확인하는 것이지만 트라이를 사용하게 되면 문자열 길이 만큼의 속도가 걸리기 때문에 훨씬 더 빠르게 적용이 될 수 있습니다.

 보통 트라이를 사용할 때 고려해야할 점은 단어의 길이와 파생되는 Child 노드의 개수입니다. 영어 사전을 예로 들자면, 영어는 알파벳이 26가지이기 때문에 Child 노드는 26개를 가지고 있을 수 있습니다. 전화번호 목록 같은 경우도 0부터 9가지 10가지의 수를 가지고 있을 수 있습니다. 이처럼 적은 Child 노드를 가지고 있는 데이터 구조일 경우에 사용하는 것이 유용합니다. 만약 차수가 크고 단어 길이가 길면 그 만큼 메모리 낭비가 많고 검색 속도가 느려질 수 있습니다.

참조: https://meylady.tistory.com/23