이진 트리 검색(Binary Tree Search), 기수 검색(Radix Tree, Radix Trie Search)

이진 트리 검색, 기수검색은 트리구조를 사용한다.
이때 사용되는 트리는 in-order 방식으로 이진트리 검색의 경우는 좌<부모<우 법칙에 따라 값이 담기고
기수검색시는 각 비트 자리에 있는 값에 따라 좌우측을(좌-0, 우-1) 취한다.
한가지 유념해서 볼 것은 밸런스를 맞추는 부분과 노드의 삽입, 삭제시 처리이다.
밸런스는 나중에 B 트리나 레드블랙트리 등에서 보다 심화되니 나중 포스트에서 핵심을 살펴보고
여기서는 삽입, 삭제 등 중요부분들에 대해서 정리해 본다. 

이진트리검색에서는 좌<부모<우 법칙에 따라 노드 삭제시 삭제노드의 왼쪽 서브트리에서 가장 큰 노드를  빈 자리에 채우거나
오른쪽 서브트리에서 가장 작은 노드를 빈 자리에 대체시킬 수 있는 두 원칙이 도출된다.
이 중 대다수 채택인 줄 모르겠으나 이재규 알고리즘 서적에서는 두번째 방식을 취하고 있다.
이것을 일반화된 하나의 원칙으로 삼고, 다시 실질적으로 쉽게 조작가능한 두 가지 경우를 추가하여
3가지 방식으로 나눠서 처리한다.

첫번째, 오른쪽 자식노드가 없을 경우 그냥 왼쪽 자식을 땡기기만 하면 좌<부모<우 법칙이 그냥 들어맞는다.
오른쪽 자식은 없으므로 걱정할 필요가 없다. 이런 쉬운 방법을 놔두고 일반화된 원칙에 따라 왼쪽 서브트리에서
가장 큰 값을 가진 노드를 찾아 대신한다면 얼마나 시간적 낭비겠는가....

두번째, 오른쪽 자식의 왼쪽 자식노드가 없는 경우 역시 오른쪽 자식을 땡기기만 하면 땡기는 부분의 왼쪽자식이 없으므로
그대로 트리는 유지된다. 역시 이 방법을 제껴 놓고 오른쪽 서브트리에서 가장 큰 작은 값을 가진 노드를 찾아서
빈 자리를 대신한다면 정말 쉬운 방법을 놔두고 아주 길게 가는 거다.

세번째, 그 외는 위의 일반 원칙에 따라서 오른쪽 서브트리에서 가장 작은 값을 가진 노드를 찾아 빈 자리를 메꾸는 방식이다.
이 경우가 오버헤드가 가장 크다. 트리 구조상 서브 트리 중 가장 좌측의 leaf 노드가 가장 작은 값을 가지므로 여기까지
내려와야 한다. 그리고 딜릿된 자리에 이 leaf 노드를 집어 넣으면 된다.
각 노드의 left, right 링크 처리는 그리 어렵지 않을 것이다.

위 설명들은 그림으로 보면 금방 파악되는 데 말로 하니 좀 길어진다. 그래도 말로 제대로 설명할 수 있어야
이해가 제대로 된 것 아닌가? ,,,

Radix Tree의 경우는 컴퓨터의 이진방식을 토대로
왼쪽을 0, 오른쪽을 1로 설정하여 트리구조를 취하는 방식이다.
LSB(하위자리)부터 비트값을 뽑아서 비교후 트리구조로 만든다.
이 것은 실질적으로 이진트리검색과 유사한 구조이다. 삽입 및 삭제 모두 유사하다.
(삭제시 위의 3경우로 나뉘는 것도 똑같다.)

Radix Trie의 경우는 위 Radix Tree에 조금 변형을 준 경우이다.
컴퓨터는 비트 연산을 매우 빠르게 처리하므로 이를 이용하여 leaf 노드에만 실질적 자료를 입력하고
(이를 정보노드라 한다. information node) 그 외 내부노드들은 링크만 주는 것이다.(이를 분기노드라 한다. branch node)
매 노드마다 값을 검사할 필요가 없이 비트연산으로 내부노드(분기노드)를 재빠르게 통과하고
마지막 leaf노드에 도달해서 값을 한 번만 비교하는 이점이 있다. 대신 n/2 가량의 분기노드만큼 메모리 공간이 더 필요하다.

Radix Trie의 경우 삽입과 삭제를 주의할 필요가 있다.

삽입의 경우 3가지의 가정이 도출된다.
첫번째, 가장 첫 요소 삽입의 경우 그냥 헤더와 연결시키면 된다.
두번째, 삽입하고자 하는 노드의 부모가 분기노드인 경우 고민할 필요도 없이 그냥 갖다 붙이면 된다.
세번째, 삽입하고자 하는 노드의 부모가 정보노드인 경우(이재규 알고리즘 서적에서 인용),,,
이 경우 표현이 좀 애매한 데,,, 부모이기보다는 삽입시 비트 비교를 통하여 말단인 정보노드까지 도달한 경우라고 함이
정확한 표현이라고 본다. 이 때는 양 요소 비트 비교를 통하여 공통되는 부분까지 계속 분기노드를 생성해주고
마침내 서로 갈리는 순간 비트 1인 것은 오른쪽에 비트 0인 것은 왼쪽에 위치시키면 된다.
(결국 형제노드가 되는 데 부모라고 하기에는 어감이 조금 이상하다... )

삭제의 경우 역시 유념해야 한다.
형제노드가 단순한 링크만 가진 분기노드인 경우와 정보노드인 경우로 나뉜다.

첫번째 형제가 분기노드인 경우 그냥 노드를 삭제하고 링크를 처리해 주면 된다.
옆 형제인 분기노드를 당겨 축소시키는 어리석은 짓을 해서는 안된다.
형제노드로 분기노드가 있는 상황은 그 분기노드 하위에 정보노드가 2개 이상이 있다는 소리이다.
 trie 알고리즘 원리상 이 경우 하위에 정보노드가 한 개 밖에 없는 구조는 있을 수가 없다.
(한 개이면 개념상 분기노드는 없고 그 자리에 그 정보노드가 위치하는 구조가 될 것이다.)
비트자리에 맞게 분기노드들와 정보노드들이 위치하는 상황에서 땡겨버리면 엉망이 될 것이다.

두번째, 형제노드가 정보노드인 경우는 분기노드의 축소가 가능하다. 왜냐면 형제노드가 없어지면
비교대상이 없는 마당에 굳이 아래까지 내려올 필요가 없기 때문이다. 불필요한 분기노드를 없애고 당겨주면 된다.
이 때 땡겨질 위치의 부모노드(CP)를 구하는 작업은 삭제노드 찾아 내려오는 과정에서 일거에 해결할 수 있다.
2개의 자식이 존재하고 그 자식 중 적어도 한쪽이 분기노드이면 조건이 충족될 것이다. 그 중에 가장 삭제된 노드와 가까운 위치를 찾으면 될 것이다. 즉 그 부모 이후로 내려올 때부터는 모두 외줄타기하는 분기노드이므로 땡길 수 있는 것이다.

참고로 위에서 땡겨질 부모노드 위치 구하는 조건식에서 2개의 자식이 모두 정보노드인 경우를 배제한 이유는,,,
먼저 삭제노드와 최단거리인,,, 2개의 정보노드를 자식들로 가진 노드는 현재 삭제될 노드의 부모이므로 고려대상이 아니고,,,
삭제노드와 연결되는 윗단계에서 정보노드가 2개라는 것은 당연히 개념상 존재할 수 없기 때문이다.
(정보노드는 말단 Leaf Node이므로 그보다 하위노드는 존재할 수 없다.)