[ Open Data Structure ] - An Unbalanced Binary Search Tree (불균형 이진탐색트리) - 3

본격적으로 Binary Search Tree 중 Unbalanced Binary Search Tree를 살펴봅니다. Binary Search Tree의 Property는 Tree 내부의 어떤 데이터 x를 빠르게 특정해준다는 점에서 상당히 유용합니다. 그렇다면 바로 Tree 내부의 어떤 데이터 x를 찾는 코드를 살펴보도록 합니다. 그 전에 몇 가지 간단한 규칙부터 공부하는 편이 좋습니다.

여기서 x는 임의의 데이터를 가리키고 u는 임의의 node이며 u.x란 node u가 가진 데이터를 이릅니다.

1. 만약, x < u.x라면 탐색 과정은 u->left로 진행합니다.

2. 만약, x> u.x라면 탐색 과정은 u->right로 진행합니다.

3. 만약, x == u.x라면 데이터 x를 가진 node u를 찾아낸 것입니다.

만일, u == nullptr 이거나 3의 case에 해당하는 경우, Search Process는 끝납니다. 

Figure 4.1

특별히 이해하기 어려운 점은 없습니다. 기저를 이루는 아이디어는 모두 같기 때문에 필요에 따라 적당히 Return 값을 바꾸거나 Parameter를 통해 전달해주는 방식을 차용하면 됩니다.

Search Algorithm에서 찾고자 하는 값 x가 저장된 node u를 발견하지 못하더라도 Figure4.1은 상당히 유용한 정보를 제공해줍니다. 만일, Binary Tree에서 찾고자하는 값 x가 발견되지 않았다면 두 가지 경우를(x < u->x와 x > u-x) 추적하다보면, 각각 x보다 큰 가장 작은 값과 x보다 작은 가장 큰 값을 찾아낼 수 있다는 점입니다.

Figure 4.2

Addition

이제는 Binary Tree에 새로운 데이터 x 를 추가하는 과정입니다. 먼저, Tree를 쭉 탐색하며 내려가는 도중에 추가하려는 정보 x와 같은 정보가 존재한다면 Binary Tree에 구태여 무언갈 추가할 필요가 없습니다. 그러나 마지막 Leaf node에 도달했음에도 불구하고 추가하려는 정보 x를 발견하지 못했다면, Leaf node u가 가진 정보와 x를 비교하여 Left child에 추가할 지 Right Child에 추가할 지 결정을 내립니다. 원활한 구현을 위해 이 과정을 세 개의 함수로 나누어 표현합니다.

Figure 5.1

Figure 5.2

Figure 5.3

따로 기록할만한 내용은 없습니다. 작성된 코드를 천천히 따라가며 이해하면 좋습니다. Figure 5.2에 나타난 Return엔 두 가지 Case의 Return이 있는데 하나는 Binary Tree 내부에 추가하려는 정보 x가 존재할 경우 해당 Node를 반환하는 Case이고 다른 하나는 Leaf까지 내려갔음에도 불구하고 동일 정보를 찾을 수 없어서 nullptr바로 이전, 즉, Leaf node의 Pointer를 반환하는 Case입니다.

Removal

정보를 추가하는 것과 달리, 정보를 삭제하는 과정은 까다롭습니다. 만약 삭제하려는 정보를 담은 Node가 Leaf라면 할 일은 Leaf node를 떼어버리는 것 뿐입니다. 또한, 하나의 Child node를 가지는 Node를 삭제하는 것 역시 어렵지 않은데, 이는 Splice라는 Process를 거쳐서 해결할 수 있습니다. Splice의 내용은 Figure 6.1과 같습니다. 엉망진창 부끄러운 영어 주석은 이 Function이 하는 역할을 스스로 이해하기 위해 한땀한땀 박아넣은 것입니다.

Figure 6.1

이 Splice Function은 하나의 Child node를 가진 임의의 node u를 제거하고 child node를 u의 parent node에 이어준다고 보면 됩니다. 주의할 점이 하나 있는데, 이 Function은 반드시 하나 이하의 node를 가진 임의의 노드를 Parameter로 받는다는 점입니다. 첫 번째로 마주치는 IF STATEMENT에서 두 Children node가 모두 Nullptr일 경우에 혹시 잘못된 접근이라며 오류가 생길 것을 염려했지만 가장 마지막에 마주치는 IF STATEMENT를 확인해보면, Child node의 Pointer인 s가 nullptr인지 아닌지를 확인하기 때문에 nullptr가 다른 pointer를 가리키게 만들며 생기는 오류를 막았습니다.

앞서 기록한 것처럼 이 Splice Function은 두 개의 서로 다른 Children node를 가지는 임의의 노드 k를 Parameter로 받아야하기 때문에 먼저 처리해야 할 과정이 있습니다.

Figure 6.2

Binary Tree의 특징을 활용하여 두 개의 Subtree 또는 Children node를 가진 임의의 node u를 삭제하는 것이 가능합니다. 그것은 삭제하고자 하는 node u의 right subtree에서 가장 작은 노드 s의 값을 node u에 그대로 복사해 주고, 가장 작은 값을 가진 node s를 제거해버리는 것입니다. 그 과정이 else문 전체에 함축되어 있습니다. Right Subtree에서 가장 작은 값이기 때문에 최소한 Leaf node라는 것이 보장되기 때문에 Figure 6.1의 Prerequisition을 충분히 만족합니다.

또, Tree의 조건 덕분에 삭제하려는 임의의 node u의 right subtree의 모든 값들은 u의 left subtree의 값보다 무조건 큽니다. 그렇기 때문에 right subtree에서 가장 작은 값을 삭제하려는 node u의 자리에 갖다 놓는 것이 tree의 Property를 해치지 않는 것입니다.

Summary 

A. Binary Search Tree는 Sorted Set Interface와 Add(x), Remove(x), Search(x)의 operation을 O(n) time-per operation 내에 제공해줍니다. O(n)이라는 time-per operation은 상당히 실망스러운 부분이었는데, Binary Search Tree를 공부하는 내내 언급된 'Unbalanced'의 가능성 때문입니다. 물론, O(n)의 time-per operation을 O(logN)까지 떨어뜨려줄 수 있는 방법도 존재합니다. 천천히 공부해 나가도록 합니다.

B. Open Data Structures에선 이 과정을 Node와 Pointer를 활용했지만 Array를 활용한 접근도 충분히 가능합니다.

C. Node를 구성함에 있어서 Parent Pointer를 구현하지 않는 경우도 있으며 충분히 가능합니다. Parent Pointer는 추가적인 Memory Space 사용, Error발생의 위험 등이 단점으로 작용합니다. 반면에 Treversal에 있어서 재귀적인 Stack 사용을 피한다는 점, Parent node에 대한 정보가 부족함으로써 발생하는 Code 구현의 복잡성 회피 등의 장점이 있습니다. 상황에 따라 알맞는 구조를 채용하는 것도 능력입니다.

Full Source Code : github.com/HiddenWriter/UnbalancedBinarySearchTree.git