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

전에 첨부한 Figure 2.3의 Application Class의 Private엔 두 가지의 Member variable이 있었는데 하나는 Application을 다루기 위한 Integer type의 mCommand였으며 다른 하나는 An Unbalanced Binary Search Tree의 모든 Implementatios와 Root Node를 포함한 정보를 가진 데이터였습니다(Figure 3.1).

Figure 3.1

BinaryTree는 BinaryTree의 Implemetations를 포함한 Class입니다. 이 Class 안에는 마침내 Binary Search Tree의 Root node의 정보가 다음과 같이 들어 있습니다.

Figure 3.2

Figure 3.2에서처럼 Root node를 포인터로 선언했기 때문에 Class의 Constructor에서 Root node를 nullptr로 설정해주는 작업을 했습니다. mLength는 임의로 설정한 길이로써 Tree의 node개수를 나타냄과 동시에 최대로 포함할 수 있는 노드를 설정하였습니다. 없어도 그만, 있어도 그만인 듯 한데 안 만들 걸 그랬나 봅니다.

Recursive Algorithm으로 살펴본 몇 가지 Implementations입니다.

본격적으로 Unbalanced Binary Search Tree의 Implementations를 복습합니다. 다음은 간단하게 작성할 수 있지만 이해가 어려웠던 node의 개수를 구하는 코드입니다. 저는 멍청해서 눈에 안 보이면 이해하는데 남들보다 백 배는 오래 걸립니다.

Figure 3.3

꼴랑 몇 줄 되지도 않는 코드로 Tree에 주렁주렁 달린 Node의 개수를 구할 수 있습니다. 각 장단점이 분명한데, 장점은 구현이 빠르다는 점이고 단점은 만일, 한쪽으로 크게 치우친 Tree일 경우에 Stack을 너무 많이 사용하게 된다는 점입니다. 특히, 현재는 Tree의 구성 성분을 재배치 또는 재배열하지 않기 때문에 이런 사태가 발생할 가능성이 매우 높습니다.

Parameter인 (Node<SimpleData>* _u) 에서 Node는 전에 본 Figure2.2이며 SimpleData는 Figure 2.1입니다. _u는 나중에 볼 수 있겠지만 처음 이 Function을 호출할 때 Root node를 집어넣어 줍니다. 처음으로 재귀적인 호출이 들어가면 _u는 더 이상 root node로 이해하기 보다는 현재 점검하고 있는 node의 성격이 강해지게 됩니다. 그림으로 이해를 했으며 다양하게 활용이 될 수 있는 함수입니다.

본인은 7개의 Node를 가진 Tree를 그려보고 천천히 코드를 따라갔습니다. 결론적으로 현재 점검하고 있는 Node가 nullptr를 가리키고 있다면, 바로 직전에 호출된 Function의 Return의 1 +F( _u->left ) + F( _u->right )에서  F(left)든 F(right)든 0을 Return하게 됩니다. 따라서 임의의 Node k가 Leaf node라면 좌우 각각 0을 Return해오기 때문에 임의의 node k는 1 + 0 + 0을 Return하게 되고 이는 곧 자신의 Ancestor에게 Descendant가 자신 혼자 뿐이라는 슬픈 정보를 전달해주는 겁니다. 

다음은 Tree의 높이를 계산해주는 Recursive Algorithm입니다다. Tree의 높이에 대한 개념은 어렵지 않으니 적지 않겠습니다. 후에 복습하는 내가 아무리 멍청해도 이걸 잊지는 않았으리라 믿습니다.

Figure 3.4

else 부분의 Return이 줄이 넘어가버려서 가독성이 떨어져버렸지만 결론은 재귀적으로 호출한 각 두 함수의 최대값에 1을 더해 Return한다는 것입니다. 한 가지 흥미로운 점은 Figure 3.3의 코드와 상당히 유사하다는 점이었습니다. 높이는 Edge를 세는 것이기 때문에 Root는 0이 나오는 것이 맞습니다.

개인적으로 가장 중요하다고 생각되는 Traverse입니다. 여러 알고리즘 문제에서도 활용하기 좋으며 그래프를 순회하는 방법 중 하나라는 점에서 참 좋아합니다.

Figure 3.5

참 직관적이고 알기 쉬운 코드입니다. 현재 다루는 Tree는 각 Node의 Data가 작은 값을 좌측으로 몰아주기 때문에 Left부터 순회하도록 했습니다. 코드대로 따라가면 현재 점검 중인 Node _u가 Nullptr일 경우 순회를 중단하고 Return하도록 합니다. 이를 활용하면 각 Node의 Data를 출력하도록 사용할 수도 있을 것입니다.

Figure 3.3에서 생기는 문제는 Tree의 node가 한쪽으로 지나치게 몰려있으면 최악의 경우 높이 만큼의 Stack을 사용하게 된다는 단점을 이야기했습니다. 다음은 재귀적인 방법이 아니라, 현재 점검하고 있는 node, 점검을 하기전의 Node 그리고 다음에 점검할 노드, 이렇게 세 가지를 가지고 구현한 Traverse Function입니다. 

Figure 3.6

길고 재미없어 보이지만 사실 상당히 간단한 아이디어에 기반한 코드였다. "this->root"가 등장한 까닭은 이 코드가 BinaryTree Class 안에 들어있기 때문입니다. 앞서 적었듯 BinaryTree Class안에 Root Node가 있었습니다.

아이디어는 다음과 같습니다. 어떤 node u가 있다면, u->parent, u->left, u->right의 관계 속에서 u를 파악하고 다음 차례로 순회하는 것입니다.

1. 어떤 노드 u에 u->parent로부터 도착했다면, 다음 차례는 u->left다.

2. 어떤 노드 u에 u->left로부터 도착했다면, 다음 차례는 u->right다.

3. 어떤 노드 u에 u->right로부터 도착했다면, 이것은 u에 달린 모든 node(즉, Subtree)를 순회한 것이므로 u->parent로 이동한다.

Figure 3.6을 그대로 활용하여 Figure 3.3을 재귀적으로 함수를 호출하지 않고 같은 기능을 구현할 수 있습니다.

Figure 3.7

어떤 지점에서 임의의 노드 u에 방문을 끝마쳤는지 살펴볼 필요가 있습니다. 이는 다방면으로 활용이 가능할 것 같습니다.