어떠한 데이터를 찾아내거나 저장할때는 어떤 위치에 데이터가 있는지 혹은 어떤 위치에 데이터를 저장할지가 상당히 중요하다. 그러한 위치에 따라서 검색의 속도나 저장의 속도가 현저히 차이가 나기 때문이다. 이러한 자료구조는 데이터베이스의 근간이기 때문에 개발자로서 이해하는게 중요하고 이러한 자료구조를 통해서 앞으로 프로그램을 설계해 나가는것도 중요하다. 따라서, 대표적인 3가지의 트리들을 선정했고 이 포스트에서 공유할 예정이다. 늘 그렇듯이 실제 코드가 궁금하다면 하단의 깃허브를 참조하면된다.
본격적인 이진 검색트리에 대한 설명을 하기전에 왜? 이진 검색트리가 탄생 했는지 생각해보자. 우선 아무런 자료구조 없이 데이터베이스에 데이터를 저장했다고 생각해보자. 랜덤 엑세스가 불가능한 저장 장치에 데이터를 저장했다면, 당연히 우리는 앞에서 부터 차근히 하나하나씩 엑세스 한다음 비교하고 엑세스 한다음 비교하고를 반복해야할 운명이다. 그럼 검색에만 O(n)을 사용해야한다. 만약 모든 데이터 엑세스가 이렇다고 한다면 상당히 비효율적인 구조라고 생각이 든다. 선배 프로그래머들도 이러한 생각을 하지 않은것은 아니다. 이러한 문제의식은 자료구조의 발전으로 이어졌고 가장 단순한 이진 검색트리가 탄생하고 점차 진화해나갔다고 생각하면된다. 이진 검색 트리는 데이터 엑세스를 평균적을 O(logn)으로 만들어준다. 다만, 최악의 경우는 O(n)이다. 최악의 경우도 O(logn)으로 만드는 자료구조가 대표적으로 두개 있는데, AVL 트리와 레드 블랙 트리이다. 둘중에 우리는 대표적으로 레드 블랙 트리를 배워볼것이다.
완벽한 예는 위의 사진으로 찾아볼 수 있다. 루트는 8이고 8보다 작은 노드들은 왼쪽 서브트리에 구성되고 8보다 큰 노드들은 오른쪽에 구성된다. 최대 두 개의 자식노드를 갖고 있고 전부 유니크한 키값을 가지고 있다.
treeSearch(t, x) // t -> root 노드, x 검색하고자 하는 키
{
if(t == null or key[t] == x) return t;
if (x < key[t])
return treeSearch(left[t], x);
else
return treeSearch(right[t], x);
}
위의 규칙을 만족하는 자료구조내에서 검색이 어떻게 이루어지는지 생각해보자. 위으 슈도코드를 생각해보면 전체적인 과정은 해당 노드(t)의 값과 찾고자하는 값(x)를 비교해서 왼쪽으로 갈지 오른쪽으로 갈지 생각한다. 예를 들자면 아래와 같다.
위의 구조에서 14를 찾고자 한다면 40보다 작기때문에 왼쪽으로 4보다 크기때문에 오른쪽으로 34보다 작기때문에 왼쪽으로 가서 마지막 비교를 하면 14가 나오고 해당 인덱스에 있는 자료를 찾아서 보낼 수 있다. 그렇다면 이 검색의 평균 시간복잡도는 어떻게 될까? 당연하게도 O(logn)이다. 왜냐하면, 균형잡힌 트리의 높이가 logn이다. 3층짜리 트리는 7개의 데이터를 저장할 수 있다(log7). 층수가 높아 질수록 logn으로 점근된다. 하지만, 트리의 높이가 n이 될 수도 있다.
이렇게 일자로 쭈욱 펼쳐진 자료구조 또한, 이진 검색 트리의 모든 규칙을 만족하게된다. 따라서, 이러한 자료구조에서는 O(n)이 걸리게 된다.
treeInsert(t, x) // t -> root 노드, x 넣고자 하는 키
{
if(t == null)
{
key[r] = x; // r -> 신규 노드
left[r] = null;
right[r] = null;
return r;
}
if (x < key[t])
{
left[t] = treeInsert(left[t], x);
return t;
}
else
{
right[t] = treeInsert(right[t], x);
return t;
}
}