트라이
-
[자료구조] 트라이Stage/Computer Science 2021. 6. 2. 18:59
학습 목표 트라이의 원리와 구조를 설명할 수 있다. 왜? 문자열의 길이가 일정한 경우 이 문자열들을 저장하고 관리하는 데 최적의 자료 구조는 무엇일까? 연결 리스트, 트리, 해시 테이블이 최선의 방안이 될 수 있을까? 이번엔 트라이라는 자료 구조에 대해 알아보자. 1. 트라이? 트라이는 retrieval의 약자로, 기본적으로 트리형태의 자료 구조이고, 문자열을 빠르게 탐색하게 해주는 자료구조이다. 즉 문자열 탐색에 특화된 자료구조이다. 특이한 점은 각 노드가 배열로 이루어져있다는 것이다. 예를 들어 알파벳으로 이루어진 문자열 값을 저장한다고 한다면, 이 노드는 a부터 z까지의 값을 가지는 배열이 된다. 그리고 이 알파벳은 다음 층의 노드(a~z까지의 배열)를 가리킨다. Hermione, Harry, Ha..