[Programming/Algorithm] 이진 탐색 트리 (Binary Search Tree)

이진 탐색 트리는 '탐색에 효율적인 자료구조'이다 그리고 '이진 트리'의 일종이다.

이진 트리의 구조를 보면, 트리는 탐색에 효율적이라는 사실을 쉽게 알 수 있다. 이진 트리에 저장된 데이터의 수가 10억 개 수준에 이른다 해도 트리의 높이는 30을 넘지 않기 때문이다. 그렇다면 이것이 탐색에 있어서 어떤 의미를 지니겠는가?
예를 들어 연결 리스트에 10억 개의 데이터가 저장되어 있다고 가정해보자. 그리고 찾는 데이터가 이 리스트의 정중앙에 위치한다는 정보를 얻었다고 가정해보자. 이는 분명 유용한 정보이다. 하지만 이러한 정보를 가지고 있음에도 불구하고 데이터에 이르기 위해서는 약 5억 개의 노드를 지나야 한다.
반면 이진 트리의 경우에는 위치를 알고 있다면, 즉 데이터에 이르는 길을 알고 있다면 루트 노드에서부터 단말 노드에 이르기까지 총 30개의 노드를 지나는 과정에서 원하는 데이터를 찾을 수 있다. 물론 여기에는 다음과 같은 가정이 존재한다.

"이진 트리는 단말 노드에 이르는 길의 갈래가 매우 많다. 따라서 찾는 데이터가 존재하는 제대로 된 길을 선택할 수 있어야 한다."

위의 가정으로 인해 '이진 탐색 트리'는 어떠한 특성의 트리인지 대략 짐작이 가능할 것이다. 이진 탐색 트리는 다음과 같은 특성을 지닌다.

"이진 탐색 트리에는 데이터를 저장하는 규칙이 있다. 그리고 그 규칙은 특정 데이터의 위치를 찾는데 사용할 수 있다."

다시 말해 '이진 트리'에 '데이터의 저장 규칙'을 더해놓은 것이 '이진 탐색 트리'이다. 다음은 이진 탐색 트리가 되기 위한 조건이다. 참고로 '팀색 키'는 정수라고 가정한다. 이러한 탐색 키를 간단히 키(key)로 표현한다.

• 이진 탐색 트리의 노드에 저장된 키(key)는 유일하다.
• 루트 노드의 키가 왼쪽 서브 트리를 구성하는 어떠한 노드의 키보다 크다.
• 루트 노드의 키가 오른쪽 서브 트리를 구성하는 어떠한 노드의 키보다 작다.
• 왼쪽과 오른쪽 서브 트리도 이진 탐색 트리이다.

키(key)에는 유일하다는 의미가 포함되어 있음을 알 수 있다. Database의 Primary Key(PK)라고 생각하면 되겠다. 그럼 위의 조건을 만족하는 트리의 예는 다음 그림과 같다.

이진 탐색 트리의 예

위 그림에서 보이듯이 루트 노드의 왼쪽 서브 트리에 저장된 값들은 12보다 작고, 오른쪽 서브 트리에 저장된 값들은 12보다 크다. 그런데 위의 그림을 통해 다음 수식이 어디서나 만족함을 알 수 있다.

왼쪽 저식 노드의 키 < 부모 노드의 키 < 오른쪽 자식 노드의 키

그리고 이 수식이 이진 탐색 트리의 구현에 더 직접적으로 도움이 되는 결론이다. 그럼 위 그림의 이진 탐색 트리를 대상으로 숫자 10을 저장한다고 가정해보자. 그러면 루트 노드를 시작으로 하여 다음의 과정을 거쳐서 저장될 위치를 결정하게 된다.

• 1단계 : 10 < 12 이므로 왼쪽 자식 노드로 이동
• 2단계 : 10 > 8 이므로 오른쪽 자식 노드로 이동
• 3단계 : 10 > 9 이므로 오른쪽 자식 노드로 이동
• 4단계 : 오른쪽에 아무것도 없으니 그 위치에 저장

따라서 숫자 10은 다음 그림에서 보이듯이 숫자 9의 오른쪽 자식 노드로 저장이 된다.

데이터 추가 후의 이진 탐색 트리

이렇듯 이진 탐색 트리는 '작으면 왼쪽으로, 크면 오른쪽으로'라는 원칙을 기준으로 데이터를 삽입한다. 따라서 탐색의 과정에서도 이를 그대로 따르면 된다. 찾는 키의 값이 비교대상보다 작으면 왼쪽 자식 노드로, 찾는 키의 값이 비교대상보다 크면 오른쪽 자식 노드로 이동하는 것이다. 때문에 이진 탐색 트리는 탐색의 과정에서 길을 잃을 일이 없다. 그리고 몇 단계 지나지 않아서 탐색 대상을 찾을 수 있다. 그러니 탐색의 효율은 두말할 필요가 없다.

---

이진 탐색 트리의 헤더파일

BinaryTree2.cpp

0.00MB

BinaryTree2.h

0.00MB

#ifndef __BINARY_SEARCH_TREE_H__
#define __BINARY_SEARCH_TREE_H__

#include"BinaryTree2.h"

typedef BTData BSTData;

// BST의 생성 및 초기화
void BSTMakeAndInit(BTreeNode** pRoot);

// 노드에 저장된 데이터 반환
BSTData BSTGetNodeData(BTreeNode* bst);

// BST를 대상으로 데이터 저장(노드의 생성과정 포함)
void BSTInsert(BTreeNode** pRoot, BSTData data);

// BST를 대상으로 데이터 검색
BTreeNode* BSTSearch(BTreeNode* bst, BSTData target);


#endif

이진 탐색 트리의 핵심 연산 세 가지는 다른 자료구조들과 마찬가지로 삽입, 삭제 그리고 탐색이다. 

그럼 간단한 main 함수를 통해 위의 두 함수와 헤더파일에 선언된 또 다른 두 함수의 사용방법을 보자.

#include <iostream>
#include "BinarySearchTree.h"

using std::cout;
using std::cin;
using std::endl;


int main() {
    // bstRoot는 BST의 루트 노드를 가리킨다.
    BTreeNode* bstRoot;
    BTreeNode* sNode;

    // Binary Search Tree의 생성 및 초기화
    BSTMakeAndInit(&bstRoot);

    // bstRoot에 1, 2, 3을 저장
    BSTInsert(&bstRoot, 1);
    BSTInsert(&bstRoot, 2);
    BSTInsert(&bstRoot, 3);

    // 1이 저장된 노드를 탐색한다.
    sNode = BSTSearch(bstRoot, 1);
    if (sNode == nullptr) {
        cout << "탐색 실패" << endl;
    }
    else {
        cout << "탐색에 성공한 키의 값: " << BSTGetNodeData(sNode) << endl;
    }

    return 0;
}

위의 main함수에서 보이듯이 다음과 같이 BSTMakeAndInit함수가 호출되고 나면, 이진 탐색 트리의 생성 및 초기화가 완료된 것으로 간주한다.

이때부터 bstRoot는 생성도니 이진 탐색 트리를 지칭하는 이름이 된다. 그래서 트리에 데이터를 추가할 때는 다음과 같이 함수를 호출한다.

BSTInsert(&bstRoot, 1);

위 문장에서 보이듯, 이진 탐색 트리에 데이터를 저장하기 위해서 직접 노드를 생성할 필요가 없다. 노드의 생성과 위치의 선정 및 저장은 BSTInsert함수 내에서 이뤄지기 때문이다. 그리고 다음 문장에서 보이듯이 데이터의 탐색도 유사한 방식으로 진행된다.

sNode = BSTSearch(bstRoot, 1);

탐색의 결과, 목표한 대상을 찾았다면 이를 저장하고 있는 노드의 주소 값이 반환된다. 그리고 main함수에서 보였듯이 BSTGetNodeData 함수를 통해 노드에 저장된 값을 얻을 수도 있다.

---

이진 탐색 트리의 구현: 삽입과 탐색

이진 탐색 트리의 삽입과 탐색은 어렵지 않다. 몇몇 사례를 통해 그 과정을 보자. 먼저 세 개의 노드로 구성된 트리에 숫자 11과 10의 추가과정을 순서대로 살펴보자.

이진 탐색 트리 대상의 11과 10의 저장과정

위 그림을 통해 '비교대상보다 값이 작으면 왼쪽 자식 노드로, 값이 크면 오른쪽 자식 노드로 이동한다'는 기본적인 사실 이외에 강조하고픈 것이 하나 더 있다. 그것은 다음과 같다.

"비교대상이 없을 때까지 내려간다. 그리고 비교대상이 없는 그 위치가 새 데이터가 저장될 위치이다."

위 그림에 이어서 29와 22를 저장하는 예를 하나 더 보자. 

이진 탐색 트리 대상의 29와 22의 저장과정

새 데이터의 저장을 담당하는 BSTInsert함수를 보도록하자. 위의 과정을 그대로 코드로 옮긴 결과이다.

void BSTInsert(BTreeNode** pRoot, BSTData data) {
    BTreeNode* pNode = nullptr;     // parent node
    BTreeNode* cNode = *pRoot;      // current node
    BTreeNode* nNode = nullptr;     // new node

    // 새로운 노드가 추가될 위치를 찾는다.
    while (cNode != nullptr) {
        // 데이터(키)의 중복을 허용하지 않음
        if (data == GetData(cNode)) {
            return;
        }

        pNode = cNode;

        if (GetData(cNode) > data) {
            cNode = GetLeftSubTree(cNode);
        }
        else {
            cNode = GetRightSubTree(cNode);
        }
    }

    // pNode의 자식 노드로 추가할 새 노드의 생성
    nNode = MakeBTreeNode();
    SetData(nNode, data);

    // pNode의 자식 노드로 새 노드를 추가
    if (pNode != nullptr) {     // 새 노드가 루트 노드가 아니라면
        if (data < GetData(pNode)) {
            MakeLeftSubTree(pNode, nNode);
        }
        else {
            MakeRightSubTree(pNode, nNode);
        }
    }
    else {      // 새 노드가 루트 노드라면
        *pRoot = nNode;
    }
}

while문을 주목해보자. 이 while문이 하는 일은 저장할 값의 크기에 따라 왼쪽 또는 오른쪽 자식 노드로 이동을 하면서 새 노드의 저장위치를 찾는 것이다.

while(cNode != nullptr) { ... }

따라서 이 while문을 빠져나오면 cNode에는 새 노드가 저장될 위치정보가 담긴다. 그런데 이 위치에 노드를 저장하기 위해 필요한 것은, 이 위치를 자식으로 하는 부모 노드의 주소 값이다(부모 노드에 자식 노드의 주소 값이 저장되므로). 실제로 이어지는 if~else 구문에서 부모 노드의 주소 값이 담긴 pNode를 기반으로 자식 노드를 추가하고 있다. 그래서 pNode를 통해 부모 노드의 주소 값을 유지하는 것이다.

이어서 탐색을 담당하는 BSTSearch 함수를 살펴보자. 탐색의 과정은 삽입의 과정을 근거로 하기에 별도의 설명이 필요 없다.

BTreeNode* BSTSearch(BTreeNode* bst, BSTData target){
  BTreeNode* cNode = bst;
  BSTData cd;
  
  while(cNode != nullptr){
    cd = GetData(cNode);
    
    if(target == cd){
      return cNode;
    }
    else if(target < cd){
      cNode = GetLeftSubTree(cNode);
    }
    else{
      cNode = GetRightSubTree(cNode);
    }
  }
  
  return nullptr;
}

위 함수에 삽입된 while문에서도 비교대상의 노드보다 값이 작으면 왼쪽 자식 노드로, 값이 크면 오른쪽 자식 노드로 이동하고 있다. 그리고 이렇게 이동을 하면, 탐색을 위한 길을 제대로 가는 것이다. 그럼에도 불구하고 더 이상 이동할 자식 노드가 없다면, 이는 찾는 데이터가 존재하지 않는 상황이다. 그래서 이를 바탕으로 whild문의 탈출 조건을 구성되어 있다.

---

이진 탐색 트리의 삭제구현 : 삭제에 대한 이론적 설명과 구현 일부

이진 탐색 트리의 삭제는 단순하지 않다. 다음 그림을 통해 삭제의 과정이 복잡한 이유를 알아보자.

이진 탐색 트리에서 삭제가 어려운 이유

위 그림의 이진 탐색 트리에서 8이 담긴 노드를 삭제한다고 가정해보자. 이 상황에서 그냥 이 노드만 삭제하면 그만인가? 아니다. 그 자리를 누군가 대신 채워야만 이진 탐색 트리가 유지된다. 즉 이진 탐색 트리의 삭제가 아려운 이유는 다음과 같다.

"이진 탐색 트리에서 임의의 노드를 삭제하는 경우, 삭제 후에도 이진 탐색 트리가 유지되도록 빈 자리를 채워야 한다."

삭제 대상이 단말 노드라면 그 노드만 삭제하면 그만이다. 하지만 단말 노드가 아니라면 위에서 말한 것처럼 삭제할 노드를 무엇으로 대신할지 고민해야 한다. 다음은 이진 탐색 트리의 삭제에 대한 경우의 수이다.

• 상황 1 : 삭제할 노드가 단말 노드인 경우
• 상황 2 : 삭제할 노드가 하나의 자식 노드를(하나의 서브 트리를) 갖는 경우
• 상황 3 : 삭제할 노드가 두 개의 자식 노드를(두 개의 서브 트리를) 갖는 경우

이렇듯 삭제에 대한 경우의 수는 세 가지이다. 하지만 구현방법에 따라서, 삭제 대상이 루트 노드인 경우와 그렇지 않은 경우를 나눠야 하기 때문에 삭제에 대한 경우의 수는 최대 여섯 가지로 구분할 수도 있다. 

먼저 단말 노드를 삭제하는 '상황 1'에서의 삭제방법을 그림을 통해 살펴보자.

단말 노드의 삭제방법

위 그림에서 보이듯이 '상황 1'에서는 삭제 대상인 단말 노드를 삭제하는 것으로 삭제의 과정이 완료된다. 따라서 다음과 같이 코드를 구성하면 된다.

// dNode와 pNode는 각각 삭제할 노드와 이의 부모 노드를 가리키는 포인터 변수
if(삭제할 노드가 단말 노드라면){
  if(GetLeftSubTree(pNode) == dNode){  // 삭제할 노드가 왼쪽 자식 노드라면
    RemoveLeftSubTree(pNode);          // 왼쪽 자식 노드 트리에서 제거
  } 
  else{                                // 삭제할 노드가 오른쪽 자식 노드라면
    RemoveRightSubTree(pNode);         // 오른쪽 자식 노드 트리에서 제거
  }
}

위에서 호출하고 있는 Remove~로 시작하는 두 함수는 다음과 같다.

• RemoveLeftSubTree(pNode) : pNode가 가리키는 노드의 왼쪽 자식 노드 트리에서 제거
• RemoveRightSubTree(pNode) : pNode가 가리키는 노드의 오른쪽 자식 노드 트리에서 제거

다음은 '상황 2'에서의 삭제방법이다. 부모 노드와 자식 노드를 연결하는 작업만 추가하면 된다.

하나의 자식 노드 또는 서브 트리를 갖는 노드의 삭제방법

이렇듯 '상황 2'에서는 부모 노드와 자식 노드를 연결하는 것이 관건이다. 하지만 여기에도 한가지 주의할 사항이 있다.

"위 그림의 왼쪽 트리에서, 10이 저장된 노드가 왼쪽 노드이건 오른쪽 자식 노드인건, 이에 상관없이 10이 저장된 노드는 8이 저장된 노드의 오른쪽 자식 노드가 되어야 한다."

그 이유는 10이 저장된 노드가 9가 저장된 노드를 대신하는 관계이기 때문이다. 즉 9가 저장된 노드를 대신한다고 생각하면 된다. 그리고 이러한 이유 때문에 아래에서 보이는 '상황 2'를 처리하는 코드에는 두 개의 if~else문이 등장한다.

// dNode와 pNode는 각각 삭제할 노드와 이의 부모 노드를 가리키는 포인터 변수
if(삭제할 노드가 하나의 자식 노드를 지닌다면){
  BTreeNode* dcNode;    // 삭제 대상의 자식 노드를 가리키는 포인터 변수
  
  // 삭제 대상의 자식 노드를 찾는다.
  if(GetLeftSubTree(dNode) != nullptr){    // 자식 노드가 왼쪽에 있다면,
    dcNode = GetLeftSubTree(dNode);
  }
  else{    // 자식 노드가 오른쪽에 있다면
    dcNode = GetRightSubTree(dNode);
  }
  
  // 삭제 대상의 부모 노드와 자식 노드를 연결한다.
  if(GetLeftSubTree(pNode) == dNode){    // 삭제 대상이 왼쪽 자식 노드이면
    ChangeLeftSubTree(pNode, dcNode);
  }
  else{    // 삭제 대상이 오른쪽 자식 노드이면,
    ChangeRightSubTree(pNode, dcNode);    // 오른쪽으로 연결
  }
}   

• ChangeLeftSubTree : MakeLeftSubTree함수와 유사한 함수
• ChangeRightSubTree : MakeRightSubTree함수와 유사한 함수

마지막으로 '상황 3'에서의 삭제방법을 살펴보자. 

두 개의 자식 노드 또는 서브 트리를 갖는 노드의 삭제

위의 트리에서 8을 삭제하는 경우 이를 대체할 후보로 다음 두 개의 노드를 꼽을 수 있다.

• 8이 저장된 노드의 왼쪽 서브 트리에서 가장 큰 값인 7을 저장한 노드
• 8이 저장된 노드의 오른쪽 서브 트리에서 가장 작은 값인 9를 저장한 노드

위 그림에서 삭제 대상을 7 또는 9를 저장한 노드로 각각 대체했을 때의 결과는 다음과 같다. 이 그림에서 대체 후에도 이진 탐색 트리가 유지됨을 주목하자.

대체 후에도 유지되는 이진 탐색 트리

이렇듯 삭제할 노드의 왼쪽 서브 트리에서 가장 큰 값이나, 삭제할 노드의 오른쪽 서브 트리에서 가장 작은 값을 저장한 노드로 대체하면 된다. 물론 서브 트리에서 가장 큰 값이나 가장 작은 값을 저장한 노드를 찾는 것은 어렵지 않은데, 다음 그림을 통해 그 방법을 보자.

이진 탐색 트리의 가장 작은 값과 가장 큰 값

위 그림에서 보이듯이 가장 큰 값을 찾을 때는 null을 만날 때까지 계속해서 오른쪽 자식 노드로 이동하면 되고, 가장 작은 값을 찾을 때는 null을 만날 때까지 계속해서 왼쪽 자식 노드로 이동하면 된다.

'상황 3'에서는 삭제 대상을 '왼쪽 서브 트리에서 가장 큰 값을 저장한 노드'나 '오른쪽 서브 트리에서 가장 작은 값을 저장한 노드'로 대체하면 된다. 어느 것으로 대체해도 이진 탐색 트리의 유지에는 지장이 없으므로 다음의 방법을 택하기로 하자.

"삭제할 노드의 오른쪽 서브 트리에서 가장 작은 값을 지니는 노드를 찾아서 이것으로 삭제할 노드를 대체한다."

두 개의 자식 노드를 갖는 노드의 삭제

위 그림에서 보이는 삭제의 결과를 이루기 위해 해야 할 일은 다음과 같다.

"삭제가 되는 8이 저장된 노드를 9가 저장된 노드로 대체한다. 그리고 이로 인해서 생기는 빈 자리는 9가 저장된 노드의 자식 노드로 대체한다."

그리고 이를 위해 다음의 방법을 적용해보자.

두 개의 자식 노드를 갖는 노드의 삭제과정

위 그림에서는 8이 저장된 노드의 위치에 9가 저장된 노드를 가져다 놓지 않고, 값의 대입을 통해 노드의 교체를 대신하고 있다. 이 방법이 여러모로 편리하다. 이 방법을 사용할 경우, 삭제 대상인 8이 저장된 노드의 부모 노드와 자식 노드의  연결을 유지하기 위해서 별도의 코드를 삽입할 필요가 없기 때문이다.

'상황 3'에서의 삭제과정을 정리해보자.

• 단계 1 : 삭제할 노드를 대체할 노드를 찾는다.
• 단계 2 : 대체할 노드에 저장된 값을 삭제할 노드에 대입한다.
• 단계 3 : 대체할 노드의 부모 노드와 자식 노드를 연결한다.

위의 세 단계를 코드로 옮겨보자. 

// dNode와 pNode는 각각 삭제할 노드와 이의 부모 노드를 가리키는 포인터 변수
if(삭제할 노드가 두 개의 자식 노드를 지닌다면){
  BTreeNode* mNode = GetRightSubTree(dNode);    // mNode는 대체 노드를 가리킴
  BTreeNode* mpNode = dNode;    // mpNode는 대체 노드의 부모 노드를 가리킴
  ...
  // 단계 1. 삭제 대상의 대체 노드를 찾는다.
  while(GetLeftSubTree(mNode) != nullptr){
    mpNode = mNode;
    mNode = GetLeftSubTree(mNode);
  }
  
  // 단계 2. 대체할 노드에 저장된 값을 삭제할 노드에 대입한다.
  SetData(dNode, GetData(mNode));
  
  // 단계 3. 대체할 노드의 부모 노드와 자식 노드를 연결한다.
  if(GetLeftSubTree(mpNode) == mNode){    // 대체할 노드가 왼쪽 자식 노드라면
    // 대체할 노드의 자식 노드를 부모 노드의 왼쪽에 연결
    ChangeLeftSubTree(mpNode, GetRightSubTree(mNode));
  }
  else{    // 대체할 노드가 오른쪽 자식 노드라면
    // 대체할 노드의 자식 노드를 부모 노드의 오른쪽에 연결
    ChangeRightSubTree(mpNode, GetRightSubTree(mNode));
  }
  ...
}

다음 문장을 유심히 살펴보자.

if(GetLeftSubTree(mpNode) == mNode){
  // 대체할 노드의 자식 노드를 부모 노드의 왼쪽에 연결
  ChangeLeftSubTree(mpNode, GetRightSubTree(mNode));
}
else{
  // 대체할 노드의 자식 노드를 부모 노드의 오른쪽에 연결
  ChangeRightSubTree(mpNode, GetRightSubTree(mNode));
}

GetRightSubTree함수가 두 번 호출되었으니, 아무래도 이 중 하나는 GetLeftSubTree함수의 호출로 대체해야 뭔가 짝이 맞을 것 같은 생각이 들 수 있다. 하지만 이는 잘못되지 않았다. 대체할 노드의 자식 노드는 항상 오른쪽에(오른쪽 자식 노드로) 존재하기 때문이다. 그 이유는 다음과 같다.

"삭제할 노드의 오른쪽 서브 트리에서 가장 작은 값을 지니는 노드를 찾아서 이것으로 삭제할 노드를 대체한다."

가장 작은 값을 지니는 노드를 찾으려면 nullptr을 만날 때까지 왼쪽 자식 노드로 계속해서 이동해야 한다. 그러니 자식 노드가 있다면 그것은 오른쪽 자식 노드이다.

---

이진 탐색 트리의 삭제 구현 : 삭제의 구현을 위한 이진 트리의 확장

// 왼쪽 자식 노드를 트리에서 제거, 제거된 노드의 주소 값이 반환된다.
BTreeNode* RemoveLeftSubTree(BTreeNode* bt);

// 오른쪽 자식 노드를 트리에서 제거, 제거된 노드의 주소 값이 반환된다.
BTreeNode* RemoveRightSubTree(BTreeNode* bt);

// 메모리 소멸을 수반하지 않고 main의 왼쪽 자식 노드를 변경한다.
void ChangeLeftSubTree(BTreeNode* main, BTreeNode* sub);

// 메모리 소멸을 수반하지 않고 main의 오른쪽 자식 노드를 변경한다.
void ChangeRightSubTree(BTreeNode* main, BTreeNode* sub);

// 메모리의 소멸을 수반하지 않고 main의 왼쪽 자식 노드를 변경한다.
void ChangeLeftSubTree(BTreeNode* main, BTreeNode* sub){
  main->left = sub;
}

// 메모리의 소멸을 수반하지 않고 main의 오른쪽 자식 노드를 변경한다.
void ChangeRightSubTree(BTreeNode* main, BTreeNode* sub){
  main->right = sub;
}

// 왼쪽 자식 노드 제거, 제거된 노드의 주소 값이 반환된다.
BTreeNode* RemoveLeftSubTree(BTreeNode* bt){
  BTreeNode* delNode;
  
  if(bt != nullptr){
    delNode = bt->left;
    bt->left = nullptr;
  }
  
  return delNode;
}

// 오른쪽 자식 노드 제거, 제거된 노드의 주소 값이 반환된다.
BTreeNode* RemoveRightSubTree(BTreeNode* bt){
  BTreeNode* delNode;
  
  if(bt != nullptr){
    delNode = bt->right;
    bt->right = nullptr;
  }
  
  return delNode;
}

보통 '삭제' 또는 '제거'라고 하면 반드시 메모리의 해제까지 담당해야 하는 것으로 오해하는 경우가 많다. 하지만 '삭제'와 '메모리의 해제'는 별개의 것이다. 삭제과정에서 메모리의 해제를 포함하는 경우도 있지만, 반드시 필요한 것은 아니며 오히려 포함해서는 안 되는 경우도 존재한다.

솔직히 말하면 삭제과정에서 메모리의 해제를 포함하지 않는 것이 더 일반적이다. 그래서 위의 두 함수도 단순히 왼쪽 자식 노드(왼쪽 서브 트리)와 오른쪽 자식 노드(오른쪽 서브 트리)를 트리에서 제거할 뿐, 메모리의 해제까지 이뤄지도록 정의하지 않았다. 대신에 주소 값의 반환을 통해서 메모리의 해제에 대한 책음을 함수를 호출한 영역으로 넘기고 있다.

// BinaryTree3.h

#ifndef __BINARY_TREE3_H__
#define __BINARY_TREE3_H__

typedef int BTData;

typedef struct _bTreeNode {
    BTData data;
    struct _bTreeNode* left;
    struct _bTreeNode* right;
} BTreeNode;

BTreeNode* MakeBTreeNode(void);
BTData GetData(BTreeNode* bt);
void SetData(BTreeNode* bt, BTData data);

BTreeNode* GetLeftSubTree(BTreeNode* bt);
BTreeNode* GetRightSubTree(BTreeNode* bt);

void MakeLeftSubTree(BTreeNode* main, BTreeNode* sub);
void MakeRightSubTree(BTreeNode* main, BTreeNode* sub);

typedef void VisitFuncPtr(BTData data);

void PreorderTraverse(BTreeNode* bt, VisitFuncPtr action);
void InorderTraverse(BTreeNode* bt, VisitFuncPtr action);
void PostorderTraverse(BTreeNode* bt, VisitFuncPtr action);

BTreeNode* RemoveLeftSubTree(BTreeNode* bt);
BTreeNode* RemoveRightSubTree(BTreeNode* bt);

void ChangeLeftSubTree(BTreeNode* main, BTreeNode* sub);
void ChangeRightSubTree(BTreeNode* main, BTreeNode* sub);

#endif

// BinaryTree3.cpp

#include <iostream>
#include <cstdlib>
#include "BinaryTree3.h"


BTreeNode* MakeBTreeNode(void) {
    BTreeNode* nd = (BTreeNode*)malloc(sizeof(BTreeNode));
    nd->left = nullptr;
    nd->right = nullptr;
    return nd;
}

BTData GetData(BTreeNode* bt) {
    return bt->data;
}

void SetData(BTreeNode* bt, BTData data) {
    bt->data = data;
}

BTreeNode* GetLeftSubTree(BTreeNode* bt) {
    return bt->left;
}

BTreeNode* GetRightSubTree(BTreeNode* bt) {
    return bt->right;
}

void MakeLeftSubTree(BTreeNode* main, BTreeNode* sub) {
    if (main->left != nullptr) {
        free(main->left);
    }
    main->left = sub;
}

void MakeRightSubTree(BTreeNode* main, BTreeNode* sub) {
    if (main->right != nullptr) {
        free(main->right);
    }
    main->right = sub;
}

void PreorderTraverse(BTreeNode* bt, VisitFuncPtr action) {
    if (bt == nullptr) {
        return;
    }
    action(bt->data);
    PreorderTraverse(bt->left, action);
    PreorderTraverse(bt->right, action);
}

void InorderTraverse(BTreeNode* bt, VisitFuncPtr action) {
    if (bt == nullptr) {
        return;
    }
    InorderTraverse(bt->left, action);
    action(bt->data);
    InorderTraverse(bt->right, action);
}

void PostorderTraverse(BTreeNode* bt, VisitFuncPtr action) {
    if (bt == nullptr) {
        return;
    }
    PostorderTraverse(bt->left, action);
    PostorderTraverse(bt->right, action);
    action(bt->data);
}

BTreeNode* RemoveLeftSubTree(BTreeNode* bt) {
    BTreeNode* delNode = nullptr;

    if (bt != nullptr) {
        delNode = bt->left;
        bt->left = nullptr;
    }

    return delNode;
}

BTreeNode* RemoveRightSubTree(BTreeNode* bt) {
    BTreeNode* delNode = nullptr;

    if (bt != nullptr) {
        delNode = bt->right;
        bt->right = nullptr;
    }

    return delNode;
}

void ChangeLeftSubTree(BTreeNode* main, BTreeNode* sub) {
    main->left = sub;
}

void ChangeRightSubTree(BTreeNode* main, BTreeNode* sub) {
    main->right = sub;
}

---

이진 탐색 트리의 삭제 구현 : 완전한 구현

• BinarySearchTree2.h : 이진 탐색 트리의 헤더파일
• BinarySearchTree2.cpp : 이진 탐색 트리의 소스파일

// BinarySearchTree2.h

#ifndef __BINARY_SEARCH_TREE2_H__
#define __BINARY_SEARCH_TREE2_H__

#include "BinaryTree3.h"

typedef BTData BSTData;

// 이진 탐색 트리의 생성 및 초기화
void BSTMakeAndInit(BTreeNode** pRoot);

// 노드에 저장된 데이터 반환
BSTData BSTGetNodeData(BTreeNode* bst);

// 이진 탐색 트리를 대상으로 데이터 저장(노드의 생성과정 포함)
void BSTInsert(BTreeNode** pRoot, BSTData data);

// 이진 탐색 트리를 대상으로 데이터 탐색
BTreeNode* BSTSearch(BTreeNode* bst, BSTData target);

// 트리에서 노드를 제거하고 제거된 노드의 주소 값을 반환한다.
BTreeNode* BSTRemove(BTreeNode** pRoot, BSTData target);

// 이진 탐색 트리에 저장된 모든 노드의 데이터를 출력한다.
void BSTShowAll(BTreeNode* bst);

#endif