트라이❓

트라이란 '각각의 노드가 배열로 이루어진 트리'다.

이렇게 '트리'형태의 자료 구조로 찾으면 걸리는 시간이 '문자열의 길이'에 의해 한정된다.

일반적인 영어 이름의 길이를 n이라고 했을때, 검색 시간은 O(n)이 되지만, 대부분의 이름은 그리 크지 않은 상수값이므로 O(1)이나 마찬가지라고 볼 수 있다.

트라이의 장점과 단점

장점 : 검색속도가 매우 빠르다.
단점 : 메모리 사용량이 매우 크다.