[DS] 이진탐색트리(Binary Search Tree)란?

이진탐색트리(Binary Search Tree)란?

Left subtree에 속한 모든 node의 값(key)은 root의 값(key)보다 작고,

Right subtree에 속한 모든 node의 값(key)보다 큰 이진 트리(binary tree)입니다.

+ Empty tree도 이진탐색트리입니다.

+ 모든 subtree도 이진탐색트리입니다.

+ 모든 노드(node)의 값(key)이 겹치면 안 됩니다.

 

 

 

Binary Search Tree를 구현하기 위한 ADT 구현

---

class bst_node {
public:
    string id;
    string name;
    double score;
    bst_node *left, *right;
    bst_node();
    bst_node(string s1, string s2, double n);
    void set_data(string s1, string s2, double n);
};

데이터와 포인터를 포함한 node 클래스를 정의해줍니다.

 

이번에는 오버로딩(overloding)된 생성자(constructor)도 만들어줬습니다.

class bst_tree {
    bst_node *root;
    int csize;
public:
    bst_tree();
    int bst_size();
    void insert_node(bst_node t);
    void show_inorder();
    bool empty();
    bst_node search(string tid);
};

bst_tree - 이진탐색트리(binary search tree)를 생성한 초기 상태

bst_size - tree node의 개수를 return

insert_node - tree에 node를 추가

show_inorder - inorder 상태로 tree의 node를 출력

empty - 현재 tree가 empty인지에 대한 상태 확인

search - 원하는 node를 찾아서 return

 

 

 

함수 구현

---

bst_node::bst_node() {
    left = NULL;
    right = NULL;
}

bst_node의 첫 번째 생성자(constructor)에서는 left, right을 NULL로 초기화시킵니다.

 

 

bst_node::bst_node(string s1, string s2, double n) {
    id = s1;
    name = s2;
    score = n;
    left = NULL;
    right = NULL;
}

bst_node의 두 번째 생성자(constructor)에서는 left, right을 NULL로 초기화 시킬 뿐 아니라,

id, name과 score에도 값을 부여합니다.

 

 

 

void bst_node::set_data(string s1, string s2, double n) {
    id = s1; 
    name = s2;
    score = n;
}

bst_node의 data를 셋팅(setting)해주는 메소드(method)입니다.

 

 

bst_tree::bst_tree() {
    root = NULL;
    csize = 0;
}

이진탐색트리(binary search tree)의 생성자(constructor)에서는 root를 NULL로 csize를 0으로 초기화시킵니다.

 

 

int bst_tree::bst_size() {
    return csize;
}

bst_size는 현재 tree node의 개수를 return 해주는 함수입니다.

 

 

bool bst_tree::empty() {
    if(root == NULL) return true;
    else return false;
}

empty는 이진탐색트리(binary search tree)의 tree가 empty 상태인지 확인하는 함수입니다.

root에 node가 존재하지 않으면 true를 return 해줍니다.

 

 

void bst_tree::insert_node(bst_node t){
    bst_node* p;           
    bst_node* tmp;         

    tmp = new bst_node;
    *tmp = t;                
    tmp->left = NULL;     
    tmp->right = NULL;    

    if(root == NULL){
        root = tmp;
        return;
    }

    p = root;
    while(1){
        if(p->id == t.id){          
            cout << "Insertion Failed : the Key " << t.id << "already exists."<<endl;
            return ;
        }
        if(p->id < t.id){             
            if(p->right == NULL){
                p->right = tmp;
                return;
            }
            else 
                p = p->right;
        }
        else{                        
            if(p->left == NULL){
                p->left = tmp;
                return;
            }
            else 
                p =  p->left;
        }
    }
}

insert_node는 tree에 node를 추가하는 함수입니다.

 

if(root == NULL)부터 설명을 드리겠습니다.

 

if(root == NULL) root = tmp; return;

root에 원소가 없으면 새로 들어온 원소를 넣어주고 함수를 종료합니다.

 

p == root;

원소를 넣을 자리를 찾기 위해 p 변수에 root를 넣어줍니다.

 

while(1)

새로운 원소를 찾을 때까지 while문을 돌려줍니다.

 

if(p->id == t.id) { cout<<"??";   return;}

새로 넣을 값이 이미 존재할 때 "already exists."라는 문구와 함께 함수를 종료시킵니다.

 

if(p->id < t.id)

현재 node의 값보다 새로운 node의 값이 클 때

 

if(p->right == NULL) { p->right = tmp;  return;}

현재 node의 right child가 없다면 새로운 원소를 추가해주고 함수를 종료시킵니다.

 

else {p = p->right}

현재 node의 right child가 있다면 현재 node의 right child로 이동합니다.

 

else{

현재 node의 값보다 새로운 node의 값이 작을 때

 

if(p->left == NULL) {p->left = tmp;  return;}

현재 node의 left child가 없다면 새로운 원소를 추가해주고 함수를 종료시킵니다.

 

else {p = p->left;}

현재 node의 left child가 있다면 현재 node의 left child로 이동합니다.

 

 

 

void bst_tree::show_inorder() {
    inorder_print(root);
}

show_inorder은 bst_tree의 private root 데이터를 파라미터로 보내주는 함수입니다.

 

 

void inorder_print(bst_node *p) {
    if(p == NULL) return;

    inorder_print(p->left);
    cout << p->id << " : " << p->name << " : " << p->score << endl;
    inorder_print(p->right);
}

inorder_print는 recursion 함수로 tree의 node를 inorder 순서로 출력해주는 함수입니다.

 

left node를 방문해서 원소의 값을 출력하고 right node를 방문해서 값을 출력합니다.

 

 

bst_node bst_tree::search(string tid) {
    bst_node *p;
    p = root;

    bst_node tmp;
    tmp.set_data("00000000", "None", -1);

    if(root == NULL) {
        cout << "The key " << tid << "does not exist.\n";
        return tmp;
    }
    while(1) {
        if(p->id == tid) 
            return (*p);
        if(p->id < tid) {
            if(p->right == NULL) {
                cout << "The key " << tid << " does not exist.\n";
                return tmp;
            } 
            else p = p->right;
        }
        else if(p->id > tid) {
            if(p->left == NULL) {
                cout << "The key " << tid << " does not exist.\n";
                return tmp;
            }
            else p = p->left;
        }
    }
}

search는 원하는 원소를 return 해주는 함수입니다.

 

 

bst_node tmp;

tmp.set_data("00000000", "None", -1);

원소하는 원소가 없을 때 return 해줄 값을 미리 셋팅합니다.

 

if(root == NULL) {cout << "??";  return tmp;}

root에 값이 없다면 "does not exist."메세지와 함께 앞서 미리 세팅해놓은 값을 return 합니다.

 

while(1)

원하는 원소를 찾을 때까지 while문을 돌려줍니다.

 

if(p->id == tid) return (*p);

현재 node가 원하는 원소라면 현재 node의 값을 return 합니다.

 

if(p->id < tid){

원하는 원소가 현재 node의 값보다 크면서

 

if(p->right == NULL) {cout << "??"; return tmp;}

현재 node의 right child가 없다면 "does not exist."메세지와 함께 앞서 미리 세팅해놓은 값을 return 합니다.

 

else p = p->right;

현재 node의 child node가 존재하면 child node로 이동합니다.

 

else if(p->id > tid){

원하는 원소가 현재 node의 값보다 작으면서

 

if(p->left == NULL) {cout << "??"; return tmp;}

현재 node의 left child가 없다면 "does not exist."메세지와 함께 앞서 미리 세팅해놓은 값을 return 합니다.

 

else p = p->left;

현재 node의 left node가 존재하면 left node로 이동합니다.

 

 

main 함수 구현

---

int main() {
    bst_node tmp;
    bst_tree bst;

    tmp.set_data("00000006", "F", 6);
    bst.insert_node(tmp);
    tmp.set_data("00000004", "D", 4);
    bst.insert_node(tmp);
    tmp.set_data("00000008", "H", 8);
    bst.insert_node(tmp);
    tmp.set_data("00000002", "B", 2);
    bst.insert_node(tmp);
    tmp.set_data("00000005", "E", 5);
    bst.insert_node(tmp);
    tmp.set_data("00000007", "G", 7);
    bst.insert_node(tmp);
    tmp.set_data("00000009", "I", 9);
    bst.insert_node(tmp);
    tmp.set_data("00000003", "C", 3);
    bst.insert_node(tmp);
    tmp.set_data("00000010", "G", 10);
    bst.insert_node(tmp);
    

    cout<<"Node list : indorder sequence \n";
    bst.show_inorder();
    cout << "\n\n";

    string key = "00000001";
    tmp = bst.search(key);

    cout << "\n -- " << key << "'s record ---" << endl;
    cout << " Student ID   : "<< tmp.id << endl;
    cout << " Student Name : "<< tmp.name << endl;
    cout << " Score: " << tmp.score << endl;

    key = "00000010";
    tmp = bst.search(key);

    cout << "\n -- " << key << "'s record ---" << endl;
    cout << " Student ID   : "<< tmp.id << endl;
    cout << " Student Name : "<< tmp.name << endl;
    cout << " Score: " << tmp.score << endl;
}

원소가 다 들어갔을 때 tree의 모습은 아래와 같고

inder 순서로 node의 값(key)를 출력했을 때 

2 - 3 - 4 - 5 - 6 - 7 - 8 - 9 - 10

순서로 출력이 잘 됩니다.

 

 

"00000001"인 id를 찾으면 없는 원소라는 문구가 (search)함수 안에서 출력되고,

 (search)함수에서 빠져나오면 return 된 값과 함께 다음 코드가 실행됩니다.

 

 

"00000010"인 id는 존재하는 원소이기 때문에 원소의 값이 잘 출력되는 것을 확인할 수 있습니다.

 

 

 

◡̈