공부하는 식빵맘 👱‍♀️

공부하는 식빵맘 👱‍♀️

반갑습니다 :)

(C++) 이진 탐색 트리 (장단점, 삽입, 삭제, 탐색, 순회)

Date:     Updated:

카테고리:

태그:

<뇌를 자극하는 알고리즘> 책을 참고했습니다.

🚀 이진 탐색 트리란?

“이진 탐색”을 위한 이진 트리(자식 노드가 최대 2개)

  • 모든 노드의 Key 는 유일하다. (중복이 없다.)
  • 왼쪽 자식 노드는 나보다 작고 ✨
  • 오른쪽 자식 노드는 나보다 크다. ✨

모든 노드가 위 규칙을 만족한다. 이런 구조 때문에 “이진 탐색”하기가 쉬움! 각각의 노드들이 중앙 요소가 된다. 임의의 어떤 노드의 왼쪽 서브트리에는 해당 노드보다 작은 값들만, 오른쪽 서브트리에는 해당 노드보다 큰 값들만 있기 때문이다.


🔥 이진 탐색 트리의 장점

  • 일반 이진 탐색은 중앙 요소를 알아야하므로 “배열”에서만 사용할 수 있다.
    • 연결 리스트는 이진 탐색 하기에 적합하지 않음
    • 또한, 배열의 크기가 변하면 안됨. 정적이어야 함.
  • “이진 탐색 트리”를 사용하여 탐색하면
    • 1️⃣ 배열을 사용하여 탐색할 때 보다 시간 복잡도가 줄어듬 O(logN) 👉 이진 탐색
    • 2️⃣ 동적으로 데이터 집합 크기가 바뀌고 순서가 바뀌어도 문제 없다. ✨


🔥 이진 탐색 트리의 단점

image

트리 모양이 이렇게 한쪽으로 치우쳐지게 되면 트리 탐색의 장점인 O(logN) 시간복잡도가 마치 배열을 순차탐색 하듯 하는 O(N)에 가까워지게 된다. 이진 탐색 트리 모양이 이렇게 되면 트리 사용하여 이득보는게 없다..!

따라서 이진 탐색 트리에 데이터를 “추가/삭제” 할 때 트리 모양이 한쪽으로 치우쳐지지 않고 균형있는 모양을 유지시키면 O(N)이 되는 것을 방지할 수 있다. 👉 이렇게 균형 잡힌 이진 탐색 트리가 되도록 보장되는 트리가 바로 “레드 블랙 트리”이다.


🚀 이진 탐색 트리의 연산

class Node
{
public:
    int data;
    Node* leftChild = NULL;
    Node* rightChild = NULL;

    Node(int _data, Node* _leftChild, Node* _rightChild)
        :data(_data), leftChild(_leftChild), rightChild(_rightChild)
    { }
};

🔥 탐색

루트 노드부터 시작하여 찾을 값과 크기를 비교하며 내려오면서 찾으면 된다.

  • 찾으려는 값 < 현재 트리의 루트 노드의 값
    • 왼쪽 서브트리로 내려간다. (👉 해당 노드보다 작은 값들 범위로)
  • 찾으려는 값 > 현재 트리의 루트 노드의 값
    • 오른쪽 서브트리로 내려간다. (👉 해당 노드보다 큰 값들 범위로)

일치하는 값을 찾을 때까지 위 과정을 재귀적으로 반복한다.

// 트리에 target 이 있다면 true 리턴
bool BST_SearchNode(Node* tree, int target) 
{
    if (tree == NULL)
        return false;

    if (tree->data == target)
        return true;
    else if (tree->data > target)
        return BST_SearchNode(tree->leftChild, target);
    else if (tree->data < target)
        return BST_SearchNode(tree->rightChild, target);
}

// 트리에 target 이 있다면 해당 노드 리턴
Node* BST_SearchNode(Node* tree, int target)
{
    if (tree == NULL)
        return NULL;

    if (tree->data == target)
        return tree;
    else if (tree->data > target)
        return BST_SearchNode(tree->leftChild, target);
    else if (tree->data < target)
        return BST_SearchNode(tree->rightChild, target);
}


🔥 삽입

새 노드가 삽입될 곳은 어디인가

이진 탐색 규칙을 만족해야 하므로 새 노드가 삽입될 적합한 위치 또한 이진 탐색으로 찾아야 한다. 그래서 위의 탐색 함수 코드랑 비슷하다.

이진 탐색 트리에 “추가” 된다는 것은 곧 조상부터 크기를 비교며 내려오면서 누군가의 왼쪽, 오른쪽 자식으로 세팅된다는 것이다.

이진 탐색 트리 규칙을 만족하면서 각 레벨 마다 왼쪽 혹은 오른쪽 서브트리를 선택하면서 쭉쭉 내려오다가 자식이 없는 Leaf 노드에 도달하면 그 곳에 추가하면 된다.

참고 👉 길 찾기 게임 문제

void BST_InsertNode(Node* tree, Node* node)
{
    if (node->x < tree->x) { // 현재 재귀 단계에서의 트리의 루트와 크기 비교 (서브트리의 루트)
        if (tree->leftChild == NULL) { // 루트보다 작은데 마침 루트에게 왼쪽 자식이 없다면 루트의 왼쪽 자식으로 세팅 후 종료
            tree->leftChild = node;
            return;
        }
        else
            BST_InsertNode(tree->leftChild, node); // 루트보다 작은데 루트에게 왼쪽 자식이 있다면 거기에 추가될 수 없으므로 더 내려가야 함. 왼쪽 서브트리로 내려가기.
    }
    else if (node->x > tree->x) {  // 루트보다 큰데 마침 루트에게 오른쪽 자식이 없다면 루트의 오른쪽 자식으로 세팅 후 종료
        if (tree->rightChild == NULL) {
            tree->rightChild = node;
            return;
        }
        else
            BST_InsertNode(tree->rightChild, node); // 루트보다 큰데 루트에게 오른쪽 자식이 있다면 거기에 추가될 수 없으므로 더 내려가야 함. 오른쪽 서브트리로 내려가기.
    }
}
  • tree 를 루트로 하는 서브트리로 재귀호출 하면서 내려온다.
    • 왼쪽 서브 트리의 루트로 호 출하면 왼쪽으로 내려가는 것이고
    • 오른쪽 서브 트리의 루트로 호출하면 오른쪽으로 내려가는 것이 된다.


🔥 삭제

이진 탐색 트리에서의 노드 삭제는 삭제하려는 노드의 자식이 몇 개냐에 따라 삭제 방법이 다르다.

  • Case
    1. 삭제할 노드의 서브트리가 0 개일 때
    2. 삭제할 노드의 서브트리가 1 개일 때
    3. 삭제할 노드의 서브트리가 2 개일 때

삭제할 노드의 부모와 삭제할 노드의 자식을 연결지어 주어야 하기 때문에 삭제할 노드의 부모가 누군지에 대한 정보도 가지고 있어야 한다.

✈ 전체 코드

Node* BST_SearchMinNode(Node* tree)
{
    if (tree == NULL)
        return NULL;

    if (tree->left == NULL)
        return tree;
    else
        return BST_SearchMinNode(tree->left);
}

Node* BST_RemoveNode(Node* tree, Node* parent, int target)
{
    // target과 일치하는 노드는 삭제할 노드다.
    // 삭제할 노드의 위치가 되는 노드는 tree 에, 삭제할 노드의 부모는 parent 에 저장된다.
    // 삭제할 노드(tree)는 removedNode 에 복사해 옮겨두고 나중에 이를 리턴한다.
    // tree 의 값을 새롭게 세팅해 이제 삭제되고 새로운 노드로 대체된 것처럼 연산해준다. 

    if (tree == NULL) 
        return NULL;
        
    Node* removedNode = NULL;
    
    /* 삭제할 노드 탐색하기*/
    if (tree->data > target)
        removedNode = BST_RemoveNode(tree->left, tree, target);
    else if (tree->data < target)
        removedNode = BST_RemoveNode(tree->right, tree, target);
    else if (tree->data == target) { // 삭제할 노드 찾음
        removedNode = tree; // 삭제된 노드 리턴할거라 삭제 작업 전 캐싱

        // 1. 삭제하려는 노드의 자식 서브트리가 0 개 일때 (=단말노드)
        if (tree->left == NULL && tree->right == NULL) {
            if (parent->left == tree)
                parent->left = NULL;
            if (parent->right == tree)
                parent->right = NULL;
        }
        // 2. 삭제하려는 노드의 자식 서브트리가 1 개 일때
        else if (tree->left == NULL || tree->right == NULL) {
            Node* temp = NULL;
            if (tree->left != NULL)
                temp = tree->left;
            else
                temp = tree->right;

            if (parent->left == tree)
                parent->left = temp;
            else
                parent->right = temp;
        }
        // 3. 삭제하려는 노드의 자식 서브트리가 2 개 일 때
        else if (tree->left != NULL && tree->right != NULL) {
            Node* minNode_Of_BiggerNodes = BST_SearchMinNode(tree->right);
            minNode_Of_BiggerNodes = BST_RemoveNode(tree, NULL, minNode_Of_BiggerNodes->data);
            tree->data = minNode_Of_BiggerNodes->data;
        }
    }

    return removedNode;
}


✈ 우선 삭제할 노드 탐색
Node* BST_RemoveNode(Node* tree, Node* parent, int target)
{
    // target과 일치하는 노드는 삭제할 노드다.
    // 삭제할 노드의 위치가 되는 노드는 tree 에, 삭제할 노드의 부모는 parent 에 저장된다.
    // 삭제할 노드(tree)는 removedNode 에 복사해 옮겨두고 나중에 이를 리턴한다.
    // tree 의 값을 새롭게 세팅해 이제 삭제되고 새로운 노드로 대체된 것처럼 연산해준다. 

    if (tree == NULL) // 비어있는 트리의 경우엔 삭제 불가
        return NULL;
        
    Node* removedNode = NULL; // 이 곳에 삭제할 노드를 저장할 것
    
    /* 삭제할 노드 탐색하기*/
    if (tree->data > target) 
        removedNode = BST_RemoveNode(tree->left, tree, target); // 왼쪽으로 더 내려감. (왼쪽 서브트리의 부모는 나 자신인 tree, 왼쪽 서브트리 당사자는 tree->left) 찾으면 재귀 함수들이 끝나면서 삭제할 그 노드를 건너건너 리턴받게 될 것.
    else if (tree->data < target)
        removedNode = BST_RemoveNode(tree->right, tree, target); // 왼쪽으로 더 내려감. (오른쪽 서브트리의 부모는 나 자신인 tree, 오른쪽 서브트리 당사자는 tree->right) 찾으면 재귀 함수들이 끝나면서 삭제할 그 노드를 건너건너 리턴받게 될 것.
    else if (tree->data == target) { // 삭제할 노드 드디어 찾음! tree 가 바로 삭제할 노드
        removedNode = tree; // 삭제된 노드 리턴할거라 삭제 작업 전, removedNode에 캐싱해놓기.

우선 삭제할 노드를 찾아야한다. target 과 일치하는 data를 가지고 있는 노드를 탐색해야 한다!

  • Node* BST_RemoveNode(Node* tree, Node* parent, int target)
    • 항상 parent는 tree의 부모를 가리킨다.
      • 삭제할 노드의 부모와 삭제할 노드의 자식을 연결지어 주어야 하기 때문에 (즉, 할머니와 손녀끼리!) 즉!! 부모 노드의 left 혹은 right를 업데이트 해주어야 하기 때문에 삭제할 노드의 부모가 누군지에 대한 정보도 항상 가지고 있어야 한다.
      • 루트 노트부터 target과 일치하는 노드를 찾기 위해 한 레벨씩 내려오면서 tree는 현재의 노드, parent는 tree의 이전 노드이자 tree의 부모가 된다. tree와 paretn는 내려오면서 점점 업뎃 됨
    • else if (tree->data == target) 여기에 걸리면
      • 이때의 tree는 삭제할 노드.
      • 이때의 parent는 삭제할 노드의 부모 노드.
      • removedNode = tree
        • 삭제할 노드를 리턴할 것이라서 미리 removedNode에 옮겨 놓는다.
        • 이제 tree는 내용이 바뀌어(data, left, right 새롭게 세팅될 것) 새로운 노드로 탈바꿈 될 것이다.
          • 삭제되는거나 다름 없음!


1️⃣ 삭제할 노드의 서브트리가 0 개일 때 (Lead 노드일 때)
    else if (tree->data == target) { // 삭제할 노드 찾음
        removedNode = tree; // 삭제된 노드 리턴할거라 삭제 작업 전 캐싱

        // 1. 삭제하려는 노드의 자식 서브트리가 0 개 일때 (=단말노드)
        if (tree->left == NULL && tree->right == NULL) {
            if (parent->left == tree)
                parent->left = NULL;
            if (parent->right == tree)
                parent->right = NULL;
        }

image

삭제할 대상인 tree의 부모인 parent의 left 혹은 right에 tree가 저장되어 있을 텐데, parent의 left 혹은 right를 NULL 로 세팅해주면 된다. 즉 tree가 왼쪽 자식이면 parent의 왼쪽 자식이 없다고 업데이트 해주고, tree가 오른쪽 자식이면 parent의 오른쪽 자식이 없다고 업데이트 해주어 이렇게 연결을 끊어버리면 된다. 현재 삭제할 노드는 tree에서도, removedNode에서도 참조하고 있기 때문에 연결 끊어주어도 나중에 삭제할 노드를 리턴하는데 문제 없다. removedNode에서 참조 중이니까 미아 안됨..!


2️⃣ 삭제할 노드의 서브트리가 1 개 일 때
    else if (tree->data == target) { // 삭제할 노드 찾음
        // ...

        // 2. 삭제하려는 노드의 자식 서브트리가 1 개 일때
        else if (tree->left == NULL) || tree->right == NULL) {
            Node* temp = NULL;
            if (tree->left != NULL)
                temp = tree->left;
            else
                temp = tree->right;

            if (parent->left == tree)
                parent->left = temp;
            else
                parent->right = temp;
        }

image

  • tree가 왼쪽 자식 하나 있다면
    • 삭제할 노드인 tree가 parent의 왼쪽 자식이라면 parent의 왼쪽 자식은 tree의 왼쪽 자식으로 세팅 -삭제할 노드인 tree가 parent의 오른쪽 자식이라면 parent의 오른쪽 자식은 tree의 왼쪽 자식으로 세팅
  • tree가 오른쪽 자식 하나 있다면
    • 삭제할 노드인 tree가 parent의 왼쪽 자식이라면 parent의 왼쪽 자식은 tree의 오른쪽자식으로 세팅 -삭제할 노드인 tree가 parent의 오른쪽 자식이라면 parent의 오른쪽 자식은 tree의 오른쪽 자식으로 세팅


3️⃣ 삭제할 노드의 서브트리가 2 개 일 때
Node* BST_SearchMinNode(Node* tree)
{
    if (tree == NULL)
        return NULL;

    if (tree->left == NULL)
        return tree;
    else
        return BST_SearchMinNode(tree->left);
}

삭제될 노드의 자리에는 이진 탐색 트리의 규칙을 만족할 수 있는 노드로 교체가 되어야 한다. 즉, 삭제될 노드의 왼쪽 서브트리보다 크고, 삭제될 노드의 오른쪽 서브트리보단 작은 규칙이 만족되는 노드여야 한다.

  • 삭제될 노드 자리에 올 수 있는 후보 노드
    • 1️⃣ 삭제될 노드의 오른쪽 서브트리에서의 가장 왼쪽에 위치한 노드
      • 삭제될 노드의 왼쪽 서브트리보단 크다는 것이 보장된다. 오른쪽 서브트리에 속해있는 노드이니까!
      • 이 후보 노드가 채택된다면 오른쪽 서브트리보다 작다는 것이 보장된다. 삭제될 노드의 기존 오른쪽 서브트리 내에서 가장 최소값이였으니까! (가장 왼쪽)
    • 2️⃣ 삭제될 노드의 왼쪽 서브트리에서의 가장 오른쪽에 위치한 노드
      • 삭제될 노드의 왼쪽 서브트리보단 크다는 것이 보장된다. 삭제될 노드의 기존 왼쪽 서브트리 내에서 가장 최대값이였으니까! (가장 오른쪽)
      • 삭제될 노드의 오른쪽 서브트리보단 작다는 것이 보장된다. 왼쪽 서브트리에 속해있는 노드이니까!

1️⃣ 2️⃣ 둘 중 아무거나 채택해도 괜찮다. 삭제할 노드를 1️⃣ 로 교체하겠다고 결정 후 위의 함수를 작성.

  • Node* BST_SearchMinNode(Node* tree)
    • 해당 tree의 가장 왼쪽의 왼쪽의 왼쪽!! 서브트리 노드를 리턴한다.
    • BST_SearchMinNode(tree->right); 호출 👉 오른쪽 서브트리에서의 가장 왼쪽에 위치한 노드 (= 오른쪽 서브트리에서의 가장 최소값)
    else if (tree->data == target) { // 삭제할 노드 찾음
        // ...

        // 3. 삭제하려는 노드의 자식 서브트리가 2 개 일 때
        else if (tree->left != NULL && tree->right != NULL) {
            Node* minNode_Of_BiggerNodes = BST_SearchMinNode(tree->right);
            minNode_Of_BiggerNodes = BST_RemoveNode(tree, NULL, minNode_Of_BiggerNodes->data);
            tree->data = minNode_Of_BiggerNodes->data;
        }

image

  • minNode_Of_BiggerNodes : 삭제할 노드 tree의 오른쪽 서브트리 中 가장 최소값 노드
  • minNode_Of_BiggerNodes를 삭제한다.
    • minNode_Of_BiggerNodes 또한 서브트리 몇 개를 가지고 있는 노드인지 모르는 일! 그래서 재귀적으로 BST_RemoveNode 를 호출해서 minNode_Of_BiggerNodes 노드를 삭제하면 된다.
  • tree에 minNode_Of_BiggerNodes를 덮어씌운다.
    • tree의 기존 왼쪽 오른쪽 자식은 유지되므로 사실상 data만 바꿔치기 하면 된다.


🔥 순회

✈ 전위 순회

내려가기 전 출력 (두 서브트리 순회 전)

void BST_PreOrder(Node* tree, vector<int>& pre)
{
    if (tree == NULL)
        return;
    pre.push_back(tree->data); // 출력
    BST_PreOrder(tree->leftChild, pre);
    BST_PreOrder(tree->rightChild, pre);
}


✈ 중위 순회

왼쪽 서브트리 순회 전부 마치고 돌아온 후 출력 후 오른쪽 서브트리 순회

이진 검색 트리를 “중위 순회” 하면 정렬된 순서대로 출력이 된다.⭐


void BST_InOrder(Node* tree, vector<int>& pos)
{
    if (tree == NULL)
        return;
    BST_InOrder(tree->leftChild, pos);
    pos.push_back(tree->data); // 출력
    BST_InOrder(tree->rightChild, pos);
    
}


✈ 후위 순회

왼쪽 서브트리 순회, 오른쪽 서브트리 순회 전부 다 마치고 돌아온 후에 출력


void BST_PostOrder(Node* tree, vector<int>& pos)
{
    if (tree == NULL)
        return;
    BST_PostOrder(tree->leftChild, pos);
    BST_PostOrder(tree->rightChild, pos);
    pos.push_back(tree->data); // 출력
}



🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우 
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄

맨 위로 이동하기

Algorithm 카테고리 내 다른 글 보러가기

댓글 남기기

최근 글 10 개 :)