트라이
-
[Data Structure] 트라이알고리즘 & 자료구조 2021. 1. 25. 16:32
'트라이'는 기본적으로 ' 트리' 형태의 자료 구조이다. 특이한 점은 각 노드가 '배열'로 이루어져 있다는 것이다. 예를 들어 영어 알파벳으로 이루어진 문자열 값을 저장 한다고 하면 이 노드는 a부터 z까지의 값을 가지는 배열이 된다. 그리고 배열의 각 요소, 즉 알파벳은 다음 층의 노드(a-z배열)를 가리킨다. 아래 그림과 같이 Hermione, Harry, Hagrid 세 문자열을 트라이에 저장해보자 루트 노드를 시작으로 각 화살표가 가리키는 알파벳을 따라가면서 노드를 이어주면 된다. 단순히 문자열의 각 문자를 보며 트리를 탐색해나가기만 하면 되기때문에, 위와 같은 트라이에서 값을 검색하는데 걸리는 시간은 '문자열의 길이'에 의해 한정된다. 일반적인 영어 이름의 길이를 n이라고 할때, 검색 시간은 O..