[자료구조] 래딕스 트리(Radix Tree) (기수 트리)

* radix tree 는 radix trie, compact prefix tree라고도 부른다 * 

 

radix tree역시 binary search tree를 알아야 한다. 

개인적으로는 red black tree 글을 작성하고 이 글을 작성했으므로 

red black tree 글을 먼저 보고 오는걸 추천한다. 

 

radix tree의 예시

 

 

radix tree는 binary search tree, red black tree처럼 왼쪽 < 자신 < 오른쪽 노드의 크기로 배치된다. 

그러나 radix tree는 트리의 균형을 맞추는 방식이 조금 다르다. 

 

red-black tree는 색상값 데이터를 가지고 노드를 좌우로 회전시키면서 균형을 맞췄다. 

그러나 radix tree는 이런 회전 작업 없이도, 키 값에 따라서 0이면 왼쪽, 1이면 오른쪽으로 노드를 배치해서 균형을 맞춘다고 한다. 

 

라딕스 트리는 어떤 index에 어떤 item을 저장하는 자료구조이다.

index의 bit를 이용해서 item을 찾아가는 방식으로 어찌보면 Hash와 Binary Tree와 비슷하다고 볼 수 있다.

 

 

활용

associative array( 연관 배열 : 키-값 형태로 되어 있는 배열. 예를 들면 map이나 dictionary )

IP routing

 

 

 

Trie를 공부하고 나서 볼 주제!!

 

+) 리눅스 4.20 버전부터는 xarray가 도입되어서 radix tree를 대체하고 있다고 한다. 

 

[출처]

 

https://siisee111.medium.com/radix-tree-분석-4902ff8169e4

https://m.blog.naver.com/namhong2001/221463525400