Binary Search Tree 자료구조 (C++)

" class Node "

- Tree에 들어갈 데이터를 Node로 저장한다.

 

1. 변수

- int data  :  데이터 저장한다.

- Node* parent  :  부모Node를 가르키는 포인터를 저장한다.

- Node* leftChild  :  왼쪽 자식을 가르키는 포인터를 저장한다.

- Node* rightChild  :  오른쪽 자식을 가르키는 포인터를 저장한다.

 

2. 함수

- 각 변수에 대해 get, set 함수가 필요하다

 

3. class Node ADT

class Node {
private:
    int data;
    Node* parent;
    Node* leftChild;
    Node* rightChild;
public:
    Node() {//생략 }
    Node(int data) {//생략 }
    Node* getParent() {//생략 }
    Node* getLeftChild() {//생략 }
    Node* getRightChild() {//생략 }
    int getData() {//생략 }
    void setParent(Node* node) {//생략 }
    void setLeftChild(Node* node) {//생략 }
    void setRightChild(Node* node) {//생략 }
    void setData(int data) {//생략 }
};

 

" class BinarySearchTree "

- 각 Node를 연결 시켜주는 class이다.

 

1. 변수

- Node* root  :  최상단 root Node를 저장한다.

 

2. 함수

- Node* find(int e)  :  데이터 e를 지닌 Node를 찾아 반환한다.

- void insert(int e)  :  데이터 e를 지닌 Node를 생성하여 알맞은 위치에 추가한다.

- Node* find_min(Node* node)  :  node를 포함한 서브트리 내에서 가장 값이 적은 Node를 찾아 반환한다.

- void erase(int e)  :  데이터 e를 지닌 Node를 찾아 자식의 수 상황에 따라 알맞게 삭제한다.

 

3. class BinarySearchTree ADT

class BinarySearchTree {
private:
    Node* root;
public:
    BinarySearchTree() {//생략 }
    Node* find(int e) {//생략 }
    void insert(int e) {//생략 }
    Node* find_min(Node* node) {//생략 }
    void erase(int e) {//생략 }
};

 

4. 예시코드

- 참조 코드 : github.com/FreeDeveloper97/Data-Structure-based-cpp/blob/main/7.%20Binary%20Search%20Tree/Code_cpp/W11_P1_Binary_Search_Tree.cpp

- 참조 문제 : github.com/FreeDeveloper97/Data-Structure-based-cpp/blob/main/7.%20Binary%20Search%20Tree/Exercize_pdf/prob-W11_P1.pdf

//
//  W11_4_BinearySearchTree.cpp
//  INHA CLASS
//
//  Created by Kang Minsang on 2020/12/15.
//  Copyright © 2020 Kang Minsang. All rights reserved.
//

#include <iostream>
using namespace std;

class Node {
private:
    int data;
    Node* parent;
    Node* leftChild;
    Node* rightChild;
public:
    Node() {
        this->data = 0;
        this->parent = NULL;
        this->leftChild = NULL;
        this->rightChild = NULL;
    }
    Node(int data) {
        this->data = data;
        this->parent = NULL;
        this->leftChild = NULL;
        this->rightChild = NULL;
    }
    Node* getParent() {
        return parent;
    }
    Node* getLeftChild() {
        return leftChild;
    }
    Node* getRightChild() {
        return rightChild;
    }
    int getData() {
        return data;
    }
    void setParent(Node* node) {
        parent = node;
    }
    void setLeftChild(Node* node) {
        leftChild = node;
    }
    void setRightChild(Node* node) {
        rightChild = node;
    }
    void setData(int data) {
        this->data = data;
    }
};

class BinarySearchTree {
private:
    Node* root;
public:
    BinarySearchTree() {
        this->root = NULL;
    }

    Node* find(int e) {
        Node* result = root;
        while(result != NULL) {
            if(e == result->getData()) {
                return result;
            }
            else if(e < result->getData()) {
                result = result->getLeftChild();
            }
            else {
                result = result->getRightChild();
            }
        }
        return NULL;
    }

    void insert(int e) {
        Node* newNode = new Node(e);
        if(root == NULL) {
            root = newNode;
            return;
        }
        Node* parent = NULL;
        Node* temp = root;
        while(temp != NULL) {
            parent = temp;
            if(e < temp->getData()) {
                temp = temp->getLeftChild();
            }
            else {
                temp = temp->getRightChild();
            }
        }
        newNode->setParent(parent);
        if(e < parent->getData()) {
            parent->setLeftChild(newNode);
        }
        else {
            parent->setRightChild(newNode);
        }
    }

    Node* find_min(Node* node) {
        Node* result = NULL;
        Node* temp = node;
        while(temp != NULL) {
            result = temp;
            temp = temp->getLeftChild();
        }
        return result;
    }

    void erase(int e) {
        Node* delNode = find(e);
        int num = bool(delNode->getLeftChild()) + bool(delNode->getRightChild());
        if(num == 0) {
            if(delNode == root) {
                root = NULL;
            }
            else {
                Node* parent = delNode->getParent();
                if(e < parent->getData()) {
                    parent->setLeftChild(NULL);
                }
                else {
                    parent->setRightChild(NULL);
                }
            }
            delete delNode;
        }
        else if(num == 1) {
            if(delNode == root) {
                if(delNode->getLeftChild() != NULL) {
                    root = delNode->getLeftChild();
                }
                else {
                    root = delNode->getRightChild();
                }
                delete delNode;
            }
            else {
                Node* parent = delNode->getParent();
                Node* child = delNode->getLeftChild() != NULL ? delNode->getLeftChild() : delNode->getRightChild();
                if(child->getData() < parent->getData()) {
                    parent->setLeftChild(child);
                    child->setParent(parent);
                }
                else {
                    parent->setRightChild(child);
                    child->setParent(parent);
                }
                delete delNode;
            }
        }
        else if(num == 2) {
            Node* min = find_min(delNode->getRightChild());
            int data = min->getData();
            erase(data);
            delNode->setData(data);
        }
    }

    void startPost() {
        if(root == NULL) {
            cout<<"Empty\n";
        }
        else {
            postOrderPrint(root);
            cout<<"\n";
        }
    }

    void postOrderPrint(Node* node) {
        if(node == NULL) {
            return;
        }
        postOrderPrint(node->getLeftChild());
        postOrderPrint(node->getRightChild());
        cout<<node->getData()<<" ";
    }
};

int main()
{
    int T;
    cin>>T;
    while(T--) {
        BinarySearchTree tree = BinarySearchTree();
        int P;
        cin>>P;
        int N;
        while(P--) {
            cin>>N;
            tree.insert(N);
        }
        int Q;
        cin>>Q;
        while(Q--) {
            cin>>N;
            tree.erase(N);
        }
        tree.startPost();
    }
}

 

5. 기타

- erase함수 : 자식수가 0개인 경우

  -> root인 경우 root 포인터 값을 NULL로 수정 후 제거한다.

  -> 그 외의 경우 parent의 left 또는 right child를 NULL로 수정 후 제거한다.

 

- erase함수 : 자식수가 1개인 경우

-> root인 경우 left 또는 right child를 root로 저장 후 제거한다.

-> 그 외의 경우 parent와 left 또는 right child를 구한 후 parent와 child를 연결 해준 후 제거한다.

 

- erase함수 : 자식수가 2개인 경우

-> find_min(right child)를 실행하여 오른쪽노드의 최소값을 임시저장한 다음

-> 먼저 최소값 노드를 erase 한 다음 삭제노드의 data를 임시저장한 값으로 수정한다