7.4 이진 탐색 트리 구현 [디딤돌 자료구조와 알고리즘 with C++]

7.4 이진 탐색 트리 구현

이제 앞에서 설계한 이진 탐색 트리를 구체적으로 구현합시다.

 

먼저 이진 탐색 트리의 추가 기능인 AddBook 메서드를 구현하기로 해요.

bool BinSearchTree::AddBook(int bnum,string title)

{

먼저 주요 키인 도서 번호로 부모 노드를 검색하기로 해요.

    Node *parent = Find(root,bnum);

    if(parent)

    {

검색한 부모의 키가 입력한 도서 번호와 일치하였는지 확인하세요.

        Book *sbook = parent->book;

        if(sbook->GetBNum() == bnum)

        {

일치하면 도서를 보관하지 않고 추가 실패를 반환하세요.

            return false;

        }

    }

입력받은 인자로 도서 개체를 생성하세요.

    Book *book = new Book(bnum,title);

그리고 검색한 부모의 자식으로 도서 개체를 보관한 노드를 매달게 하세요.

    HangNode(parent,new Node(book));

    return true;

}

다음은 이진 탐색 트리의 가장 핵심적인 검색 기능입니다. 이 기능은 내부 메서드로 추가할 때 부모 노드를 검색하고 삭제나 검색 기능에서 입력한 도서 번호와 같은 키 값을 갖는 노드를 찾는 메서드입니다.

Node *BinSearchTree::Find(Node *sr, int bnum)const

{

만약 검색할 서브 트리의 루트가 0인지 확인하세요.

    if(sr==0)

    {

서브 트리의 루트가 0이라는 말은 root가 0이라는 말과 같습니다. 이 메서드에서는 재귀 호출을 사용할 것이며 언제나 서브 트리가 존재할 때만 호출할 것입니다. 따라서 처음 호출할 때 sr이 0일 때만 이 조건에 해당하며 결국 root가 0이라는 말과 같습니다.

        return sr;

    }

입력 받은 도서 번호와 서브 트리의 루트에 보관한 도서의 번호의 차이를 계산합니다.

    int gap = bnum - sr->book->GetBNum();

    if(gap==0)

    {

만야 차이가 없다면 sr을 반환하세요.

        return sr;

    }

    if(gap>0)

    {

차이가 0보다 크면 오른쪽 서브 트리에서 탐색해야 합니다.

        if(sr->right)

        {

만약 오른쪽 서브 트리가 있으면 재귀 호출하여 탐색한 값을 by pass 하세요.

            return Find(sr->right,bnum);

        }

만약 오른쪽 서브 트리가 없으면 탐색을 끝내고 현재 sr을 반환하세요.

        return sr;

    }

gap이 0이거나 0보다 크면 반환했죠. 여기에 도달했다는 것은 gap이 0보다 작다는 것입니다.

    if(sr->left)

    {

왼쪽 서브 트리가 있으면 재귀 호출하여 탐색한 값을 by pass 하세요.

        return Find(sr->left,bnum);

    }

만약 왼쪽 서브 트리가 없으면 탐색을 끝내고 현재 sr을 반환하세요.

    return sr;

}

이제 추가할 노드와 부모 노드의 연결하는 메서드를 구현합시다.

void BinSearchTree::HangNode(Node *parent, Node *now)

{

    if(parent == 0)

    {

만약 부모가 없으며 새로운 노드가 첫 노드이므로 root로 설정하세요.

        root = now;

        return;

    }

먼저 새로운 노드의 parent 링크를 설정하세요.

    now->parent = parent;

그리고 부모 노드의 어느 쪽에 매달 것인지 판단하기 위해 키 값의 차이를 계산하세요.

    int gap = now->book->GetBNum() - parent->book->GetBNum();

차이가 0보다 크면 부모의 오른쪽 자식으로 매달고 그렇지 않으면 왼쪽 자식으로 매다세요.

    if(gap>0)

    {

        parent->right = now;

    }

    else

    {

        parent->left = now;

    }

}

이제 사용하는 곳에서 검색에 사용할 FindBook 메서드를 구현합시다.

bool BinSearchTree::FindBook(int bnum)const

{

먼저 bnum으로 검색합니다.

    Node *now = Find(root,bnum);

    if(now)

    {

now가 존재하면 now에 보관한 도서 개체를 구하세요.

        Book *sbook = now->book;

        if(sbook->GetBNum() == bnum)

        {

만약 도서 개체의 도서 번호와 입력받은 bnum이 같으면 검색 성공입니다. 여기에서는 도서 정보를 출력하게로 했죠.

            sbook->View();

            return true;

        }

    }

여기에 도달했다는 것은 검색 실패를 의미합니다.

    return false;

}

 

도서 삭제 기능을 구현합시다.

bool BinSearchTree::RemoveBook(int bnum)

{

먼저 bnum으로 노드를 검색하세요.

    Node *now = Find(root,bnum);

    if(now)

    {

now가 존재하면 now에 보관한 도서 개체를 구하세요.

        Book *sbook = now->book;

        if(sbook->GetBNum() == bnum)

        {

만약 도서 개체의 도서 번호와 입력받은 bnum이 같으면 삭제할 노드입니다. 트리에서 연결을 끊으세요.

            DeHang(now);

            return true;

        }

    }

여기에 도달했다는 것은 삭제할 노드가 없다는 것입니다.

    return false;

}

 

 

 

이제 연결을 끊는 메서드를 구현합시다.

void BinSearchTree::DeHang(Node *now)

{

먼저 자식이 양쪽에 있으면 자신과 같은 성향을 갖는 노드를 찾습니다.

    if(now->left && now->right)

    {

자신과 같은 성향을 갖는 노드는 왼쪽 서브 트리에서 제일 큰 값을 갖는 노드와 오른쪽 서브 트리에서 제일 작은 값을 갖는 노드입니다. 여기에서는 왼쪽 서브 트리에서 찾기로 해요.

        Node *alter = now->left;

 

왼쪽 서브 트리에서 제일 큰 값을 갖는 노드를 찾아야 하므로 오른쪽 자식이 있으면 이동하면서 처음으로 오른쪽 자식이 없는 노드를 찾으세요.

        while(alter->right)

        {

            alter = alter->right;

        }

 

now에 보관한 도서 개체와 대체할 노드에 보관한 도서 개체를 교환하세요.

        Book *tmpbook = now->book;

        now->book = alter->book;

        alter->book = tmpbook;

 

이제 대체할 노드를 now에 설정하세요. 이와 같이 하면 언제나 now는 자식이 없거나 하나만 있는 노드라는 논리가 성립합니다.

        now = alter;

    }

 

자식이 없거나 하나만 있을 때는 자신의 부모에 자신이 있던 위치에 자식을 매달고 자식의 부모 링크를 자신의 부모로 변경합니다. 이를 위해 먼저 부모를 기억하는 변수를 선어하여 설정하세요.

    Node *pa = now->parent;

    Node *child = 0;

 

자식은 자신의 왼쪽 노드 혹은 오른쪽 노드입니다. 아래의 코드는 왼쪽에 자식이 있다면 논리합 연산 뒤에 대입 구문은 수행하지 않습니다. 만약 오른쪽에 자식이 있거나 아무 자식이 없으면 논리합 연산 뒤에 대입 구문도 수행합니다. 따라서 아래 구문으로 정확하게 자신의 자식 노드를 설정할 수 있습니다.

    (child = now->left)||(child = now->right);

    if(pa)

    {

부모가 있다면 부모에 자신이 있던 위치에 자식을 설정합니다.

        if(pa->left == now)

        {

            pa->left = child;

        }

        else

        {

            pa->right = child;

        }

    }

    else

    {

부모가 없다는 것은 now가 root라는 것입니다. 따라서 now를 삭제하면 자식 노드를 root로 설정하세요.

        root = child;

    }

    if(child)

    {

자식이 있다면 자식의 부모 링크를 pa로 설정하세요.

        child->parent = pa;

    }

삭제할 now의 도서 개체를 소멸하고 now 노드도 소멸하세요.

    delete now->book;

    delete now;

}

전체 출력하는 ListAll 메서드를 구현합시다.

void BinSearchTree::ListAll()const

{

여기에서는 전위 순회, 중위 순회, 후위 순회를 하며 모든 노드를 출력하기로 해요.

    cout<<"=== Pre order ===="<<endl;

    PreOrder(root);   

    cout<<"===  In order ===="<<endl;

    InOrder(root);   

    cout<<"=== Post order ===="<<endl;

    PostOrder(root);

}

다음은 전위 순회입니다.

void BinSearchTree::PreOrder(Node *sr)const

{

    if(sr)

    {

sr이 참일 때만 수행합니다. 따라서 sr이 0일 때가 재귀의 탈출 조건입니다.

먼저 서브 트리의 루트 정보를 출력합니다.

        sr->book->View();

그리고 왼쪽 서브 트리와 오른쪽 서브 트리를 재귀 호출로 순회하세요.

        PreOrder(sr->left);

        PreOrder(sr->right);

    }

}

중위 순회와 후위 순회도 서브 트리의 루트 정보를 언제 출력하는지만 차이가 있을 뿐이죠.

void BinSearchTree::InOrder(Node *sr)const

{

    if(sr)

    {       

        InOrder(sr->left);

        sr->book->View();

        InOrder(sr->right);

    }

}

void BinSearchTree::PostOrder(Node *sr)const

{

    if(sr)

    {       

        PostOrder(sr->left);

        PostOrder(sr->right);

        sr->book->View();

    }

}

소멸자에서는 후위 순회로 모든 노드를 소멸하세요.

BinSearchTree::~BinSearchTree(void)

{

    Clear(root);

}

void BinSearchTree::Clear(Node *sr)

{

    if(sr)

    {

        Clear(sr->left);

        Clear(sr->right);

노드에 보관한 도서 개체를 소멸한 후에 노드를 소멸하세요.

        delete sr->book;

        delete sr;

    }

}

 

 

 

 

 

 

 

 

다음은 이진 탐색 트리를 구현한 내용입니다.

//BinSearchTree.h

#pragma once

#include "Book.h"

 

struct Node

{

    Book *book;

    Node *left;

    Node *right;

    Node *parent;

    Node(Book *book)

    {

        this->book = book;

        left = right = parent = 0;

    }   

};   

 

 

class BinSearchTree

{   

    Node *root;

public:

    BinSearchTree(void);

    ~BinSearchTree(void);

    bool AddBook(int bnum,string title);

    bool FindBook(int bnum)const;

    bool RemoveBook(int bnum);

    void ListAll()const;   

private:

    Node *Find(Node *sr, int bnum)const;

    void HangNode(Node *parent, Node *now);

    void DeHang(Node *now);

    void PreOrder(Node *sr)const;   

    void InOrder(Node *sr)const;   

    void PostOrder(Node *sr)const;

    void Clear(Node *sr);

};

 

 

 

 

 

//BinSearchTree.cpp

#include "BinSearchTree.h"

 

BinSearchTree::BinSearchTree(void)

{

    root = 0;

}

 

bool BinSearchTree::AddBook(int bnum,string title)

{

    Node *parent = Find(root,bnum);

    if(parent)

    {

        Book *sbook = parent->book;

        if(sbook->GetBNum() == bnum)

        {

            return false;

        }

    }

    Book *book = new Book(bnum,title);

    HangNode(parent,new Node(book));

    return true;

}

 

Node *BinSearchTree::Find(Node *sr, int bnum)const

{

    if(sr==0)

    {

        return sr;

    }

    int gap = bnum - sr->book->GetBNum();

    if(gap==0)

    {

        return sr;

    }

    if(gap>0)

    {

        if(sr->right)

        {

            return Find(sr->right,bnum);

        }

        return sr;

    }

    if(sr->left)

    {

        return Find(sr->left,bnum);

    }

    return sr;

}

 

void BinSearchTree::HangNode(Node *parent, Node *now)

{

    if(parent == 0)

    {

        root = now;

        return;

    }

 

    now->parent = parent;

    int gap = now->book->GetBNum() - parent->book->GetBNum();

    if(gap>0)

    {

        parent->right = now;

    }

    else

    {

        parent->left = now;

    }

}

 

bool BinSearchTree::FindBook(int bnum)const

{

    Node *now = Find(root,bnum);

 

    if(now)

    {

        Book *sbook = now->book;

        if(sbook->GetBNum() == bnum)

        {

            sbook->View();

            return true;

        }

    }   

    return false;

}

 

bool BinSearchTree::RemoveBook(int bnum)

{

    Node *now = Find(root,bnum);

    if(now)

    {

        Book *sbook = now->book;

        if(sbook->GetBNum() == bnum)

        {           

            DeHang(now);

            return true;

        }

    }   

    return false;

}

void BinSearchTree::DeHang(Node *now)

{

    if(now->left && now->right)

    {

        Node *alter = now->left;

        while(alter->right)

        {

            alter = alter->right;

        }

        Book *tmpbook = now->book;

        now->book = alter->book;

        alter->book = tmpbook;

        now = alter;

    }

 

    Node *pa = now->parent;

    Node *child = 0;

    (child = now->left)||(child = now->right);

    if(pa)

    {

        if(pa->left == now)

        {

            pa->left = child;

        }

        else

        {

            pa->right = child;

        }

    }

    else

    {

        root = child;

    }

    if(child)

    {

        child->parent = pa;

    }

    delete now->book;

    delete now;

}

 

void BinSearchTree::ListAll()const

{   

    cout<<"=== Pre order ===="<<endl;

    PreOrder(root);   

    cout<<"===  In order ===="<<endl;

    InOrder(root);   

    cout<<"=== Post order ===="<<endl;

    PostOrder(root);

}

 

void BinSearchTree::PreOrder(Node *sr)const

{

    if(sr)

    {

        sr->book->View();

        PreOrder(sr->left);

        PreOrder(sr->right);

    }

}

 

void BinSearchTree::InOrder(Node *sr)const

{

    if(sr)

    {       

        InOrder(sr->left);

        sr->book->View();

        InOrder(sr->right);

    }

}

 

 

void BinSearchTree::PostOrder(Node *sr)const

{

    if(sr)

    {       

        PostOrder(sr->left);

        PostOrder(sr->right);

        sr->book->View();

    }

}

 

BinSearchTree::~BinSearchTree(void)

{

    Clear(root);

}

 

void BinSearchTree::Clear(Node *sr)

{

    if(sr)

    {       

        Clear(sr->left);

        Clear(sr->right);

        delete sr->book;

        delete sr;

    }

}