가장 빠른 검색, 이진탐색트리(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

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#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

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
#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

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#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

 

감사합니다.

댓글

댓글 쓰기

이 블로그의 인기 게시물

Qt Designer 설치하기

-
이미지
개요 오늘은 Qt Designer 설치방법에 대해 설명하고자 합니다. Qt Designer는 Qt앱 생성시 GUI ( G raphic U ser I nterface) 를 쉽게 구성하고 배치하는 것을 도와주는 도구 입니다. [Qt Designer 실행화면] C++언어로 Qt를 사용하는 경우는 Qt Creator 설치시 같이 설치되어 바로 사용이 가능하지만 파이썬의 경우 별도 패키지를 설치 후 사용가능합니다. 그럼 파이썬에서 Qt Designer를 설치하는 방법을 살펴보겠습니다.
Read more »

PyQt5 기반 동영상 플레이어앱 만들기

-
이미지
비디오 재생 예전 게시물 중 음악파일 플레이어 를 파이썬으로 만든 예제가 있습니다. Qt 의 QMediaPlayer , QMediaPlaylist class를 이용해 mp3 등 음악 파일을 재생하는 원리입니다. 아래와 같이 사용합니다. from PyQt5.QtWidgets import QApplication from PyQt5.QtMultimedia import QMediaPlaylist, QMediaPlayer, QMediaContent from PyQt5.QtCore import QUrl import sys if __name__ == '__main__': app = QApplication(sys.argv) playlist = QMediaPlaylist() url = QUrl.fromLocalFile('test.mp3') playlist.addMedia(QMediaContent(url)) player = QMediaPlayer() player.setPlaylist(playlist) player.play() sys.exit(app.exec_()) PlayList를 생성해 파일을 추가하고, Player의 play() 함수를 수행하면 음악이 재생됩니다. 이번에는 동영상 플레이어 (Video Player) 를 Python + PyQt5 를 이용해 만들어 보았습니다. 기본 원리는 위와 같지만 비디오을 출력할 위젯 (QVideoWidget)만 설정 하면 동영상이 재생되는 원리입니다. [동영상 재생 프로그램] 주요기능 재생 리스트에 동영상 파일 추가, 삭제 (*.avi. *.mp4, *.mkv, *.mp...
Read more »