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

이진 탐색 트리란

- 이진탐색과 연결리스트를 결합한 자료구조의 일종이다.

- 효율적인 탐색 능력을 유지하면서도, 빈번한 자료 입력과 삭제를 가능하게끔 고안되었다.

 

특징

- 각 노드에 중복되지 않은 키(key)가 있다.

- 루트노드의 왼쪽 서브트리는 해당 노드의 키보다 작은 키를 갖는 노드들로 이루어져 있다.

- 루트노드의 오른쪽 서브 트리는 해당 노드의 키보다 큰 키를 갖는 노드들로 이루어져 있다.

- 좌우 서브 트리도 모두 이진 탐색 트리여야 한다.

 

탐색 과정

1. 루트 노드의 키와 찾고자하는 값을 비교한다. 찾고자 하는 값이라면 탐색을 종료한다.

2. 찾고자 하는 값이 루트 노드의 키보다 작다면 왼쪽 서브 트리로 탐색을 진행한다.

3. 찾고자 하는 값이 루트 노드의 키보다 크다면 오른쪽 서브 트리로 탐색을 진행한다.

* 위의 과정을 통해 값을 찾지 못한다면 그대로 종료한다.

 

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. 삽입할 값을 루트 노드와 비교해 같다면 오류를 발생한다(중복 Key)

2. 삽입할 값이 루트 노드의 키보다 작다면 왼쪽 서브트리의 자리로 이동하며 비어있는 자리에 삽입한다.

3. 삽입할 값이 루트 노드의 키보다 크다면 오른쪽 서브트리의 자리로 이동하며 비어있는 자리에 삽입한다.

 

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;
            }
        }
    }
    
}

 

 

이진 탐색 트리의 삭제 과정

이진탐색 트리의 삭제과정은 세가지로 나뉜다.

1. 삭제하려는 노드가 단말노드인 경우

2. 삭제하려는 노드에 서브트리가 하나 있는경우

3. 삭제하려는 노드에 서브트리가 두개 있는 경우

 

1. 삭제하려는 노드가 단말노드인 경우

자식이 없는 단말 노드의 삭제는 간단하다.

삭제할 노드의 부모 노드가 있다면 부모노드의 자식 노드를 NULL로 만들고,

삭제할 노드를 삭제(메모리 해제) 해주면 된다.

 

2.삭제하려는 노드에 서브트리가 하나 있는 경우

이 경우도 간단한다.

삭제할 노드의 자식노드를 삭제할 노드의 부모노드의 자식노드로 설정한뒤 해당 노드를 삭제하면된다.

 

3. 삭제하려는 노드의 서브트리가 두개 있는 경우

이 경우가 가장 복잡하다.

두가지 방법을 사용할 수 있다.

 

1) 삭제할 노드의 왼쪽 서브 트리의 가장 큰 자손을 해당 노드의 자리로 올린다.

2) 삭제할 노드의 오른쪽 서브트리의 가장 작은 자손을 해당 노드의 자리로 올린다.

책에서는 2번을 더 중점으로 설명해두었다.

 

TreeNode* delete_node(TreeNode* root, int key){
    TreeNode* del = NULL;    // 삭제할 노드     
    TreeNode* parent = NULL;    // 삭제할 노드의 부모 노드 
    TreeNode* successor = NULL;    // 삭제할 노드의 왼쪽 서브트리에서 가장 큰 노드 
    TreeNode* predecessor = NULL;    // successor의 부모노드 
    TreeNode* child = NULL;        // 삭제할 노드의 자식 노드 
    
    del= root;
    while(del != NULL){    // 삭제할 노드 탐색 
        if(key == del->key){
            break;
        }
        parent = del;
        if(key < del->key){
            del = del->left;
        }else{
            del = del->right;
        }
    }
    
    if(del == NULL){
        printf("Error : 존재하지 않는 키\n");
        return root;
    }
    
    if(del->left == NULL && del->right == NULL){    // 삭제할 노드의 자식노드가 없는 경우 
        if(parent != NULL){    // 부모노드가 있는 경우 
            if(parent->left == del){    // 부모노드의 왼쪽노드가 삭제할 노드일 때 
                parent->left = NULL;
            }else{    // 오른쪽 일 때 
                parent->right = NULL;
            }
        }else{    // 부모노드가 없는 경우 = root 노드 
            root = NULL;
        } 
    }else if(del->left != NULL && del->right != NULL){    // 삭제할 노드의 자식 노드가 2개인 경우 
        predecessor = del;
        successor = del->left;
        
        while(successor->right != NULL){    // 왼쪽 서브트리에서 가장 큰 값 찾기 
            predecessor = successor;
            successor = successor->right;
        }
        
        if(predecessor->left == successor){
            predecessor->left = successor->left;
        }else{
            predecessor->right = successor->left;
        }
         
        
        del->key = successor->key;
        del = successor;
 
    }else{    //     삭제할 노드의 자식 노드가 1개인 경우 
        if(del->left != NULL){    // 왼쪽 노드 
            child = del->left;
        }else{    // 오른쪽 노드 
            child = del->right;
        }
        
        if(parent != NULL){    // 부모노드가 있는 경우 
            if(parent->left == del){    // 부모노드의 왼쪽 노드로 삭제할 노드의 자식노드 연결 
                parent->left = child;
            }else{    // 부모노드의 오른쪽 노드로 삭제할 노드의 자식노드 연결  
                parent->right = child;
            }
        }else{
            root = child;
        }
    }
    
    free(del);    // 메모리해제 
    return root; 
}

 

 

 

참고 링크 : https://code-lab1.tistory.com/10