Chap11. 이진 탐색 트리 (Binary Search Tree)

이진 트리의 높이는 데이터의 갯수가 N일때 logN이기 때문에 데이터의 갯수가 10억개여도 트리의 높이는 30 정도 이다.

따라서 탐색에 효율적이라는 것을 알수 있다.

 

이진 탐색 트리 

이진 탐색 트리:

https://en.wikipedia.org/wiki/Binary_search_tree

이진 탐색 트리는 이진 트리에 데이터를 저장하는 규칙들을 추가한 것이다.

 

 

이진 탐색 트리 되기 위한 조건 

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

 

이진 탐색트리에서 항상 만족하는 조건

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

 

이런 규칙 때문에 데이터를 삽입할때는 루트 노드에서부터 비교해가며 삽입하는 데이터가 더 작으면 왼쪽으로, 크면 오른쪽으로 이동해가며 자리를 찾으면 되고, 탐색할때도 마찬가지이다.

 

 

---

문제 11-1 [이진 탐색 트리의 조건]

이진 탐색 트리의 조건 중 다음 조건이 있다.

• 루트 노드의 키가 왼쪽 서브트리를 구성하는 어떠한 노드의 키보다 크다 
• 루트 노드의 키가 오른쪽 서브트리를 구성하는 어떠한 노드의 키보다 작다 

또한 이진 탐색 트리에서는 다음 조건이 항상 만족한다고 했다 

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

그렇다면 위의 이진 탐색 트리의 두 조건을 다음과 같이 바꾸면 안되는 이유가 무엇일까? 

• 부모 노드의 키가 왼쪽 자식 노드의 키보다 크다
• 부모 노드의 키가 오른쪽 자식 노드의 키보다 작다 

 

다음 트리를 보면 알 수 있다.

 

            12

         /         \

       9

    /      \

  4        18

 /   \

2  21

 

위 트리는 어느 위치에서든 부모 노드의 키가 왼쪽 자식 노드의 키보다 크고, 오른쪽 자식의 키보다 작다.

하지만 루트 노드인 12 보다 큰 값이 왼쪽 서브트리에 존재한다. (18, 21)

 

 

---

이진 탐색 트리 구현 

삽입 

삽입할때는 이진 탐색 트리의 조건에 따라 루트 노드에서부터 삽입되는 노드의 위치를 찾아가면 된다.

즉 새로운 노드의 값이 현재 위치의 노드의 값 보다 작으면 왼쪽, 크면 오른쪽으로 이동하면서 새로운 노드가 삽입될 위치를 찾아서 삽입한다. 이때 키의 중복은 허용하지 않는다.

 

탐색

탐색도 삽입과 똑같은 논리이다.

루트 노드에서부터 찾는 데이터의 값이 현재 위치 노드의 값보다 작으면 왼쪽으로 크면 오른쪽으로 이동하면서 찾는다.

이렇게 점점 트리 깊숙히 이동하다가 NULL을 만난다면 내가 찾는 데이터가 트리에 없다는 뜻이다. 

 

삭제

이진 탐색 트리에서 삭제는 삽입과 탐색과 달리 까다롭다. 

왜냐하면 노드의 삭제 이후에도 이진 탐색 트리의 조건들이 유지되어야 하기 때문이다. 

특정 노드를 삭제를 하는 경우를 생각해보면 다음과 같은 경우가 있을 것이다.

 

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

 

상황1  의 경우 단말노드이기 때문에 자식이 없는 경우이다. 

이 경우 그냥 단말노드를 삭제해버리면 그만이다. 

 

상황2 의 경우 삭제 되는 노드의 부모 노드와 자식 노드를 연결한다. 

다음과 같은 트리에서 9가 담긴 노드를 삭제한다고 생각해보자.

 

8

    \

      9

         \

           10

 

9를 삭제하고 8의 오른쪽 자식 노드가 10이 되도록 하면 될것이다.

 

8

   \ 

    10 

 

여기서 기억해야 할 것은 10이 저장된 노드가 9의 오른쪽 노드이건 왼쪽 노드이건 상관 없이, 9가 삭제된 이후에 8의 오른쪽 자식 노드가 되어야 한다는 것이다. 생각해보면 삭제 이전 10이 9의 왼쪽 노드였더라도 8 입장에서 보면 오른쪽 서브 트리에 해당한다.

 

 

상황3  

상황3은 삭제할 노드가 두 개의 서브 트리를 갖는 경우인데 이 경우가 좀 까다롭다.

우선 다음 트리를 보자.

 

               12

            /       \

        8

       /  \

    4     9

  /  \        \

2    7       10

 

위 트리에서 8이 담긴 노드를 삭제했을때도 이진 탐색 트리의 조건들이 유지되려면 어떻게 해야할까.

8의 왼쪽 서브 트리 중 가장 큰값 7과 오른쪽 서브 트리 중 가장 작은 값 9와 대체 하면 된다.  

이 두 경우 모두 노드 삭제 이후에도 이진 탐색 트리의 조건이 유지 가능하다.

따라서 오른쪽 서브 트리 중 가장 작은 값과 대체하기로 하겠다.

 

대체 하는 방법은 다음과 같다.

1. 삭제할 노드를 대체할 노드를 찾는다. // 위 트리에서는 9 

2. 대체할 노드에 저장된 값을 삭제할 노드에 대입한다. // 위 트리에서 8이 9가 된다 

3. 대체할 노드의 부모 노드와 자식 노드를 연결한다. // 원래 9가 있던 노드는 삭제되고, 원래 8이 였던 노드의 오른쪽 자식 노드가 10이 된다.

 

 

이진 탐색 트리 구현을 위해 이진 트리 헤더에 추가해야할 함수들 

// 이진 탐색 트리를 위한 함수들
// 왼쪽 자식 노드를 트리에서 제거, 제거된 노드 주소값 반환
BTreeNode *RemoveLeftSubTree(BTreeNode *bt);
BTreeNode *RemoveRightSubTree(BTreeNode *bt);
// 메모리 소멸을 수반하지 않고 main의 왼쪽 자식 노드를 sub 노드로 변경
void ChangeLeftSubTree(BTreeNode *main, BTreeNode *sub);
void ChangeRightSubTree(BTreeNode *main, BTreeNode *sub);

 

구현

BinaryTraversalTree.h 는 이진 트리 구현의 헤더이고, BinarySearchTree.h 는 이진 탐색 트리의 헤더이다.

이진 탐색트리는 이진 트리를 이용해서 구현한다.

 

BinaryTraversalTree.h

/*
 * 이진 트리 순회 함수 포함하는 연결 리스트 기반 이진트리 구현
 */

#ifndef CHAP08_BINARYTREETRAVERSAL_BINARYTREETRAVERSAL_H
#define CHAP08_BINARYTREETRAVERSAL_BINARYTREETRAVERSAL_H

typedef int BTData;

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

BTreeNode *MakeBTreeNode();
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);

// func pointer
typedef void (*VisitFuncPtr)(BTData data);

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

// 순회하며 메모리 해제
void DeleteTree(BTreeNode *bt);

// 이진 탐색 트리를 위한 함수들
// 왼쪽 자식 노드를 트리에서 제거, 제거된 노드 주소값 반환
BTreeNode *RemoveLeftSubTree(BTreeNode *bt);
BTreeNode *RemoveRightSubTree(BTreeNode *bt);
// 메모리 소멸을 수반하지 않고 main의 왼쪽 자식 노드를 sub 노드로 변경
void ChangeLeftSubTree(BTreeNode *main, BTreeNode *sub);
void ChangeRightSubTree(BTreeNode *main, BTreeNode *sub);

#endif //CHAP08_BINARYTREETRAVERSAL_BINARYTREETRAVERSAL_H

BinaryTraversalTree.c

#include "BinaryTreeTraversal.h"
#include <stdio.h>
#include <stdlib.h>

BTreeNode * MakeBTreeNode()
{
    BTreeNode *nd = (BTreeNode*)malloc(sizeof(BTreeNode));
    nd->left = NULL;
    nd->right = NULL;
    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)
{
    // main 트리의 left child가 이미 존재한다면 삭제하고 연결
    // 이 경우, 삭제되는 트리가 여러개의 노드로 이뤄져 있다면 메모리 누수가 발생한다
    if(main->left != NULL)
        free(main->left);

    main->left = sub;
}

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

    main->right = sub;
}

void PreorderTraverse(BTreeNode *bt, VisitFuncPtr action)
{
    if(bt == NULL) return;

    action(bt->data);
    PreorderTraverse(bt->left, action);
    PreorderTraverse(bt->right, action);
}

void InorderTraverse(BTreeNode *bt, VisitFuncPtr action)
{
    if(bt == NULL) return;

    InorderTraverse(bt->left, action);
    action(bt->data);
    InorderTraverse(bt->right, action);
}

void PostorderTraverse(BTreeNode *bt, VisitFuncPtr action)
{
    if(bt == NULL) return;

    PostorderTraverse(bt->left, action);
    PostorderTraverse(bt->right, action);
    action(bt->data);
}

void DeleteTree(BTreeNode *bt)
{
    if(bt == NULL) return;
    DeleteTree(bt->left);
    DeleteTree(bt->right);
    free(bt);
}

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

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

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

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

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

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

BinarySearchTree.h

/*
 * 이진 탐색 트리 (Binary Search Tree)
 */
#ifndef CHAP11_BINARYSEARCHTREE_BINARYSEARCHTREE_H
#define CHAP11_BINARYSEARCHTREE_BINARYSEARCHTREE_H

#include "BinaryTreeTraversal.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);


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

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

#endif //CHAP11_BINARYSEARCHTREE_BINARYSEARCHTREE_H

BinarySearchTree.c

#include "BinaryTreeTraversal.h"
#include <stdio.h>
#include <stdlib.h>

BTreeNode * MakeBTreeNode()
{
    BTreeNode *nd = (BTreeNode*)malloc(sizeof(BTreeNode));
    nd->left = NULL;
    nd->right = NULL;
    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)
{
    // main 트리의 left child가 이미 존재한다면 삭제하고 연결
    // 이 경우, 삭제되는 트리가 여러개의 노드로 이뤄져 있다면 메모리 누수가 발생한다
    if(main->left != NULL)
        free(main->left);

    main->left = sub;
}

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

    main->right = sub;
}

void PreorderTraverse(BTreeNode *bt, VisitFuncPtr action)
{
    if(bt == NULL) return;

    action(bt->data);
    PreorderTraverse(bt->left, action);
    PreorderTraverse(bt->right, action);
}

void InorderTraverse(BTreeNode *bt, VisitFuncPtr action)
{
    if(bt == NULL) return;

    InorderTraverse(bt->left, action);
    action(bt->data);
    InorderTraverse(bt->right, action);
}

void PostorderTraverse(BTreeNode *bt, VisitFuncPtr action)
{
    if(bt == NULL) return;

    PostorderTraverse(bt->left, action);
    PostorderTraverse(bt->right, action);
    action(bt->data);
}

void DeleteTree(BTreeNode *bt)
{
    if(bt == NULL) return;
    DeleteTree(bt->left);
    DeleteTree(bt->right);
    free(bt);
}

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

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

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

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

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

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

BinarySearchTreeMain.c

#include <stdio.h>
#include <stdlib.h>
#include "BinarySearchTree.h"

int main()
{
    BTreeNode *bstRoot;
    BTreeNode *sNode;

    BSTMakeAndInit(&bstRoot);

    BSTInsert(&bstRoot, 5);
    BSTInsert(&bstRoot, 8);
    BSTInsert(&bstRoot, 1);
    BSTInsert(&bstRoot, 6);
    BSTInsert(&bstRoot, 4);
    BSTInsert(&bstRoot, 9);
    BSTInsert(&bstRoot, 3);
    BSTInsert(&bstRoot, 2);
    BSTInsert(&bstRoot, 7);

    // 노드 하나씩 제거하면서 노드 중위 순회해서 출력
    BSTShowAll(bstRoot); printf("\n");
    sNode = BSTRemove(&bstRoot, 3);
    free(sNode);

    BSTShowAll(bstRoot); printf("\n");
    sNode = BSTRemove(&bstRoot, 8);
    free(sNode);

    BSTShowAll(bstRoot); printf("\n");
    sNode = BSTRemove(&bstRoot, 1);
    free(sNode);

    BSTShowAll(bstRoot); printf("\n");
    sNode = BSTRemove(&bstRoot, 6);
    free(sNode);

    BSTShowAll(bstRoot); printf("\n");
}