C# 자료구조 : 이진검색트리 (Binary Search Tree)

이진트리(Tree)의 특수한 형태로 자주 사용되는 트리로서 이진검색트리 (Binary Search Tree)가 있다. 이진검색트리는 이진트리의 모든 속성을 가짐과 동시에 중요한 또 하나의 속성을 가지고 있는데, 그것은 특정 노드에서 자신의 노드보다 작은 값들은 모두 왼쪽에 있고, 큰 값들은 모두 오른쪽에 위치한다는 점이다. 또한 중복된 값을 허락하지 않는다. 따라서 전체 트리가 소트되어 있는 것과 같은 효과를 같게 되어 검색에 있어 배열이나 이진트리처럼 순차적으로 모든 노드를 검색하는 것(O(n))이 아니라, 매 검색마다 검색영역을 절반으로 줄여 O(log n)으로 검색할 수 있게 된다. 하지만 노드들이 한쪽으로 일렬로 기울어진 Skewed Tree인 경우, 검색영역을 n-1로만 줄이기 때문에 O(n)만큼의 시간이 소요된다. 즉, 예를 들어 소트된 데이타를 이진검색트리에 추가하게 되면, 이렇게 한쪽으로 치우쳐 진 트리가 생겨 검색시간이 O(n)으로 떨어지게 되는데, 이러한 현상을 막기 위하여 노드 추가/갱신시 트리 스스로 다시 밸런싱(Self balancing)하여 검색 최적화를 유지할 수 있다. 이러한 트리를 Self-Balancing Binary Search Tree 또는 Balanced Search Tree라 하는데, 가장 보편적인 방식으로 AVL Tree, Red-Black Tree 등을 들 수 있다.
NOTE: 참고로 Search Tree에는 최대 2개의 자식노드를 갖는 Binary Search Tree 이외에, 여러 개의 자식노드들을 갖는 N-Way 검색 트리 (n-way Search Tree)가 있는데, 대표적으로 B-Tree (혹은 이의 변형인 B* Tree, B+ Tree)가 있으며 흔히 SQL Server와 같은 관계형 DB 인덱스로 주로 사용된다. 

C#으로 간단한 이진검색트리 구현 

.NET Framework은 이진검색트리와 관련된 클래스를 제공하지 않는다. 아래 소스는 간단한 이진검색트리를 C#으로 구현해 본 것으로서, 이진검색트리의 기본적인 개념을 예시하기 위한 코드이다. 

//

//  main.c

//  LinkedList1

//

//  Created by Jang sang wook on 7/11/13.

//  Copyright (c) 2013 Jang sang wook. All rights reserved.

//

#include <stdio.h>

int BSearch(int ar[], int len, int target);

int main(int argc, const char * argv[])

{

    // insert code here...

    printf("Hello, World!\n");

    

    int arr[] = {1,3,5,7,9,10,23,24,30};

    int idx;

    

    idx = BSearch(arr, sizeof(arr)/sizeof(int), 30);

    

    printf("%d\n", idx);

    

    if(idx==-1) printf("탐색 실패.\n");

    else printf("타겟 저장 인덱스: %d \n", idx);

    

    return 0;

}

int BSearch(int ar[], int len, int target){

    int first = 0;

    int last = len-1;

    int mid;

    while(first<=last){

        mid = (first+last)/2;

        if(target==ar[mid]){

            return mid;

        }

        else{

            if(target < ar[mid]) last = mid-1;

            else first = mid+1;

        }

    }

    return -1;

}