18-1. 이진 탐색 트리 - 이진 탐색 트리 / 이진 탐색 트리 구현하기

이진 탐색 트리(Binary Search Tree)

이진 탐색 트리란, 이진 탐색이 항상 동작하도록 구현해서 탐색 속도를 극대화 시킨 자료구조이다. 

 

이진 탐색 트리의 동작 방식

이진 탐색 트리에서는 항상 부모 노드가 왼쪽 자식보다는 크고, 오른쪽 자식보다는 작다.

위의 이진트리에서 37이라는 원소를 찾는 다면,

37이 루트노드(30)보다 큰 값이기 때문에, 루트노드의 왼쪽자식들은 탐색할 필요가 없다. 따라서 오른쪽 자식 중 48보다 작으므로 48의 왼쪽 자식만 탐색하면 된다.

 

이진 탐색 트리의 탐색

위의 예제에서 볼 수 있듯이,  이진 탐색 트리에서는 한번 확인할 때마다 탐색해야하는 원소의 개수가 절반씩 줄어든다는 점에서, O(logN)의 시간 복잡도를 가진다.

 

이진 탐색 트리에서, 찾고자 하는 값이 부모 노드보다 작을 경우 왼쪽 자식으로, 찾고자 하는 값이 부모 노드보다 클 경우 오른쪽 자식으로 방문을 이어나가며 탐색한다.

이진 탐색 트리 구현

이진 탐색 트리->노드 정의

#include <stdio.h>
#include <stdlib.h>

typedef struct{
    int data;
    struct Node leftChild;
    struct Node rightChild;
}Node;

이진 탐색 트리의 삽입 함수

Node* insertNode(Node* root, int data){
    if (root == NULL){ //트리가 비어있거나, 해당 root노드가 NULL값일 때 새 노드를 초기화
        root = (Node*)malloc(sizeof(Node));
        root->leftChild = root->rightChild = NULL;
        root->data = data;
    }
    else{
        if(root->data > data){ //부모 노드의 데이터보다 삽입 데이터가 작다면
            root->leftChild = insertNode(root->leftChild, data);      
        }
        else{ //부모 노드의 데이터가 삽입 데이터가 크다면
            root->rightChild = insertNode(root->rightChild, data);
        }
    }
    return root;
}

 

이진 탐색 트리의 탐색 함수

Node* searchNode(Node* root, int data){ //특정한 값(data)를 갖는 노드 탐색
    if (root == NULL) return NULL; //탐색 실패
    if (root->data == data) return root; //노드 발견시 해당 노드 자체(포인터)를 반환
    else if (root->data > data) returnsearchNode(root->leftChild, data);
    else return searchNode(root->rightChild, data);
}

 

이진 탐색 트리의 순회

void preorder(Node* root){ //전위순회로 구현함
    if(root == NULL) return;
    printf("%d ", root->data);
    preorder(root->leftChild);
    preorder(root->rightChild);
}

 

이진 탐색 트리 생성하기

int main(void){
    Node* root = NULL;
    root = insertNode(root, 30);
    root = insertNode(root, 17);
    root = insertNode(root, 48);
    root = insertNode(root, 5);
    root = insertNode(root, 23);
    root = insertNode(root, 37);
    root = insertNode(root, 50);
    preorder(root); //전위 순회 방식으로 출력
    system("pause");
}