컴퓨터의 두뇌인 CPU의 동작을 쪼개어 들어가 보면 결국 0과 1 즉 비트(bit)를 다루는 것을 기본으로 합니다. 컴퓨터에 저장된 모든 데이터는 비트의 배열로 구성됩니다. 하나의 바이트는 8개의 비트로 구성되며, 일반적인 정수형은 4개의 바이트 즉 32비트로 구성됩니다. 지금까지는 데이터를 수학적인 혹인 추상적인 개념으로서 취급했다면, 이 장에서 소개하는 기수 검색(Radix Search)은 데이터를 기본 단위인 비트의 배열로 취급합니다. 비트는 0과 1 두가지 값 밖에 없기 때문에 자연스럽게 자식을 두개 가질 수 있는 이진트리(Binary Tree)와 연결됩니다.
그래서 기수 검색은 이진트리 검색과 매우 유사합니다. 이 장에서 배울 기수 검색은 기수 트리(Radix Tree) 검색과 기수 트라이(Radix Trie) 검색 두가지 입니다. 트리와 트라이의 차이점은 정보가 중간 노드에 있을 수 있느냐 없느냐의 차이입니다.
전혀 다른 접근법으로 문제를 보는 예로서 기수 검색에 대해 찬찬히 살펴 보시기 바랍니다.
강의 자료
강의 동영상
17.0 기수 검색 - 시작 : 기수 검색은 검색 키의 비트 배열을 이용하여 검색하는 방법입니다. 어찌보면 이진트리 검색과 비슷하지만, 이진트리 검색의 단점인 불균형 문제를 자연스럽게 극복합니다.
17.1 기수 트리의 개념 : 기수 트리는 비트가 0이면 왼쪽, 1이면 오른쪽 자식으로 두는 간단한 규칙을 가지고 있습니다. 이런 규칙을 지키는 기수 트리의 삽입/삭제/검색 방법은 어떻게 되는지 알아봅니다.
17.2 기수 트리의 구현 : 앞서 기수 정렬에서 구현했던 bits 함수를 이용하면, 기수 검색도 쉽게 구현할 수 있습니다. 그 구현법을 알아봅니다.
17.3 기수 트라이의 개념 : 트리는 중간 노드에도 단말 노드에도 데이터가 존재합니다. 하지만 트라이는 단말 노드(Leaf Node)에만 데이터가 존재하는 특수한 트리를 의미합니다. 트라이라는 개념을 도입하면 비교는 단말 노드에서만 하면 되기 때문에 검색이 효율적입니다.
17.4 기수 트라이의 검색 : 기수 트라이의 검색은 매우 쉽습니다. 단말 노드가 아닌 경우 비트가 0이냐 1이냐에 따라 분기만 합니다. 단말 노드에 이르면 검색 키가 맞는지 한번만 비교하면 됩니다.
17.5 기수 트라이의 삽입 : 기수 트리의 경우 이진 트리 검색의 삽입/삭제와 동일한 로직이었습니다. 하지만 기수 트라이의 경우 검색은 간단하고 효율적이지만, 삽입과 삭제 로직이 복잡합니다. 삽입의 경우 부모가 분기 노드냐 정보 노드냐를 구분해야 합니다.
17.6 기수 트라이의 삭제 : 기수 트라이의 삭제는 형제 노드가 분기 노드냐 정보 노드냐를 구분해야 합니다. 다소 복잡하지만 찬찬히 들여다 보면 이해할 수 있습니다.
17.7 기수 검색의 비교 분석 : 기수 트리와 기수 트라이는 비슷한 듯 하지만 완전히 다릅니다. 이 둘의 차이점과 성능에 대해 알아봅니다. 흥미로운 것은 이 둘은 자동적으로 균형이 잡히는 이진트리라는 점입니다.
17.9 기수 검색 - 결론 : 기수 트리와 기수 트라이는 둘 다 키의 비트 배열을 이용하여 이진 트리를 구성하는 검색 구조입니다. 이진 트리여서 O(logN)의 성능을 보이지만 균형이 유지되는 트리라 매우 효율적입니다.
관련글 |
- C++로 배우는 알고리즘
- 16장 : 해쉬 (Hash)
- 18장 : B-트리 (B-Tree) 검색
댓글 없음:
댓글 쓰기