본문 바로가기
CS/자료구조

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

duqrlcks 2022. 3. 28. 10:24
반응형

이진 탐색 트리(Binary Search Tree)는 이진 트리의 특수 케이스로 아래와 같은 특징을 가진다. 

 

1. 각 노드는 고유한 값을 가진다.
2. 모든 노드의 왼쪽 서브트리는 자신보다 작은 값을 가지고, 오른쪽 서브트리는 자신보다 큰 값을 가진다. 

 

개념 자체는 매우 간단하다. 그런데 구현은 생각보다 까다롭다. 내가 공부하는 책에서는 좀 가볍게 넘어가는 부분이 있어서 대학 강의자료를 참고했다. 손으로 먼저 이진 탐색 트리를 만들어보고, 구현까지 해보는게 목표다. 포인터에 대한 이해가 확실하게 되어있지 않으면 구현 코드를 이해하기 어려울 수 있다. 

 

손으로 직접 해보기

J , E , T , A , H , M , V ,  P , N 을 순서대로 트리에 삽입해보자. 

<규칙>
루트 노드부터 시작
1) 삽입 값이 현재 노드값보다 작으면 왼쪽으로 
2) 삽입 값이 현재 노드값보다 크면 오른쪽으로
3) 더이상 갈 곳이 없으면 그 자리에 삽입

 

구현

1. 클래스 정의

template <class ItemType>
struct TreeNode{
    ItemType info;
    TreeNode* left;
    TreeNode* right;
};

enum OrderType {PRE_ORDER, IN_ORDER, POST_ORDER};

template <class ItemType>
class TreeType{
public:
    TreeType();
    ~TreeType();
    TreeType(const TreeType<ItemType>& tree);
    void operator=(const TreeType<ItemType>& tree);
    void MakeEmpty();
    bool IsEmpty() const;
    bool IsFull() const;
    int LengthIs() const;
    void RetrieveItem(ItemType& item, bool& found);
    void ResetTree(OrderType order);
    void GetNextItem(ItemType& item, OrderType order, bool& finished);
    void PrintTree(OrderType order);

    // 변수
    TreeNode<ItemType>* root;
    queue<ItemType> preQue;
    queue<ItemType> inQue;
    queue<ItemType> postQue;
};

// 삽입함수
template <class ItemType>
void Insert(TreeNode<ItemType>*& tree, ItemType item);

// 삭제함수
template <class ItemType>
void Delete(TreeNode<ItemType>*& tree, ItemType item);

 

노드의 구조체를 먼저 살펴보면 트리의 기본적인 구조는 아래와 같다. 각 노드는 값(info)과 좌,우 자식을 가리키는 포인터를 가지고 있다. 포인터가 NULL을 가리키면 '말단'을 의미한다.

구조체 세부구조

구현할 기능이 좀 많다. 하나씩 차근차근 해보자.. 

 

 

1) 생성자

 

# 기본 생성자
template <class ItemType>
TreeType<ItemType>::TreeType(){
    root = NULL;
}

# 복사 생성자
template <class ItemType>
TreeType<ItemType>::TreeType(const TreeType<ItemType>& originalTree){
    CopyTree(root, originalTree.root);
}
  • 빈 트리를 생성할 때 기본 생성자가 적용된다. 빈 트리는 아무 값도 가지고 있지 않으므로 루트에 NULL을 넣어주기만 하면 된다.
  • 복사 생성자는 트리를 복사할 때 적용된다. 복사는 CopyTree 라는 외부 함수로 이루어진다. CopyTree 함수는 아래와 같다. 
  • 복사 함수에서 copy가 &로 전달되기 때문에 노드는 자동으로 연결됨에 유의하자.
# 복사 함수
template <class ItemType>
void CopyTree(TreeNode<ItemType>*& copy, const TreeNode<ItemType>* originalTree){
    // originalTree를 copy에 복사하는 과정
    
    if(originalTree == NULL)
        copy = NULL;
    else{
        copy = new TreeNode<ItemType>; // 새로운 노드 추가
        copy->info = originalTree->info; // 값 복사
        CopyTree(copy->left, originalTree->left); // 오리지널의 왼쪽 노드 복사
        CopyTree(copy->right, originalTree->right); // 오리지널의 오른쪽 노드 복사
    }
}

 

 

 

2) 배정 연산자(=)

 

template <class ItemType>
void TreeType<ItemType>::operator=(const TreeType<ItemType>& originalTree){

    // 자기 자신을 복사하는 경우 무시해준다
    if (&originalTree == this)
         return;     
    
    Destroy(root); // 원래 나의 정보를 다 삭제 
    CopyTree(root, originalTree.root); // 복사
}

 

  • 자기 자신을 복사하는 경우 무시
  • A = B 에서 B가 originalTree에 해당한다. 

 

3) 소멸자

 

# 소멸 함수
template <class ItemType>
void Destroy(TreeNode<ItemType>*& tree){
    if(tree != NULL){
        Destroy(tree->left);
        Destroy(tree->right);
        delete tree;
    }
}

# 소멸자
template <class ItemType>
TreeType<ItemType>::~TreeType(){
    Destroy(root);
}
  • 소멸 함수는 재귀적으로 실행되는데, 가장 말단 노드부터 할당해제 되어야 하므로 후위 순회와 동일한 순서로 진행된다. 
  • 소멸 함수에서 트리를 &로 받으므로 노드는 알아서 삭제된다. 
  • 소멸 함수에 소멸하고자 하는 트리의 루트만 넣어주면 소멸자가 된다. 

 

4) MakeEmpty

 

template <class ItemType>
void TreeType<ItemType>::MakeEmpty(){
     Destroy(root);
     root = NULL;
}
  • Destroy를 하고 나면 트리의 모든 노드가 할당 해제된다. 
  • 빈 트리임을 명시하기 위해 모든 노드 삭제 후 'root = NULL' 를 적어줘야 한다. 이를 생략하면 프로그램 종료시 소멸자에서 root가 아무것도 가리키지 않기 때문에 에러가 발생한다. 

 

5) IsEmpty

 

template <class ItemType>
bool TreeType<ItemType>::IsEmpty() const{
    return root == NULL;
}

 

 

6) IsFull

 

template <class ItemType>
bool TreeType<ItemType>::IsFull() const{
    TreeNode<ItemType>* location;
    try{
        location = new TreeNode<ItemType>;
        delete location;
        return false;
    }
    catch(std::bad_alloc exception){
        return true;
    }
}
  • 새로운 노드를 한 번 생성해보고, 메모리에 여유가 없으면 트리가 가득찬 것으로 간주한다. 
  • 메모리에 여유가 있으면 노드를 추가할 수 있다는 뜻이므로 거짓을 반환하고 임시로 생성한 노드는 다시 할당 해제해준다.

 

7) LengthIs

 

# 노드 세는 외부 함수
template <class ItemType>
int CountNodes(TreeNode<ItemType>* tree){
    if(tree == NULL)
        return 0;
    else
        return CountNodes(tree->left) + CountNodes(tree->right) + 1;
}

# 길이 반환 멤버 함수
template <class ItemType>
int TreeType<ItemType>::LengthIs() const{
    return CountNodes(root);
}
  • 왼쪽 노드 + 오른쪽 노드 + 1(현재 노드) 를 재귀적으로 실행해주면 된다. 

 

8) RetrieveItem

 

# 값 찾기 외부 함수
template <class ItemType>
void Retrieve(TreeNode<ItemType>* tree, ItemType& item, bool& found){
    if(tree == NULL)
        found = false;
    else if(item < tree->info)
        Retrieve(tree->left, item, found);
    else if(item > tree->info)
        Retrieve(tree->right, item, found);
    else{
        found = true;
    }
}

# 값 찾기 멤버 함수
template <class ItemType>
void TreeType<ItemType>::RetrieveItem(ItemType& item, bool& found){
    Retrieve(root, item, found);
}
  • item이 트리에 있는지 확인하는 함수로 외부 함수를 사용한다. 트리가 비었거나 값이 존재하지 않으면 found는 false, 값이 존재하면 found는 true가 된다. 
  • 재귀적으로 실행되며 두 개의 else if 의 위치가 바껴도 상관없다. 값을 찾을때까지 재귀적으로 모든 노드를 탐색한다. 

 

9) ResetTree

 

template <class ItemType>
void TreeType<ItemType>::ResetTree(OrderType order){
    switch(order){
        case PRE_ORDER:
            PreOrder(root, preQue);
            break;
        case IN_ORDER:
            InOrder(root, inQue);
            break;
        case POST_ORDER:
            PostOrder(root, postQue);
            break;
    }
}
  • 순회 타입(order)에 따라 큐에 알맞은 데이터 삽입
  • PRE_ORDER, IN_ORDER, POST_ORDER 는 각각 전위, 중위, 후위 순회를 말하며 함수는 아래와 같다. 
# 후위 순회
template <class ItemType>
void PostOrder(TreeNode<ItemType>* tree, queue<ItemType>& postQue){
    if(tree != NULL){
        if(tree != NULL){
            PostOrder(tree->left, postQue);
            PostOrder(tree->right, postQue);
            postQue.push(tree->info);
        }
    }
}

# 중위 순회
template <class ItemType>
void InOrder(TreeNode<ItemType>* tree, queue<ItemType>& inQue){
    if(tree != NULL){
        if(tree != NULL){
            InOrder(tree->left, inQue);
            inQue.push(tree->info);
            InOrder(tree->right, inQue);
            
        }
    }
}

# 전위 순회
template <class ItemType>
void PreOrder(TreeNode<ItemType>* tree, queue<ItemType>& preQue){
    if(tree != NULL){
        if(tree != NULL){
            preQue.push(tree->info);
            PreOrder(tree->left, preQue);
            PreOrder(tree->right, preQue);
        }
    }
}

 

 

 

10) GetNextItem

 

template <class ItemType>
void TreeType<ItemType>::GetNextItem(ItemType& item, OrderType order, bool& finished){
    finished = false;
    switch(order){
        case PRE_ORDER:
            item = preQue.front();
            preQue.pop();
            if(preQue.empty())
                finished = true;
            break;
        case IN_ORDER:
            item = inQue.front();
            inQue.pop();
            if(inQue.empty())
                finished = true;
            break;
        case POST_ORDER:
            item = postQue.front();
            postQue.pop();
            if(postQue.empty())
                finished = true;
            break;
    }
}
  • 순회 타입(order)에 따라 다음 순서의 노드값을 item에 저장한다. 
  • ResetTree 함수로 먼저 큐에 값을 넣은 뒤에 사용 가능하다.

 

11) PrintTree

 

template <class ItemType>
void TreeType<ItemType>::PrintTree(OrderType order){
    switch(order){
        case PRE_ORDER:
            while(!preQue.empty()){
                cout << preQue.front();
                preQue.pop();
            }
            break;
        case IN_ORDER:
            while(!inQue.empty()){
                cout << inQue.front();
                inQue.pop();
            }
            break;
        case POST_ORDER:
            while(!postQue.empty()){
                cout << postQue.front();
                postQue.pop();
            }
            break;
    }
}
  • 순회 타입(order)에 맞게 트리의 모든 값을 출력한다.
  • ResetTree 함수로 먼저 큐에 값을 넣은 뒤에 사용 가능하다.

 

12) Insert

template <class ItemType>
void Insert(TreeNode<ItemType>*& tree, ItemType item){
    if(tree == NULL){
        tree = new TreeNode<ItemType>;
        tree->right = NULL;
        tree->left = NULL;
        tree->info = item;
    }
    else if(item < tree->info)
        Insert(tree->left, item);
    else
        Insert(tree->right, item);
}
  • 삽입되는 위치를 재귀적으로 찾고, 해당 위치에 노드를 추가해주면 된다.
  • 트리를 &로 받으므로 노드는 알아서 추가된다. 
  • 아래는 트리에 11을 삽입하는 과정을 나타낸 그림이다.

11 삽입 과정

 

13) Delete

 

삭제 함수가 좀 복잡하다. 데이터 삽입은 항상 말단 노드에서 이뤄지기 때문에 간단하지만 삭제는 그렇지 않다. 노드 삭제의 경우 아래와 같이 세 가지 케이스로 분류된다.

 

 

  [1] 리프 노드를 삭제하는 경우

말단 노드를 삭제하는 경우 문제될 것은 딱히 없다. 그냥 삭제해주기만 하면 된다. 

 

 

  [2] 하나의 자식만 가지는 노드를 삭제하는 경우 

이 케이스 역시 문제될 것은 없다. 그냥 위 그림과 같이 삭제하는 노드의 자식 노드를 부모의 자식으로 만들어주면 된다.

 

 

  [3] 두 개의 자식을 가지는 노드를 삭제하는 경우

위 그림에서 Q를 삭제한다고 했을 때 Q 자리에 어떤 값이 들어가야 할까? Q의 왼쪽 서브트리는 모두 Q보다 작은 값이고, Q의 오른쪽 서브트리는 모두 Q보다 큰 값이다. Q가 삭제되어도 대체되는 값이 동일한 규칙을 만족해야 한다. 이를 만족시키는 대체값은 Q보다 작은 최대값 또는 Q보다 큰 최소값이 될 것이다. 따라서 Q를 대체할 수 있는 값은 왼쪽 서브트리의 최대값 또는 오른쪽 서브트리의 최소값이다. 위 그림에서는 Q를 왼쪽 서브트리의 최대값으로 대체했다. 구현 코드 또한 대체값을 왼쪽 서브트리에서 찾도록 짤 것이다. 아래 더보기란을 클릭하면 트리 전체를 삭제하는 예시가 나오니 참고하길 바란다. 

 

위 세 가지 삭제 케이스를 그대로 구현하면 아래와 같다. 

 

template <class ItemType>
void DeleteNode(TreeNode<ItemType>*& tree){
    ItemType data;
    TreeNode<ItemType>* tmpPtr;
    tmpPtr = tree;
    
    // 1. 자식이 0 or 1개인 노드 삭제
    if(tree->left == NULL){ 
    	// 1) 왼쪽이 비었으면 오른쪽 자식과 연결
        tree = tree->right;
        delete tmpPtr;
    }
    else if(tree->right == NULL){ 
    	// 2) 오른쪽이 비었으면 왼쪽 자식과 연결
        tree = tree->left;
        delete tmpPtr;
    }
    
    // 2. 자식이 두 개인 노드 삭제
    else{
        GetPredecessor(tree->left, data); // 왼쪽 서브트리 최대값을 data에 저장
        tree->info = data;
        Delete(tree->left, data);
    }
}

 

여기서 GetPredecessor 라는 함수가 등장하는데, 이 함수는 왼쪽 서브트리의 최대값을 구해주는 함수다. 왼쪽 서브트리의 최대값은 왼쪽 자식을 시작점으로 해서 가장 오른쪽 말단에 위치한 노드다. 이를 재귀적으로 구현한 함수에 불과하다. 코드는 아래와 같다. 

 

template <class ItemType>
void GetPredecessor(TreeNode<ItemType>* tree, ItemType& data){
    while(tree->right != NULL)
        tree = tree->right;
    data = tree->info;
}

 

이 함수는 tree의 가장 오른쪽에 위치한 값을 data에 저장해준다. DeleteNode 함수에서 tree에 tree->left 를 넣어줌으로써 tree의 왼쪽 서브트리의 최대값을 구하는 함수로 사용할 수 있다. 

 

이제 진짜 삭제 함수를 구현해보자. 우리가 최종적으로 구현하고자 하는 것은 특정값을 가지는 노드를 삭제하는 함수다. 위에서 다룬 함수는 단순히 '노드'만을 삭제하는 함수였다. 삭제 함수의 알고리즘은 아래와 같다. 

 

1. 삭제값과 일치하는 노드 찾기
2. 해당 노드 삭제

 

1번은 Insert 함수와 비슷하다. 단순히 트리의 왼쪽, 오른쪽을 재귀적으로 탐색하면 된다. 1번으로 삭제하고자 하는 노드를 찾았으면, DeleteNode로 해당 노드를 삭제해주기만 하면 된다. 코드는 아래와 같다. 

 

template <class ItemType>
void Delete(TreeNode<ItemType>*& tree, ItemType item){
    if(item < tree->info)
        Delete(tree->left, item);
    else if(item > tree->info)
        Delete(tree->right, item);
    else
        DeleteNode(tree);
}

 

 

 

이진 탐색 트리는 포인터와 재귀함수가 많아서 이해하는데 시간이 좀 걸린다. 그래도 확실하게 이해하고 나면 포인터와 재귀함수에 대한 이해도가 높아지니 포기하지 말자!

 

 

반응형
저작자표시 비영리 변경금지

'CS > 자료구조' 카테고리의 다른 글

[ 자료구조 ] 이진 트리와 순회  (0) 2022.03.25
[ 자료구조 ] 트리 용어 정리  (0) 2022.03.23
[ 자료구조 ] 큐(Queue)  (0) 2022.03.17
[ 자료구조 ] 스택(Stack)  (0) 2022.03.09
[ 자료구조 ] 연결 리스트 : 원형 연결 리스트  (0) 2022.03.07

'CS/자료구조' Related Articles

티스토리툴바