CS/DataStructure (1) 썸네일형 리스트형 트라이 ( Trie ) 자료구조 트라이 문자열에 특화된 자료구조이며, 문자열 집합을 표현하는 트리 자료구조이다. 우리가 원하는 원소를 O(n)으로 찾을 수 있다. 위 그림을 보면, blog를 예로 들 때, b, bl, blo, blog 순으로 트리에 저장되어 있는 것을 볼 수 있다. 이는 각각 blog의 접두사들이다. 이러한 이유들 때문에 트라이는 접두사 트리 ( Prefix Tree )라고도 불린다고 한다. 트라이 단점 트라이의 치명적 단점은 공간 복잡도다. 문자열에서 각각의 문자별로 하나의 노드가 필요한데, 예를 들어 알파벳 소문자 a~z가 포함되어있다면 기본적으로 26개의 포인터 배열을 가지고 있어야 하는 문제가 생긴다. 이렇게 되면, 최종 메모리는 ( 포인터 크기 * 포인터 배열 개수 * 트라이에 존재하는 총 노드의 개수 ) 가.. 이전 1 다음
