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

그래프의 일종이며 기본적인 형태는 다음과 같습니다. 이는 Computer Science(CS)의 가장 기초를 이루는 구조 중 하나입니다. Tree라는 이름이 붙은 이유는 자료의 구조를 설명하기 위해 그림을 그리면 종종 나무와 나뭇가지를 닮은 구조를 얻을 수 있기 때문입니다. 수학적으로 이 구조를 정의하면 다음과 같습니다.

A binary tree is a connected, undirected, finite graph with no cycles, and no vertex of degree greater than three.

각 Vertex(정점 또는 꼭지점)는 세 개 미만의 연결을 가지고 연결되어 있습니다. 또, Graph theory에서 Cycle이란 Simple Circuit이라고도 하는데 어떤 경로 상에서 반복되어 나타나는 vertex가 원점뿐인 Vertex의 집합을 말합니다.

Figure 1.1

Binary Tree는 너무 중요해서 Terminology가 따로 있을 정도입니다. 가장 상단에 Root Node가 존재하면 좌우로는 각각 좌측하단에 RootNode보다 작은 어떤 값, 우측엔 큰 값을 배치합니다. Figure1.2는 각 노드들의 일반적인 명칭입니다. Parent Node는 하나의 Child Node를 가지거나 아예 없거나, 두 개의 Children을 가질 수 있습니다. 특히, 아무런 children을 가지지 않는 노드에 대해 Leaf Node라는 이름을 붙이도록 했습니다. Figure 1.2에 나타나지는 않았으나 Leaf노드가 아닌 Node에 대해서는 별도로 Internal Node라는 명칭을 사용하기도 합니다.

Figure 1.2

또, tree의 root node를 r이라고 하고 u에서 r로 가는 경로 상에 w가 있는 상황을 가정하도록 합니다. 이 경우에 우리는 w를 Ancestor of u(u의 조상)라고 하고 w를 Descendant of w(w의 후손)라고 합니다.

Depth라는 표현을 마주할 때가 종종 있을 텐데 가령 Node u의 depth라는 표현은 root node r로부터 node u가지의 path를 이르는 말이며 path는 그래프 이론에서 Edge를 일컫는 말이니 노드 간의 Edge의 수를 말하는 겁니다. Figure 1.2에서 Leaf node라고 적인 node의 depth는 그럼 2가 됩니다. Height라는 표현도 Depth라는 표현과 비슷하기 때문에 개념적으로 차이가 없다고 느낄 수 있지만 미묘한 차이가 있습니다. 예를 들어서 Node w의 Height는 root node부터 w의 Descendant node까지 가장 긴 Path를 일컫는 말입니다.

An unbalanced binary search tree를 구현함에 있어서 다양한 방법을 사용할 수 있겠지만 여기서는 포인터를 사용하여 구현하기로 합니다. 본격적으로 Binary Search Tree를 구현하기에 앞서서 완성된 Binary search tree를 간편하게 다룰 수 있도록 총 세 가지 사전 작업을 하도록 합니다. 실은, 구태여 구현할 필요가 전혀 없는 것도 포함되어 있으나, 향후에 테스트를 편하게 해보기 위해서는 사전에 작은 수고를 들이는 것도 나쁜 방법이 아니라고 생각합니다. 첫 째로 node에 저장할 간단한 데이터를 만들었습니다.

이 데이터에는 ID(나중에 데이터의 대소를 비교하는데 주로 사용될 값)와 이름(별 기능은 없습니다.)이 포함되어 있습니다. 또한, 대소비교를 단순히 operator로 실시하기 위해서 필요한 operator overloading을 간단하게 해두었습니다.

Figure 2.1

다음은 An unbalanced binary search tree에 주렁주렁 달아 놓을 Node를 구현한 코드입니다(Figure 2.2). Template는 하지 않아도 좋습니다. 본인은 하다보니 습관적으로 찍어버렸습니다.

Figure 2.2

마지막으로 데이터의 Insertion, Deletion, Traverse 등등을 Console창에서 바로바로 확인하기 쉽도록 Application을 구현하였습니다. 상당히 귀찮은 작업일지도 모르겠으나 향후 다양한 Data Structure를 공부함에 있어서 다방면으로 활용이 될 것이라고 믿습니다(Figure 2.3).

Figure 2.3

Figure 2.3 내부에 구현된 내용은 Figure 3.1부터 시작되는 본격적인 Binary Tree를 이해한다면 자연스럽게 이해가 갑니다. 사실, 그런 내용이 없어도  Application class는 직감적으로 각 Function이 어떤 역할을 하는 지 알기 쉽습니다. 글이 길면 나도 읽기가 싫기 때문에 잠깐 끊어서 작성하기로 했습니다.