[File System] ::트라이(trie)

키 탐색을 위해 키값을 직접 표현하지 않고 키를 구성하는 문자나 숫자의 순서로 키값을 표현한 자료구조

radix tree, prefix tree라고도 한다.

트라이는 m-진 트리이다. 그러나 m-원 탐색 트리는 아니다. 키값의 배열 순서가 M-원 탐색 트리 규칙과 다르기때문!

+M원 탐색 트리의 구조는 다음과 같다.

예를 들어서, 아래의 그림은 10-원 트라이 노드의 구조를 나타내고 있다.

노드 내에서 각 포인터 위치는 그 포인터의 위치에 대응하는 숫자 값을 나타낸다.트라이의 높이는 키 필드의 길이와 같다.

예를 들어서 아래와 같은 트라이가 있을때

P3은 키값이 2로 시작되는 모든 키값을 나타내는 서브트리를 가르키고있으며 P4는 23으로 시작하는 모든 키값을 나타낸다.

여기서 0은 공백 노드를 나타내는데 이러한 공백노드는 형식적으로만 존재하고 있다가 실제 키 값들이 삽입될 때 생성되는 것이다. 메모리를 효율적으로 활용하기 위해서이다.

삽입,삭제

노드의병합이나 분할이 일어나지 않고 리프노드부터 시작해서 레코드의 주소를 입력하여 삽입하고 삭제할때는 NULL값으로 변경해주면 된다. 보통 트라이에서 삭제를 하지 않는다고 한다.