트라이(Trie)

트라이(Trie)

트라이(Trie)는 검색 트리의 일종으로 일반적으로 키가 문자열인, 동적 배열 또는 연관 배열을 저장하는 데 사용되는 정렬된 트리 자료구조

위의 그림은 문자열 ‘apple’, ‘appeal’, ‘appear’으로 트라이를 구성한 것이다.

만약 문자열 ‘apple’를 찾는 경우는 a-> ap -> app -> appl -> apple로 탐색된다.

이처럼 트라이에서는 각 문자열의 길이만큼만 탐색하면 원하는 결과를 찾을 수 있다.

시간복잡도는 O(문자열 길이)만큼 걸린다.

다만, 트라이의 단점은 공간 복잡도에 나타난다. 트라이는 다음 문자를 가리키는 노드가 필요하다.

그래서 숫자 트라이라면 0~9인 총 10개의 포인터, 영어인 경우는 a~z인 26개의 포인터 배열이 필요하다.

즉, 최종 메모리는 O(포인터 크기 * 포인터 배열 개수 * 트라이에 존재하는 총 노드의 개수)이다.