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 에, 내부(중간)노드는 분기노드