화일 처리 및 응용 공부 #16 (트라이)

트라이(Trie)

키를 구성하는 문자나 숫자의 순서를 이용해 키 값을 검색하는 자료구조
- m 진 트리 이지만 m원 탐색 트리는 아님 : 키 값의 배열 순서가 다름
m진 트라이
- 차수 m : 키 값을 표현하기 위해 사용하는 문자의 수

- m진 트라이 : m개의 포인터를 표현하는 1차원 배열
10진 트라이의 노드 구조

트라이의 높이 = 키 필드의 길이
10진 트라이의 레벨 j의 포인터 pi는 j번째 에 숫자가 i인 모든 키값을 나타내는 서브트리를 가리킴
e.g 레벨 3에 있는 p4는 키값의 3번째 숫자가 4인 키값을 가진 서브트라이를 가리킴
키 값 : 루트 노드의 pi 에서 리프 노트의 pj 까지의 경로를 각 포인터에 대응하는 기수 원소로 표현
리프 노드에는 해당 키 값을 가진 레코드의 주소가 저장
키 검색 뿐만 아니라 키의 존재 유무를 빠르게 결정
트라이에서 널 포인터만 가지고 있는 공백노드는 생성 안함