[자료구조]이진 탐색 트리(Binary Search Tree)

이진 탐색 트리(Binary Search Tree)란?

-각 노드에는 서로 다른 값이 할당되어 있다.

-모든 내부 노드에 대해, 노드의 왼쪽 서브 트리는 그 노드의 값보다 작은 값을 가진 노드들로 이루어져 있다.

-모든 내부 노드에 대해, 노드의 오른쪽 서브 트리는 그 노드의 값보다 큰 값을 가진 노드들로 이루어져 있다.

 

 

이진 탐색 트리를 구현하기 위해서는, 먼저 아래와 같은 코드가 필요합니다.

 

typedef struct element{
    int key;
} element;

typedef struct treeNode* treePointer;
typedef struct treeNode{
    element data;
    treePointer leftChild;
    treePointer rightChild;
} treeNode;

 

아래는 이진 탐색 트리에서 특정 key 값을 가진 노드를 찾아서 그 노드의 data의 주소값을 반환하는 코드들입니다.

 

먼저, 재귀적으로 탐색하는 코드입니다.

 

element* recursiveSearch(treePointer root, int k)
{
    if(!root) return NULL
    if (k == root->data.key) return &(root->data);
    if(k < root->data.key) return recursiveSearch(root->leftChild, k);
    return recursiveSearch(root->rightChild, k);
}

 

위 코드는 다음과 같은 방식으로 실행됩니다.

1. 매개변수로 받은 root가 NULL이면 종단 노드까지 탐색했다는 의미입니다. 즉, 해당 이진 트리에서 찾고자 하는 값을 찾지 못했다는 뜻입니다. 따라서 이 경우에는 NULL을 반환해줍니다. 만약 root가 NULL이 아니라면 아래 코드를 계속 실행합니다.
2. 만약 root의 data에 담긴 key 값이 k(찾고자하는 값)와 같다면 해당 root의 data의 주소값을 리턴해줍니다.
3. 만약 k가 root의 data에 담긴 key 값보다 작다면 root의 왼쪽 서브 트리를 탐색해애 하므로 root->leftChild를 매겨변수로 넘겨준 recursiveSearch의 실행 결과를 반환하게 합니다.
4. 만약 k가 root의 data에 담긴 key 값보다 크다면 root의 오른쪽 서브 트리를 탐색해야 하므로 root->rightChild를 매겨변수로 넘겨준 recursiveSearch의 실행 결과를 반환하게 합니다.

 

 

 

그 다음은, 반복문으로 탐색하는 코드입니다.

 

element* iterativeSearch(treePointer tree, int k)
{
    while(tree)
    {
        if(k == tree->data.key) return &(tree->data);
        if(k < tree->data.key)
            tree = tree->leftChild;
        else
            tree = tree->rightChild;
    }
    return NULL;
}

 

위 코드는 다음과 같은 방식으로 살행됩니다.

1. tree가 NULL일 때까지 while문을 실행합니다. tree가 NULL이면 종단 노드까지 탐색했다는 의미입니다. 즉, 해당 이진 트리에서 찾고자 하는 값을 찾지 못했다는 뜻입니다. 따라서 이 경우에는 NULL을 반환해줍니다. 만약 tree가 NULL이 아니라면 반복문을 계속 실행합니다.
2. 만약 tree의 data에 담긴 key 값이 k(찾고자하는 값)와 같다면 해당 tree의 data의 주소값을 리턴해줍니다.
3. 만약 k가 tree의 data에 담긴 key 값보다 작다면 tree의 왼쪽 서브 트리를 탐색해애 하므로  tree를 tree->leftChild로 초기화하여 반목문을 계속 실행합니다.
4. 만약 k가 tree의 data에 담긴 key 값보다 크다면 tree의 오른쪽 서브 트리를 탐색해애 하므로  tree를 tree->rightChild로 초기화하여 반목문을 계속 실행합니다.