[알고리즘] 이진탐색트리(BST)

 

 

---

이진탐색트리(BST)는 링크드리스트를 기반으로 한 탐색 알고리즘입니다.

그래서 링크드리스트를 모르시면 꼭! 자료구조를 통해 공부를 하시고 

읽으시길 바랍니다. 본 게시물이선 BST에 대해서만 설명합니다.

---

 

 

 

이해 순서

 

1.  포인터를 정확히 이해한다.

2.  링크드리스트를 이해한다.

3.  완전 이진트리를 이해한다.

4.  이진 탐색트리를 이해한다.

 

이진탐색트리(BST) 란 ?

 

: 방탄소년단(BST) ? 죄송합니다. 이진탐색트리는 이진탐색(Binary Search)와 연결리스트(Linked List)를 결합한 자료구조의 일종입니다. 이진탐색은 탐색에 필요한 시간복잡도가 O(logN)으로 빠르지만 자료 입력과 삭제가 불가능합니다. 연결리스트의 경우는 입력과 삭제의 시간복잡도가 O(1)로 빠르지만 탐색하는 시간복잡도는 O(n)으로 매우 비효율 적입니다. 따라서 두 자료구조의 장점을 합친것이 이진탐색트리입니다.

 

 

 

이진탐색트리의 조건

 

• 모든 서브트리는 이진탐색트리 구조이다.

• 각 노드의 왼쪽 서브트리는 해당노드의 값 보다 작은 노드들로 구성되어 있다.

• 각 노드의 오른쪽 서브트리는 해당노드의 값 보다 큰 노드들로 구성되어 있다.

• 중복된 노드가 없어야 한다.

특징 : 이진탐색트리는 중위순회(inorder) 방식을 사용합니다. 이유는 이렇게 순회를 하면 모든 값들이 정렬된 순서대로 읽을 수 있기 때문입니다.  

중위순회 방식으로 간단한 이진트리를 읽어보겠습니다. 순서는 왼쪽 서브트리의 마지막 노드-> 부모노드 -> 오른쪽 서브트리의 노드 의 순서입니다. 이렇게 읽어보면 1, 3, 5, 7, 8, 10 입니다.

 

삽입 코드 

 

void InsertNode(BSTree_Node* tree, BSTree_Node* newNode) {

    if (tree->Value() < newNode->Value()) { //큰값은 오른쪽 서브트리

        if (tree->right == NULL)

            tree->right = newNode;

        else

            InsertNode(tree->right, newNode);

    }

    else if (tree->Value() > newNode->Value()) { // 작은값은 왼쪽 서브트리

        if (tree->left == NULL)

            tree->left = newNode;

        else

            InsertNode(tree->left, newNode);

    }

 

    return;

}

Colored by Color Scripter

cs

삽입(insert) 과정은 생각보다 간단합니다.

처음에 입력받은 값이 트리의 노드 값보다 크다면 오른쪽 서브트리를 들어갑니다.

이때 노드의 오른쪽 자식이 없다면 해당위치에 입력받은 값을 삽입.

  노드의 오른쪽 자식이 있다면 오른쪽 자식노드에서 재귀함수 호출.

만약 입력받은 값이 트리의 노드 값보다 작다면 왼쪽 서브트리를 들어갑니다.

여기선 오른쪽과 동일합니다.

삭제 코드

BSTree_Node* RemoveNode(BSTree_Node* root, BSTree_Node* parent, int target) {
    BSTree_Node* cur = NULL;
 
    if (root == NULL)
        return NULL;
 
    if (root->Value() > target)         // 작은경우 왼쪽서브트리에서 재귀호출
        cur = RemoveNode(root->left, root, target);
    else if (root->Value() < target) // 큰경우 오른쪽 서브트리에서 재귀호출
        cur = RemoveNode(root->right, root, target);
    else {
        cur = root;
 
        if (root->left == NULL && root->right == NULL)   //자식이 없는 경우
        {            
            if (parent->left == root)
                parent->left = NULL;
            else
                parent->right = NULL;
        }
        else if (root->left != NULL && root->right != NULL)   //자식이 두개인 경우
        {            
            BSTree_Node* minNode = searchMinNode(root->right);
            minNode = RemoveNode(root, NULL, minNode->Value());
            root->setValue(minNode->Value());
        }
        else
        {   //자식이 하나인 경우
            BSTree_Node* tmp = NULL;
            if (root->left != NULL)
                tmp = root->left;
            else
                tmp = root->right;
 
            if (parent->left == root)
                parent->left = tmp;
            else
                parent->right = tmp;
        }
 
    }
 
    return cur;
}

삭제(remover)과정은 조금 복잡합니다.

우선 3가지의 경우로 나뉩니다.

1. 삭제하고자 하는 노드의 자식이 없을때
2. 삭제하고자 하는 노드의 자식이 하나일때
3. 삭제하고자 하는 노드의 자식이 두개일때

 

1. 삭제하고자 하는 노드의 자식이 없을때 

Leef 노드의 경우를 의미하는데, 이경우는 그냥 해당 노드만 삭제해주시면 문제없습니다.

2. 삭제하고자 하는 노드의 자식이 하나일때

해당 그림에서 7을 삭제한다고 합시다.

7의 자식은 오른쪽 자식 9 하나 뿐입니다.

우선 5의 오른쪽 자식노드의 주소를 9의 주소로 바꿔줍니다.

그리고 7을 삭제하면 자연스럽게 연결이 됩니다.

3. 삭제하고자 하는 노드의 자식이 두개일때

양쪽의 자식노드를 모두 갖고있는 15를 삭제해봅시다.

두가지의 방법이 있습니다.

1. 오른쪽 자식중에서 가장 작은 값을 15의 자리로 옮긴다.

2. 왼쪽 자식중에서 가장 큰 값을 15의 자리로 옮긴다.

전자의 경우로 해보겠습니다.

가장 먼저 오른쪽 서브트리의 최솟값인 17을 해당위치에 넣어줍니다.

이렇게 되면 17은 중복값이 됩니다. 

따라서 원래 있던 17을 지워주겠습니다.

지우는 과정을 보니 자식이 없는 노드를 지우는 과정과 같네요.

이부분이 포인트 입니다.

양쪽 자식을 모두 갖고 있는 노드를 삭제하기 위해서는 

자식이 없거나 하나인 상황을 만들어서 삭제하는 것입니다.

이전과 마찬가지로 17을 19에 연결한 후 원래 있던 17을 삭제합니다.

출력 코드

출력(Print) 는 단순히 중위순회 순서로 출력해주시면 됩니다. 

void PrintTree(BSTree_Node* Node) {
    if (Node == NULL)
        return;
    PrintTree(Node->left);
    cout << Node->Value() << endl;   // 중위순회를 이용
    PrintTree(Node->right);                 // 재귀
    return;
}

 

 

 

코드

 

#include<iostream>
#include<time.h>
using namespace std;
 
 
class BSTree_Node {
private:
    int value;
public:
 
    int Value() {
        return value;
    }
    void setValue(int val) {
        value = val;
    }
    BSTree_Node* left;
    BSTree_Node* right;
 
    BSTree_Node(int val) 
    {
        value = val;
    }
    ~BSTree_Node() {
        delete this; 
    }
};
 
BSTree_Node* CreateNode(int value);         // 노드생성
void InsertNode(BSTree_Node* tree, BSTree_Node* newNode);
void DeleteNode(BSTree_Node* delNode);   // 노드삭제
void DestroyTree(BSTree_Node* root);        // 트리 삭제
void PrintTree(BSTree_Node* Node);          // 노드 출력 (중위순회)
BSTree_Node* searchMinNode(BSTree_Node* root);
BSTree_Node* RemoveNode(BSTree_Node* root, BSTree_Node* parent, int target);
 
BSTree_Node* CreateNode(int value) {
    BSTree_Node* newNode = new BSTree_Node(value);   // 생성 후
    newNode->left = NULL;                     // 각 value 초기화
    newNode->right = NULL;
 
    return newNode;
}
 
void InsertNode(BSTree_Node* tree, BSTree_Node* newNode) {
    if (tree->Value() < newNode->Value()) { //큰값은 오른쪽 서브트리
        if (tree->right == NULL)
            tree->right = newNode;
        else
            InsertNode(tree->right, newNode);
    }
    else if (tree->Value() > newNode->Value()) { // 작은값은 왼쪽 서브트리
        if (tree->left == NULL)
            tree->left = newNode;
        else
            InsertNode(tree->left, newNode);
    }
 
    return;
}
 
 
void PrintTree(BSTree_Node* Node) {
    if (Node == NULL)
        return;
    PrintTree(Node->left);
    cout << Node->Value() << endl;   // 중위순회를 이용
    PrintTree(Node->right);                 // 재귀
    return;
}
 
void DeleteNode(BSTree_Node* delNode) {
    delete delNode;
    return;
}
 
void DestroyTree(BSTree_Node* root) {
    DestroyTree(root->left);
    DestroyTree(root->right);
    DeleteNode(root);
    return;
}
 
BSTree_Node* searchMinNode(BSTree_Node* root) {
    if (root == NULL)
        return NULL;
 
    if (root->left == NULL)
        return root;
    else
        return searchMinNode(root->left);
}
 
BSTree_Node* RemoveNode(BSTree_Node* root, BSTree_Node* parent, int target) {
    BSTree_Node* cur = NULL;
 
    if (root == NULL)
        return NULL;
 
    if (root->Value() > target)         // 작은경우 왼쪽서브트리에서 재귀호출
        cur = RemoveNode(root->left, root, target);
    else if (root->Value() < target) // 큰경우 오른쪽 서브트리에서 재귀호출
        cur = RemoveNode(root->right, root, target);
    else {
        cur = root;
 
        if (root->left == NULL && root->right == NULL)   //자식이 없는 경우
        {            
            if (parent->left == root)
                parent->left = NULL;
            else
                parent->right = NULL;
        }
        else if (root->left != NULL && root->right != NULL)   //자식이 두개인 경우
        {            
            BSTree_Node* minNode = searchMinNode(root->right);
            minNode = RemoveNode(root, NULL, minNode->Value());
            root->setValue(minNode->Value());
        }
        else
        {   //자식이 하나인 경우
            BSTree_Node* tmp = NULL;
            if (root->left != NULL)
                tmp = root->left;
            else
                tmp = root->right;
 
            if (parent->left == root)
                parent->left = tmp;
            else
                parent->right = tmp;
        }
 
    }
 
    return cur;
}
 
 
int main() {
    srand(time(0));
 
    BSTree_Node* root = CreateNode(50);    // root 노드를 생성한 후
 
    BSTree_Node* newNode;
 
        newNode = CreateNode(50);
        InsertNode(root, newNode);
        newNode = CreateNode(13);
        InsertNode(root, newNode);
        newNode = CreateNode(41);
        InsertNode(root, newNode);
        newNode = CreateNode(25);
        InsertNode(root, newNode);
        newNode = CreateNode(3);
        InsertNode(root, newNode);
        newNode = CreateNode(23);
        InsertNode(root, newNode);
    
 
    PrintTree(root);
 
 
        RemoveNode(root, NULL, 13);
 
    cout << "///////////// 노드 삭제 //////////////" << endl;
 
    PrintTree(root);
 
    return 0;
}
 

 

출처 : https://zeddios.tistory.com/492

출처 : https://assortrock.com/48