가장 빠른 검색, 이진탐색트리(BST) 구현 및 이해

개요

안녕하세요.

C++ 자료구조 (Data Structure) 중 검색에 특화된 BST (Binary Search Tree)를 구현한 예제입니다.

• Root 기준으로 작은 값은 왼쪽, 큰값은 오른쪽, 중복허용X
  

• 연결리스트 (Linked List) 로 구성

• 삽입, 순회, 검색, 삭제 가능

• 노드 삭제 시 자식노드의 수 (0, 1, 2) 에 따라 삭제법이 다름에 유의
  

 

Visualization

Link : https://www.cs.usfca.edu/~galles/visualization/Algorithms.html

 

개발 환경

• C++17, Qt Creator 9.0.1, MinGW 11.2.0 64bit
  

• Windows 11 Pro

 

bst.h

#ifndef BST_H
#define BST_H

struct Node
{
    Node(int _v=0, Node *_L=nullptr, Node *_R=nullptr) :
        v(_v), L(_L), R(_R) {}
    int v;
    Node *L, *R;
};

class BST
{
public:
    BST();
    ~BST();

private:
    Node *pRoot;

public:
    inline Node* root() {return pRoot;}
    void insert(int v);
    void preorder(Node *);
    void inorder(Node *p);
    void postorder(Node *p);
    Node* search(Node *p, int v);
    void remove(int v);

private:
    Node* insert(Node *p, int v);
    void deleteNode(Node *p);    
    Node* remove(Node *p, int v);
};

#endif // BST_H

bst.cpp

#include "bst.h"
#include <iostream>
using namespace std;

BST::BST() : pRoot(nullptr)
{
    cout << "Contructor" << '\n';
}

BST::~BST()
{
    cout << "Destructor" << '\n';
    deleteNode(pRoot);
}

void BST::deleteNode(Node* p)
{
    if(p)
    {
        deleteNode(p->L);
        deleteNode(p->R);
        //cout << "Delete node value : " << p->v << '\n';
        delete p;
        p = nullptr;
    }
}

void BST::insert(int v)
{
    if (!pRoot)
    {
        pRoot = new Node(v, nullptr, nullptr);
    }
    else
    {
        insert(pRoot, v);
    }
}

Node* BST::insert(Node *p, int v)
{
    if (p==nullptr)
    {
        return new Node(v,nullptr, nullptr);
    }

    if (p->v > v)
    {
        p->L = insert(p->L, v);
    }
    else if (p->v < v)
    {
        p->R = insert(p->R, v);
    }
    else
    {
        cout << "Found same value." << '\n';
    }

    return p;
}

void BST::preorder(Node *p)
{
    if (!p)
        return;

    cout << p->v << ", ";
    preorder(p->L);
    preorder(p->R);
}

void BST::inorder(Node *p)
{
    if (!p)
        return;

    inorder(p->L);
    cout << p->v << ", ";
    inorder(p->R);
}

void BST::postorder(Node *p)
{
    if (!p)
        return;

    postorder(p->L);
    postorder(p->R);
    cout << p->v << ", ";
}

Node* BST::search(Node *p, int v)
{
    if (!p)
        return p;

    if (p->v == v)
        return p;
    else if(p->v > v)
        return search(p->L, v);
    else
        return search(p->R, v);
}

void BST::remove(int v)
{
    remove(root(), v);
}

Node* BST::remove(Node *p, int v)
{
    if(!p)
        return p;

    if (p->v > v)
        p->L = remove(p->L, v);
    else if (p->v < v)
        p->R = remove(p->R, v);
    else
    {        
       if(p->L==nullptr &&  p->R==nullptr)
       {
           delete p;
           p = nullptr;
       }
       else if(p->L==nullptr)
       {
           auto temp = p;
           p = p->R;
           delete temp;
       }
       else if(p->R==nullptr)
       {
           Node* temp = p;
           p = p->L;
           delete temp;
       }
       else
       {
           //왼쪽트리에서 제일 큰값
           auto temp = p->L;
           while (temp->R != nullptr)
               temp = temp->R;

           p->v = temp->v;
           p->L = remove(p->L, temp->v);
           //우트리에서 제일 작은값
//           auto temp = p->R;
//           while (temp->L != nullptr)
//               temp = temp->L;

//           p->v = temp->v;
//           p->R = remove(p->R, temp->v);

       }
    }
    return p;
}

main.cpp

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

using namespace std;

int main()
{
    BST bt;

    bt.insert(10);
    bt.insert(5);
    bt.insert(3);
    bt.insert(7);

    bt.insert(15);
    bt.insert(18);
    bt.insert(12);

    cout << "Preorder:";
    bt.preorder(bt.root());
    cout << '\n';

    cout << "Inorder:";
    bt.inorder(bt.root());
    cout << '\n';

    cout << "Postorder:";
    bt.postorder(bt.root());
    cout << '\n';

    return 0;
}

output

 

감사합니다.