Radix Tree (Patricia Trie)

Radix Tree (Patricia Trie)

Trie의 변형으로 단일 자식만 가진 노드를 압축하여 경로 압축(Path Compression)을 적용한 공간 효율적인 문자열 자료구조

목적: 공간 효율, 문자열 검색, Longest Prefix Match, IP 라우팅

특징: 경로 압축, 공간 효율, O(k) 연산(k=키 길이), 접두사 검색

경로 압축(Path Compression): 자식이 하나인 연속 노드를 하나로 합침

구조

• •간선에 단일 문자 대신 문자열(접두사) 저장
• •분기점에서만 노드 생성
• •노드 수 = 키 수 + 분기 수

연산

• •검색: 루트에서 키와 간선 레이블 매칭, O(k)
• •삽입: 매칭 실패 지점에서 노드 분할, O(k)
• •삭제: 노드 제거 후 단일 자식 노드 병합, O(k)

Longest Prefix Match: IP 라우팅에서 가장 긴 매칭 접두사 찾기

Linux Radix Tree: 커널의 페이지 캐시 관리, 정수 키 사용

장점: Trie보다 공간 효율, 빠른 Longest Prefix Match, 희소 데이터 효율

단점: 구현 복잡도, 노드 분할/병합 오버헤드, 갱신 비용

적용사례: IP 라우팅 테이블, Linux 커널, 문자열 사전, DNS 조회

비교: Radix Tree(압축/공간효율) vs Trie(비압축/단순) vs 해시(점검색)

연관: Trie, IP 라우팅, Longest Prefix Match, 커널 자료구조