Radix Tree

정의

컴퓨터 과학에서 기수 트리 (기수 트리 또는 컴팩트 접두사 트리 또는 압축 트리)는 유일한 자식인 각 노드가 부모와 병합되는 공간 최적화 트리(접두사 트리) 를 나타내는 데이터 구조입니다. 결과는 모든 내부 노드의 자식 수는 기수 트리의 기수 r입니다. 여기서 r은 양의 정수이고 x의 거듭제곱은 x입니다. 일반 트리와 달리 가장자리는 단일 요소뿐만 아니라 요소 시퀀스로 레이블을 지정할 수 있습니다. 이것은 작은 집합(특히 문자열이 긴 경우)과 긴 접두사를 공유하는 문자열 집합에 대해 기수 트리를 훨씬 더 효율적으로 만듭니다.

from wiki

특징

• 노드의 레벨에 해당하는 비트의 값에 따라 0은 왼쪽 자식, 1은 오른쪽 자식으로 배치한다.
• 키의 디지털 특성을 이용하여 Degenerated case를 회피한다.
• 키의 중복이 허용되지 않는다.
• 키의 비트 수가 M이라면,
  • 자료는 2m개 들어갈 수 있다.
  • 트리의 높이는 최대 M+1이다.

매크로

삽입

• 레벨에 따른 비트 검사를 통해 Leaf로 이동한다.
• 새로운 노드는 Leaf에 추가한다.

검색

• 검색 키의 비트 검사를 통해 노드를 탐색한다.

삭제

• 삭제 키의 비트 검사를 통해 노드를 탐색 한다.
• 세 가지의 경우로 나누어 노드를 삭제 한다. (이진탐색트리와 동일)
  • 오른쪽 자식이 없을 때
  • 오른쪽 자식의 왼쪽 자식이 없을 때
  • 그 외의 경우

예제

• 백준 5670