← 질문 목록
#411깊이 0
트라이의 공간 복잡도 한계는 무엇인가?
자료구조 · 알고리즘심화
답변 연습
내 답변 적어보기접힘
이 브라우저에 자동 저장 · 0자
모범답안 확인하기내 답변 뒤에 열어보세요
문자 하나에 노드 하나를 쓰고, 노드마다 다음 글자로 가는 자리를 통째로 들고 있어서다. 담은 글자 수보다 훨씬 많은 공간을 쓴다.
뿌리
빈 문자열. 여기서 갈라진다
c
노드마다 다음 글자 자리를 통째로 들고 있다
a
문자 하나에 노드 하나가 또 생긴다
o
갈래마다 같은 크기의 자리가 붙는다
자식을 배열로 들면 노드 하나가 글자 종류만큼의 칸을 갖는다. 소문자만 26칸이고 한글이나 유니코드로 넓히면 그 수가 급히 커진다.
대부분의 칸이 빈다. 실제로 쓰는 갈래는 몇 개뿐인데 나머지는 자리만 차지한다. 단어가 짧고 겹치는 앞부분이 적을수록 낭비가 커진다.
줄이는 길이 있다. 자식을 배열 대신 해시나 정렬된 목록으로 들면 쓰는 갈래만큼만 차지한다. 대신 한 글자 옮겨 가는 비용이 올라간다.
갈래가 하나뿐인 구간을 접어 한 노드에 문자열로 담는 방법도 있다. 뒷부분이 길게 이어지는 자료에서 노드 수가 크게 준다.