[자료구조] 이진탐색트리(Binary Search Tree)의 개념과 삽입 / C언어로 구현하기

이진탐색트리(Binary Search Tree)의 개념

이진탐색트리란 이진탐색(binary search)과 연결리스트(linked list)를 결합한 자료구조의 일종이다.

데이터의 삽입, 삭제, 탐색 등이 자주 발생하는 경우에 효율적으로 쓰인다.

이진트리

**(복습)

- 이진트리 - 한 노드의 자식 노드가 최대 2개(왼쪽,오른쪽)인 트리

- 포화 이진 트리 : 모든 레벨의 노드가 꽉 차있으며, 단말 노드를 제외한 모든 노드의 차수가 2인 이진 트리.
- 완전 이진 트리 : 단말 노드들이 트리 왼쪽부터 채워진 형태의 이진 트리.
- 높이 균형 트리 : 모든 단말 노드의 깊이 차이가 많아야 1인 이진 트리.
- 완전 높이 균형 이진 트리 : 왼쪽 하위 트리와 오른쪽 하위 트리의 높이가 같은 이진 트리.

이진탐색트리의 정의

이진탐색트리란 다음과 같은 특징을 갖는다.

1. 각 노드에 중복되지 않는 키(key)가 있다.
2. 루트노드의 왼쪽 서브 트리는 해당 노드의 키보다 작은 키를 갖는 노드들로 이루어져 있다.
3. 루트노드의 오른쪽 서브 트리는 해당 노드의 키보다 큰 키를 갖는 노드들로 이루어져 있다.
4. 좌우 서브 트리도 모두 이진 탐색 트리여야 한다

 

이진탐색트리의 목적

이진 탐색 트리는 기존 이진트리보다 탐색이 빠르다. 

이진탐색의 경우 탐색에 소요되는 계산복잡성은 O(logn)𝑂(log⁡𝑛)으로 빠르지만 자료 입력, 삭제가 불가능하다.

연결리스트의 경우 자료 입력, 삭제에 필요한 계산복잡성은 O(1)𝑂(1)로 효율적이지만 탐색하는 데에는 O(n)𝑂(𝑛)의 계산복잡성이 발생한다. 두 마리 토끼를 잡아보자는 것이 이진탐색트리의 목적이다.

 

이진 탐색 트리 탐색과정

이진 탐색 트리는 다음고 같은 과정을 거치며 탐색을 진행한다.

1. 루트 노드의 키와 찾고자 하는 값을 비교한다. 찾고자 하는 값이라면 탐색을 종료한다.
2. 찾고자 하는 값이 루트 노드의 키보다 작다면 왼쪽 서브 트리로 탐색을 진행한다.
3. 찾고자 하는 값이 루트노드의 키보다 크다면 오른쪽 서브트리로 탐색을 진행한다. 

 

위 과정을 원하는 값을 찾을때까지 반복한다. 만약 찾지 못하면 그대로 종료한다. 

 

이러한 탐색 과정은 트리의 높이만큼 진행된다.

예를 들어, 위와 같은 트리에서 key가 5인 노드를 찾는다면,  루트 노드와의 비교가 이루어진다. 5가 7보다 작으므로 왼쪽 서브트리로의 탐색이 이루어지고, 이후 5가 3보다 크므로 오른쪽 서브트리로 탐색이 이루어진다. key가 5인 노드를 찾았으므로 탐색이 종료된다.

 

이진 탐색 트리 탐색 - C로 구현

TreeNode* search(TreeNode* root, int key){
    if(root == NULL){    // 값을 찾지 못한 경우  
        return NULL;
    }
    
    if(key == root->key){    // 값을 찾음 
        return root;
    }
    else if(key < root->key){    // 왼쪽 서브트리 탐색 
        search(root->left, key);
    }
    else if(key > root->key){    // 오른쪽 서브트리 탐색 
        search(root->right, key);
    }
    
}

 

이진 탐색 트리 탐색 삽입 

이진 탐색트리의 삽입은 다음과 같은 과정을 거친다.

 

1. 삽입할 값을 루트 노드와 비교해 같다면 오류를 발생한다.
2. 삽입할 값이 루트 노드의 키보다 작다면 왼쪽 서브 트리를 탐색해서 비어있다면 추가하고, 비어있지 않다면 다시 값을 비교한다.
3. 삽입할 값이 루트노드의 키보다 크다면 오른쪽 서브트리를 탐색해서 비어있다면 추가하고, 비어있지 않다면 다시 값을 비교한다.

 

위와 같은 이진 트리에 6을 키로 가진 노드를 추가한다 했을떄

다음과 같은 과정으로 삽입하고자 하는 값을 계속 비교해서 삽입할 위치를 찾는다. 탐색 과정과 비슷하다.

 

이진 탐색 트리 탐색 삽입 구현 - C언어

void insert(TreeNode** root, int key){
    TreeNode* ptr;     // 탐색을 진행할 포인터 
    TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));    // newNode 생성
    newNode->key = key;
    newNode->left = newNode->right = NULL; 
    
    if(*root == NULL){    // 트리가 비어 있을 경우 
        *root = newNode;
        return;
    }
    
    ptr = *root;    // root 노드부터 탐색 진행  
    
    while(ptr){
        if(key == ptr->key){    // 중복값 
            printf("Error : 중복값은 허용되지 않습니다!\n");
            return;
        }else if(key < ptr->key){    // 왼쪽 서브트리 
            if(ptr->left == NULL){    // 비어있다면 추가 
                ptr->left = newNode;
                return;
            }else{    // 비어있지 않다면 다시 탐색 진행 
                ptr= ptr->left;
            }
        }else{    // key > ptr->key 오른쪽 서브트리 
            if(ptr->right == NULL){    // 비어있다면 추가 
                ptr->right = newNode;
                return;
            }else{    // 비어있지 않다면 다시 탐색 진행 
                ptr = ptr->right;
            }
        }
    }
    
}

 

조금 더 복잡한 이진 탐색 트리의 삭제는 다음 시간에 다룬다.