목록data structure (1)

Patrick's Devlog

[Algorithm] 트라이(Trie) 자료구조

1. 트라이탐색 트리의 일종이며, 동적 집합이나 연관 배열을 저장하는데 사용되는 트리 자료구조이다. 문자열을 저장하고 효율적으로 탐색하기 위한 자료구조로 생각하면 된다. 이진 탐색 트리와 달리 트리의 어떤 노드도 그 노드 자체와 연관된 키는 저장하지 않는다. 대신 노드가 트리에서 차지하는 위치가 연관된 키를 정의한다. 즉, 키의 값은 자료 구조 전체에 분산됨을 의미한다. 노드의 모든 자손은 노드에 연관된 문자열의 공통 접두사를 공유한다. 메모리에 최적화된 경우에는 기수 트리가 된다.   2. 장단점문자열 검색 시 빠른 검색 가능문자열 탐색 시 하나씩 전부 비교하는 것 보다 시간 복잡도 측면에서 효율적각 노드에서 자식들에 대한 포인터들을 배열로 모두 저장하고 있으므로 공간적인 측면(메모리)에서는 비효율적3..
Study/Algorithms & Data Structure 2024. 1. 30. 15:16
이전 Prev 1 Next 다음