"분리수깅" C++ 코드 | Red Black Tree | 자료구조실습 기말 과제

https://gist.github.com/gowoonsori/a725e29ef1880f0592fe5760f4908c6b

* 해당 Red Black Tree 코드를 참고하였고, 내가 원하는 문제 정의 방식대로 코드를 수정하여 완성시켰다.

 

 

코드에 대한 결과는 아래의 블로그에 설명과 함께 적어두었다.

 

https://chaesoong2.tistory.com/21

하천을 지키는 습관! "분리수깅" | Red Black Tree | 자료구조실습 기말 과제

 

코드

---

Red Black Tree 클래스를 만들어 사용하였고

Insert, Delete, Inorder의 과정에서 원하는 조건을 추가해주었다.

#include <iostream>
#include <fstream>
#include <string>
#include <iomanip>
using namespace std;

enum Color
{
    RED,
    BLACK
};
struct node
{
    double latitude; // 위도 값
    double longitude; // 경도 값
    bool isTrash[5]; // 순서: Rubbish 유무, Plastics 유무, Cans 유무, Glass 유무, Papers 유무
    bool side; // 왼쪽 길이면 0, 오른쪽 길이면 1
    node* left = nullptr;
    node* right = nullptr;
    node* parent = nullptr;
    Color color = BLACK;
};

typedef node* NodePtr;

class RBTREE
{
private:
    NodePtr root;     //루트 노드
    NodePtr leafNode; //단말 노드
    int expect_time = 0;
    double expect_distance = 0, expect_point = 0; // 예상 거리, 예상 소요 시간, 예상 마이리지

    //key값이 있는지 없는지 검사, 있으면 pointer 값, 없으면 nullptr
    NodePtr IsKey(double _latitude, double _longitude) //key는 위도, 경도 값
    {
        NodePtr t = root;
        NodePtr parent = NULL;

        /*key값을 찾거나 없다면 break*/
        while (t != NULL && (t->latitude != _latitude || t->longitude != _longitude))
        {
            parent = t;
            if (_latitude == parent->latitude) {
                t = (_longitude < parent->longitude) ? parent->left : parent->right;
            }
            else {
                t = (_latitude < parent->latitude) ? parent->left : parent->right;
            }
        }
        return t;
    }

    //================= Insert =================//

    void Insert(double _latitude, double _longitude, bool* _isTrash, bool _side)
    {

        // x : 삽입할 곳 찾기위한 포인터 | y : 삽입할 곳의 부모노드
        NodePtr x = this->root, y = nullptr;
        NodePtr z = new node();
        z->latitude = _latitude;
        z->longitude = _longitude;
        *z->isTrash = _isTrash;
        z->side = _side;
        z->color = RED;
        z->parent = nullptr;
        z->left = leafNode;
        z->right = leafNode;

        /*BST의 일반 삽입 연산*/
        while (x != leafNode)
        {
            y = x;
            if (x->latitude < _latitude) {
                x = x->right;
            }
            else if (x->latitude == _latitude) {
                if (x->longitude == _longitude) { // 위도, 경도가 모두 같을 때는, isTrash 배열의 값만 변경해주고 끝나면 됨
                    for (int i = 0; i < 5; i++) {
                        if (_isTrash[i]) {
                            x->isTrash[i] = 1; // 배열이 bool type이므로 이렇게 유무만 지정해주면 됨
                        }
                    }
                    return;
                }
                x = (x->longitude < _longitude) ? x->right : x->left;
            }
            else {
                x = x->left;
            }
        }

        // y 설정

        z->parent = y;

        if (y == nullptr) 
            root = z;
        else if (z->latitude > y->latitude)
            y->right = z;
        else if (z->latitude == y->latitude) { // 위도 값이 같다면
            (z->longitude > y->longitude) ? y->right = z : y->left = z; // 경도를 따짐
        }
        else
            y->left = z;

        //z가 root노드라면 (== z의 부모노드가 null이라면)
        if (z->parent == nullptr)
        {
            z->color = BLACK;
            return;
        }

        // z의 부모노드가 root노드라면 Fix Up 필요없이 red컬러로 붙여주면 된다.
        if (z->parent->parent == nullptr)
        {
            return;
        }

        // 위 조건에 만족하지 않으면 FixUp 필요
        InsertFixUp(z);

        return;
    }

    void InsertFixUp(NodePtr z) 
    {
        /*root 노드가 아니고 부모 색이 red라면*/
        while (z != root && z->parent->color == RED)
        {
            NodePtr grandparent = z->parent->parent;
            NodePtr uncle = (z->parent == grandparent->left) ? grandparent->right : grandparent->left;
            bool side = (z->parent == grandparent->left) ? true : false; //if p[z]가 p[p[z]]의 왼쪽 자식이면 1 / 오른쪽이면 0

            /*case 1*/
            if (uncle && uncle->color == RED)
            {
                z->parent->color = BLACK;
                uncle->color = BLACK;
                grandparent->color = RED;
                z = grandparent;
            }

            /*case 2
                side == true ) p[z]는 p[p[z]]의 왼쪽 자식 인 경우이다.
                side == false ) p[z]는 p[p[z]]의 오른쪽 자식 인 경우이다. */
            else
            {
                /*case 2-1*/
                if (z == (side ? z->parent->right : z->parent->left))
                {
                    z = z->parent;
                    side ? RotateLeft(z) : RotateRight(z);
                }
                /*case 2-2*/
                z->parent->color = BLACK;
                grandparent->color = RED;
                side ? RotateRight(grandparent) : RotateLeft(grandparent);
            }
        }
        root->color = BLACK;
    } 

    //================= Delete =================//

    bool Delete(double _latitude, double _longitude, int _trashIndex)
    {
        NodePtr z = IsKey(_latitude, _longitude);
        if (!z)
            return false;
        else
        {
            int count = 0;
            if (!z->isTrash[_trashIndex]) {
                cout << "delete error" << endl;
                return false;
            }
            else {
                for (int i = 0; i < 5; i++) {
                    if (z->isTrash[i] == 1) count++;
                }
                if (count > 1) {
                    z->isTrash[_trashIndex] = 0;
                    return true;
                }
            }

            NodePtr x, y;
            Color OriginalColor = z->color;

            /*자식이 없거나 1개인 경우
                    삭제할 노드(z)가 블랙이면 doulbe red이므로 fix*/
            if (z->left == leafNode)
            {
                x = z->right;
                Transplant(z, z->right);
            }
            else if (z->right == leafNode)
            {
                x = z->left;
                Transplant(z, z->left);
            }
            else
            {
                y = tree_minimum(z->right);
                OriginalColor = y->color;
                x = y->right; //y의 왼쪽 자식은 없다.

                if (y->parent == z)
                {                  //z의 오른쪽 자식이 가장 작은 key
                    x->parent = y; // x가 leafnode일 때, fix하게 될 때 사용
                }
                else
                {
                    Transplant(y, y->right);
                    y->right = z->right;
                    y->right->parent = y;
                }
                Transplant(z, y);
                y->left = z->left;
                y->left->parent = y;
                y->color = z->color;
            }
            delete z;
            if (OriginalColor == BLACK)
            {
                DelteFixUp(x);
            }
        }
        return true;
    }

    void DelteFixUp(NodePtr x)
    {
        NodePtr s; //형제노드 s

        //root이거나 double black 이 깨질때 까지
        while (x != root && x->color == BLACK)
        {
            /* x가 p[x]의 왼쪽자식인 경우 */
            if (x == x->parent->left)
            {
                s = x->parent->right;
                // case 1
                if (s->color == RED)
                {
                    s->color = BLACK;
                    x->parent->color = RED;
                    RotateLeft(x->parent);
                    s = x->parent->right;
                }

                // case 2
                if (s->left->color == BLACK && s->right->color == BLACK)
                {
                    s->color = RED;
                    x = x->parent;
                }
                else
                {
                    // case 3
                    if (s->right->color == BLACK)
                    {
                        s->left->color = BLACK;
                        s->color = RED;
                        RotateRight(s);
                        s = x->parent->right;
                    }

                    // case 4
                    s->color = x->parent->color;
                    x->parent->color = BLACK;
                    s->right->color = BLACK;
                    RotateLeft(x->parent);
                    x = root;
                }
            }

            /*x가 p[x]의 오른쪽 자식인 경우*/
            else
            {
                s = x->parent->left;
                // case 1
                if (s->color == RED)
                {
                    s->color = BLACK;
                    x->parent->color = RED;
                    RotateRight(x->parent);
                    s = x->parent->left;
                }

                // case 2
                if (s->left->color == BLACK && s->right->color == BLACK)
                {
                    s->color = RED;
                    x = x->parent;
                }
                else
                {
                    // case 3
                    if (s->left->color == BLACK)
                    {
                        s->right->color = BLACK;
                        s->color = RED;
                        RotateLeft(s);
                        s = x->parent->left;
                    }
                    // case 4
                    s->color = x->parent->color;
                    x->parent->color = BLACK;
                    s->left->color = BLACK;
                    RotateRight(x->parent);
                    x = root;
                }
            }
        }
        x->color = BLACK;
        root->color = BLACK;
    }


    /* u의 위치에 v를 이식 */
    void Transplant(NodePtr u, NodePtr v)
    {
        if (u->parent == nullptr)
            root = v;
        else if (u == u->parent->left)
            u->parent->left = v;
        else
            u->parent->right = v;

        v->parent = u->parent;
    }



    /*x를 중심으로 왼쪽으로 회전*/
    void RotateLeft(NodePtr x)
    {
        NodePtr y;

        y = x->right;
        x->right = y->left;
        if (y->left != leafNode)
        {
            y->left->parent = x;
        }
        y->parent = x->parent;

        if (!x->parent)
        {
            root = y;
        }
        else if (x == x->parent->left)
        {
            x->parent->left = y;
        }
        else
        {
            x->parent->right = y;
        }
        x->parent = y;
        y->left = x;
    }

    /*x를 중심으로 오른쪽으로 회전*/
    void RotateRight(NodePtr y) 
    {
        NodePtr x;

        x = y->left;
        y->left = x->right;
        if (x->right != leafNode)
        {
            x->right->parent = y;
        }
        x->parent = y->parent;

        if (!y->parent)
        {
            root = x;
        }
        else if (y == y->parent->left)
        {
            y->parent->left = x;
        }
        else
        {
            y->parent->right = x;
        }
        y->parent = x;
        x->right = y;
    }

    /*show tree*/
    void print_helper(NodePtr root, string indent, bool last) // 재귀
    {
        // print the tree structure on the screen
        if (root != leafNode)
        {
            cout << indent;
            if (last)
            {
                cout << "R----";
                indent += "     ";
            }
            else
            {
                cout << "L----";
                indent += "|    ";
            }

            string sColor = (root->color == RED) ? "RED" : "BLACK";
            cout << setprecision(12) << "(" << root->latitude << " " << root->longitude << ")" 
                << root->isTrash[0] << root->isTrash[1] << root->isTrash[2] << root->isTrash[3] 
                << root->isTrash[4] << " (" << sColor << ")" << endl;
            print_helper(root->left, indent, false);
            print_helper(root->right, indent, true);
        }
    }

    /*중위순회*/
    double pre_latitude, pre_longitude; // 중위순회 시, 이전 노드의 위도, 경도 값

    void Inorder(NodePtr target, NodePtr startTarget, NodePtr endTarget, bool _side) {

        if (target == leafNode)
            return;
        Inorder(target->left, startTarget, endTarget, _side);
        if (_side == target->side) {
            if ((target->latitude > startTarget->latitude) && (target->latitude < endTarget->latitude)) {
                cout << setprecision(12) << "(" << target->latitude << ", " << target->longitude << ") \n";
                for (int i = 0; i < 5; i++) {
                    if (target->isTrash[i]) {
                        switch (i) {
                        case 0:
                            expect_point += 5; break;
                        case 1:
                            expect_point += 7; break;
                        case 2:
                            expect_point += 7; break;
                        case 3:
                            expect_point += 10; break;
                        case 4:
                            expect_point += 3; break;
                        }
                    }
                }
            }
            expect_distance += pow((pow(pre_latitude - target->latitude, 2) + pow(pre_longitude - target->longitude, 2)), 0.5);
            pre_latitude = target->latitude;
            pre_longitude = target->longitude;
        }

        Inorder(target->right, startTarget, endTarget, _side);

    }

    void printExpectation() {
        expect_distance = static_cast<double>(expect_distance);
        expect_time = expect_distance * 15; // 예상시간은 예상 거리(km) * 15(m) 
        cout << "\nexpect_time " << expect_time << endl;

        cout << "\n<Expect>" << endl;
        cout << setprecision(5) << "Distance: " << expect_distance << " km" << endl;
        cout << "Time: " << expect_time / 60 << "h " << expect_time % 60 << "m " << endl;
        cout << "Point: " << expect_point << endl;
        clearExpectation();
    }

    void clearExpectation() {
        expect_distance = 0; expect_time = 0; expect_point = 0;
        pre_latitude = 0; pre_longitude = 0;
    }
    
public:
    RBTREE()
    {
        leafNode = new node;
        leafNode->color = BLACK;
        leafNode->left = nullptr;
        leafNode->right = nullptr;
        leafNode->parent = nullptr;
        root = leafNode;
    }
    //최솟값 찾기
    NodePtr tree_minimum(NodePtr x)
    {
        while (x->left != leafNode)
        {
            x = x->left;
        }
        return x;
    }
    //최댓값 찾기
    NodePtr tree_maximum(NodePtr x)
    {
        while (x->right != leafNode)
        {
            x = x->right;
        }
        return x;
    }

    void DisplayMenuBoard()
    {
        cout << "               Menu " << endl;
        cout << "          1. Insert Key     " << endl;
        cout << "          2. Delete Key     " << endl;
        cout << "          3. Show Tree      " << endl;
        cout << "          4. choose order   " << endl;
        cout << "          5. show Menu      " << endl;
        cout << "          6. clear Display  " << endl;
        cout << "          7. exit           " << endl;
        cout << endl;
    }
    void SelectMenu()
    {
        DisplayMenuBoard();
        int i = -1;

        while (i != 7)
        {
            cout << "--> select   :   ";
            cin >> i;
            switch (i)
            {
            case 1:
                Insert_helper();
                break;
            case 2:
                Delete_helper();
                break;
            case 3:
                print_helper(root, "", true);
                break;
            case 4:
                Order_helper();
                break;
            case 5:
                DisplayMenuBoard();
                break;
            case 6:
                system("cls");
                DisplayMenuBoard();
                break;
            case 7:
                return;
            default:
                std::cout << " !!! Wrong entered !!!\n"
                    << std::endl;
            }
        }
    }

    void Insert_helper()
    {
        double _latitude, _longitude;
        bool _isTrash[5];
        bool _side = (rand() % 2);
        string str; // 필요없는 변수값을 받아냄
        int number, widths, heights;

        fstream fs;
        fs.open("data3.txt");

        
        for (int i = 0; i < 11; i++) {
            fs >> str; 
        }

        while (!fs.eof()) {
            _side = (rand() % 2);
            fs >> number >> str >> widths >> heights
                >> _latitude >> _longitude >> _isTrash[0] >> _isTrash[1] >> _isTrash[2] >> _isTrash[3] >> _isTrash[4];
            
            
            Insert(_latitude, _longitude, _isTrash, _side);
        }
        cout << "Insert Done!" << endl;
        fs.close();

    }


    void Delete_helper()
    {
        double _latitude, _longitude;
        int _trashIndex;
        cout << "Key to delete  :  ";
        cin >> _latitude >> _longitude >> _trashIndex;
        if (!Delete(_latitude, _longitude, _trashIndex))
        {
            cout << "!!! (" << _latitude << ", " << _longitude << ") is not exists !!!\n";
        }
        else {
            cout << "Delete Done" << endl;
        }
        return;
    }
    void Order_helper()
    {
        int i;
        cout << "         == Order Menu ==" << std::endl;
        cout << "          1. InOrder" << std::endl;
        cout << "          2. exit" << std::endl;
        std::cout << " --> select  :  ";

        cin >> i;
        switch (i)
        {
        case 1:
            double s_latitude, s_longitude, e_latitude, e_longitude;
            int _side;
            cout << "Start Key: "; cin >> s_latitude >> s_longitude;
            cout << "End Key: "; cin >> e_latitude >> e_longitude;
            cout << "Side (left:0, right:1): "; cin >> _side;
            //Inorder(this->root);

            pre_latitude = s_latitude; pre_longitude = s_longitude;

            Inorder(this->root, IsKey(s_latitude, s_longitude), IsKey(e_latitude, e_longitude), _side);
            printExpectation();
            clearExpectation();
            cout << endl;
            break;
        case 2:
            return;
        default:
            cout << " !!! Wrong enter !!!\n" << endl;
            break;
        }
        return;
    }
};

int main()
{
    RBTREE tree;
    tree.SelectMenu();

    return 0;
}