Radix Tree 기수검색 와 RadixTrie

이진트리 형태로 구성

왼쪽노드는 키가 0 오른쪽 노드는 키가 1

서브트리는 루트의 왼쪽 하위는 0 오른쪽은 1 => 이진검색트리 특성과 유사하다

-각 트리의 레벨의 수치에 대한 비트수치를 적용

-왼쪽부터 오른쪽으로 비트가 증가하는 형태

Degenerated case = 한쪽으로 트리가 쏠리는 현상

같은 키를 넣으면 허용 않함

검색할때 최 하위 비트부터 동일한 비트인쪽으로찾아 검색해간다

즉 비트가 검색키이다

노드 삭제는 이진검색트리와 동일하게 삭제

삽입은 레벨에 따른 비트 검사를 통해 leaf 로 이동하여 leaf 에 추가한다

하위비트부터 살펴봐서 비트가 0이면 왼쪽으로 그다음 비트가 또 0 이면 다시 왼쪽으로 그다음 비트가 1 이면 오른쪽으로 이동

---

분기노드 = 네모 점 데이터는 없다

비트에 따라서 좌우를 판단하는 것은 동일하다

그래서 자료의 입력 순서와는 무관하다

키의중복은 허용되지 않는다( 중복을 허용하려면 링크드리스트를 이용 )

트리의 높이는 log_2(8) + 1 = 4, [8 leaf 노드 수]

자료는 2^M 개 입력될 수 있다, [m 은 키의 비트 개수 = 3]

trie : 키 비교를 한번만 한다 => 키비교가 복잡할때 사용되면 유용

---

삽입은 이전 값과 차이나는 비트까지만 분기를 하면서 노드를 하단에 위치하게 한다

차이가 나는 비트의 노드가 들어올때 분기 노드를 만들면서 노드는 가장 하위에 유지되도록 한다

C++ 알고리즘 참고

---

트리의 높이만큼 비교, 검색 하기 때문에 O(logN) 의 성능을 가진다

성능이 좋다

Radix Tree => 모든 노드가 정보노드

Radix Trie => 정보노드는 leaf 에, 내부(중간)노드는 분기노드