외부 탐색

목차

없음

본문내용

예를 들어, 5480명의 고용인을 가진 회사가 있어서 13자리의 주민 등록 번호(10진수)를 고용인 월급 레코드에 대한 키 필드로 사용된다고 가정한다. 이 키필드를 사용하여 구축된 트라이는 13개의 레벨과 단말 노드 레벨에서 1013의 요소(0.0000000548%)만이 사용된다.따라서 이런 경우에는 주민 등록 번호처럼 자릿수가 큰 것을 키 필드로 사용하지 말고 5480 ≤ 10n을 만족하는 n을 구해 자릿수가 n인 10진수를 사원 번호로 정하는 것이 효율적이다. 이 예의 경우에는 네 자리 사원 번호가 적절하겠다.
트라이에서 키 값의 삭제는 해당 노드를 찾아가 널 값으로 요소를 변경시키면 된다. 또한, 앞에서 배운 B-트리와 그 변형 트리들이 노드 분리화 노드결합이 필요한 반면에, 트라이의 경우는 노드의 분리나 결합이 불필요하다는 점이 큰 특징이다.
기본 트라이에서 몇 개의 가능한 변형 형태가 있다. 예를 들어, 트라이는 가변 길이 키 필드를 보다 더 효율적으로 다루기 위해 변경될 수 있다. 사람의 이름(미국 사람인 경우)을 키 필드로 갖는 경우를 생각해 보자. 어떤 사람의 이름은 짧고 어떤 사람의 이름을 길게 될 것이다. 만약 30자리의 이름을 26-원 트라이로 구축한다면 비록 짧은 이름일지라도 30번의 노드방문이 필요하게 된다. 이름 중의80%가 8문자를 넘어서지 않는다고 가정하면 트라이는 다음과 같은 노드 구조로 구축될수 있다.
각 내부 노드는 27개의 요소를 가질 수 있다. 26개의 글자는 영문자이면 나머지 하나(ら)는 표현되는 이름의 끝을 나타낸다. 즉,각 이름은 하나로 ら로 끝나게 된다. 예를 들어 ,IGOR 는 IGORら로 표현된다. 레벨 l에서 ら로 끝마치는 이름은 l개의 문자로 구성된 이름이다. 예를 들어, 이름 IGOR는 레벨 0에서 I가 표현되고 이는 레벨 1의 G를 가리키며 계속하여 레벨 2의 O,레벨 3의 R을 가리키고 마지막으로 레벨 4의 ら를 가리키게 된다.
따라서 이 27-원 트라이는 이름의 80%가 최대 8자릿수로 표현된다고 가정했으므로 8-레벨로 구축될수 있다. 보조 인덱스는 8자리보다 큰 이름에 대한 나머지 자리를 가리키게 된다. 그러므로 탐색의 80%가 최대 8번의 노드 방문이 필요하며 탐색의 20%가 전체 트라이와 다른 보조 인텍스를 방문하게 된다.
트라이의 기억 공간을 효율적으로 사용하는 또 다른 방법은 각 노드에서 가능한 기저를 모두 다 표현하지는 않도록 함으로써 노드 크기를 줄이는 것이다. 대신에 실제로 사용되는 값들만 표현되게 한다. 그림4.31은 3글자짜리 소년들의 이름을 저장하는데 이 방법을 사용한 것이다.

참고 자료

없음