트리(Tree)

트리 - hello70825.tistory.com/163

트리의 순회 - (작성중)

트리를 이용한 알고리즘 문제 풀이 - hello70825.tistory.com/164

 

참고

트리 기본 개념, 트리의 순회, 코드 - blog.naver.com/kks227/220788265724

트리 세부 내용 - gmlwjd9405.github.io/2018/08/12/data-structure-tree.html

 

 

======================================================================

 

 

 

 

트리는 그래프의 종류중 하나인 자료구조입니다.

 

트리의 특징

1. 싸이클이 존재하지 않는다.

2. 정점 2개를 아무렇게 잡고, 정점끼리 연결하는 단순 경로는 무조건 1개만 존재한다.

3. 간선의 개수는 무조건 정점의 개수에 1을 뺀 값이다.

 

 

사진에 나온 색깔이 칠해진 직사각형에 대해 설명을 하자면

루트노드는 부모가 없는 노드로 보통 트리를 그릴때 가장 위에 그립니다.

리프노드는 자식이 없는 노드를 뜻합니다.

정점 S와 정점 A만을 보고 있을 때, 정점 S는 정점 A의 부모노드이고, 정점 A는 정점 S의 자식노드입니다.

 

그 외에도

정점 X와 정점 Y는 부모가 정점 E로 같으므로 형제노드라고 부를 수 있습니다.

정점 {S, A, C, Z}는 위 사진에서 보이는 트리의 서브트리라고 부를 수 있습니다.

그리고 트리의 깊이는 LEVEL이라고 부릅니다. 루트노드는 LEVEL의 값이 0이며 한 칸씩 내려갈 때마다 LEVEL의 값이 1씩 올라갑니다.

 

 

 

먼저 코드를 살펴보기전에 구현한 기능과 입력값에 대해 설명하겠습니다.

 

기능

- 노드끼리 연결 시켜주는 connect_node

- 트리를 만들어주는 make_tree

- 서브트리를 추가시키는 add_tree

- 현재 트리에서 서브트리를 삭제하고, 삭제한 서브트리를 새로운 트리로 만드는 delete_sub_tree

- 트리에서 어떠한 노드를 삭제시키고, 삭제한 노드의 부모와 삭제한 노드의 자식을 연결시켜주는 delete_node

 

노드는 위에 나온 그림에서 알파벳 대신 숫자를 넣고, 4개를 노드를 추가로 붙여 총 15개의 노드를 만들어보았습니다.

 

여기서 {12, 13, 14} 노드집합은 먼저 connect_node를 이용하여 연결시켜주고, make_tree를 이용할때 노드 0번~10번까지 있는 트리, 노드 11번만 있는 트리, 노드 12번~14번만 있는 노드로 총 3개의 트리를 만들 예정입니다.

그런다음 add_tree를 이용하여 4번 노드와 11번 노드, 3번 노드와 12번 노드를 이어줍니다.

delete_sub_tree를 이용하여 다시 {11} 서브트리와 {12, 13, 14} 서브트리를 떼어낼 것이구요.

마지막으로 delete_node를 1번 노드에 적용시켜서 1번 노드를 없애준다음 1번 노드의 부모노드인 0번 노드와 1번 노드의 자식노드인 4, 5번 노드를 연결하려합니다.

 

 

이렇게 해서 나온 코드는 아래와 같습니다.

#include <bits/stdc++.h>
using namespace std;
 
class Tree
{
private:
    int N;
    vector<int> parent;
    vector<vector<int>> children;
    vector<vector<int>> adj;
    vector<bool> visited;
public:
    Tree(): N(0){}
    Tree(int n): N(n)
    {
        parent.resize(N,-1);
        children.resize(N);
        adj.resize(N);
        visited.resize(N,false);
    }
    void connect_node(int x, int y)
    {
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    void make_tree()
    {
        queue<int> q;
        for(int i=0; i<N; i++) {
            if(visited[i] == true) continue;
            q.push(i);
            visited[i] = true;
            while (!q.empty()) {
                int x = q.front();
                q.pop();
                for (int nx: adj[x]) {
                    if (!visited[nx]) {
                        visited[nx] = true;
                        parent[nx] = x;
                        children[x].push_back(nx);
                        q.push(nx);
                    }
                }
            }
        }
    }
    void add_tree(int p_node, int c_node)
    {
        parent[c_node] = p_node;
        children[p_node].push_back(c_node);
    }
    void delete_sub_tree(int new_root_node)
    {
        int del_parent = parent[new_root_node];
        children[del_parent].erase(remove(children[del_parent].begin(), children[del_parent].end(), new_root_node), children[del_parent].end());
        parent[new_root_node] = -1;
    }
 
    void delete_node(int node)
    {
        int del_parent = parent[node];
        children[del_parent].erase(remove(children[del_parent].begin(), children[del_parent].end(), node), children[del_parent].end());
        for(int nx: children[node])
        {
            children[del_parent].push_back(nx);
            parent[nx] = del_parent;
        }
        parent[node] = -1;
        children[node].clear();
    }
 
    void print()
    {
        for(int i=0; i<N; i++)
        {
            int num = 0;
            cout << "Node " << i << ": " << "parent = { " << parent[i] << " }, children = { ";
            for(int x: children[i])
            {
                cout << x << ", ";
                num += 1;
            }
            if(num != 0) cout << "\b\b }" << endl;
            else cout << " }" << endl;
        }
    }
};
 
int main()
{
    Tree tree(15);
 
    tree.connect_node(0,1);
    tree.connect_node(1,4);
    tree.connect_node(1,5);
    tree.connect_node(5,8);
    tree.connect_node(0,2);
    tree.connect_node(0,3);
    tree.connect_node(2,6);
    tree.connect_node(3,7);
    tree.connect_node(7,9);
    tree.connect_node(7,10);
 
    tree.connect_node(12,13);
    tree.connect_node(12,14);
 
    tree.make_tree();
 
    tree.print();
 
    cout << "===================================" << endl;
 
    tree.add_tree(4, 11);
    tree.add_tree(3, 12);
 
    tree.make_tree();
    tree.print();
 
    cout << "===================================" << endl;
 
    tree.delete_node(11);
    tree.delete_sub_tree(12);
 
    tree.print();
 
    cout << "===================================" << endl;
 
    tree.delete_node(1);
    tree.print();
 
    return 0;
}

 

 

먼저 트리에 넣어둘 노드의 개수인 N

부모노드가 몇번인지 기록해두는 parent 벡터

자식노드가 어떤 노드가 있는지 기록해두는 children벡터

노드끼리 연결시켜주는 adj 벡터

트리를 만들 때, bfs로 하는데 방문 여부를 파악하는 visited 벡터가 있습니다.

 

그리고 위 벡터들은 Tree를 생성할 때 N의 값에 맞게 크기를 조절해줍니다.

 

make_tree함수는 for문으로 노드를 하나하나 살펴보면서 해당 노드를 방문한 적이 없을 때마다 BFS를 돌려서 노드를 만들어줍니다.

이러면 visited[0] = false니까 여기서 BFS가 돌아가서 0번~10번까지 트리가 만들어지고, i=11일때 visited[11] = false이므로 루트노드만 있는 트리가 하나 만들어지고, i=12일때 BFS가 돌아가서 12번~14번까지 트리가 만들어집니다.

 

add_tree는 단순히 붙이려는 트리의 루트노드(c_node)와 그 루트노드를 연결할 다른 트리의 노드(p_node)를 연결시켜주면 됩니다.

이때 c_node의 부모노드를 p_node로 설정해주고, p_node의 자식노드에 c_node를 추가해주면 됩니다.

 

delete_sub_tree는 서브트리를 통째로 떼어낼 함수이므로 떼어낼 서브트리의 루트노드를 루트노드의 부모노드(del_parent)의 자식노드에서 삭제시키고, 떼어낼 서브트리의 루트노드의 부모노드는 -1로 설정해주면 됩니다.

 

마지막으로 delete_node는 트리에서 딱 하나의 노드만 삭제시키고, 삭제할 노드의 부모노드와 자식 노드를 서로 연결시켜줘야하므로 for문을 이용하여 붙여줍니다.

삭제할 노드의 부모노드가 가지고 있는 자식노드에서 삭제할 노드를 없애주고, 삭제할 노드가 가지고 있는 자식노드를 clear함수를 이용해 자식노드를 기록한 children벡터를 완전히 비워줍니다.

 

 

이건 출력하는 함수인데 그냥 for문을 이용하여 차례대로 해당노드의 부모노드가 무엇인지, 자식노드는 얼마나 있는지 보여주는 함수입니다.

 

int main()
{
    Tree tree(15);
 
    tree.connect_node(0,1);
    tree.connect_node(1,4);
    tree.connect_node(1,5);
    tree.connect_node(5,8);
    tree.connect_node(0,2);
    tree.connect_node(0,3);
    tree.connect_node(2,6);
    tree.connect_node(3,7);
    tree.connect_node(7,9);
    tree.connect_node(7,10);
 
    tree.connect_node(12,13);
    tree.connect_node(12,14);
 
    tree.make_tree();
 
    tree.print();
 
    cout << "===================================" << endl;
 
    tree.add_tree(4, 11);
    tree.add_tree(3, 12);
 
    tree.make_tree();
    tree.print();
 
    cout << "===================================" << endl;
 
    tree.delete_node(11);
    tree.delete_sub_tree(12);
 
    tree.print();
 
    cout << "===================================" << endl;
 
    tree.delete_node(1);
    tree.print();
 
    return 0;
}

 

일단 트리를 3개로 나눴으니 먼저 이어줄 간선은 다 이어줍니다.

 

그리고 make_tree를 하여 3개의 트리를 만들었습니다.

 

이 부분을 print함수를 이용해 출력해보면

 

이렇게 나옵니다.

 

0번 ~ 10번노드를 가지고 있는 노드는 0번 노드가 루트노드이므로 0번 노드의 부모노드는 -1이고, 나머지 11번 노드와 12번 노드도 각각 다른 트리의 루트노드이므로 부모노드가 -1로 저장했습니다.

 

이제 add_tree로 3개의 트리를 0번 노드가 루트노드인 1개의 트리로 바꾸면

 

이렇게 3번 노드의 자식노드에 12번 노드가 있고, 4번 노드의 자식노드에는 11번 노드, 11번 노드의 부모노드는 4번 노드, 12번 노드의 부모노드는 3번 노드임을 확인할 수 있습니다.

 

이번엔 다시 11번 노드를 delete_node, 12번 노드를 delete_sub_tree로 떼어주면

 

이렇게 다시 3번 노드와 4번 노드의 자식 노드에서 12번 노드와 11번 노드가 사라진 것을 확인할 수 있고, 11번 노드와 12번 노드의 부모노드는 다시 -1로 돌아간 것을 확인할 수 있습니다.

 

 

마지막으로 1번 노드를 delete_node를 해당 노드만 삭제해보겠습니다.

먼저 그림을 통해 확인하자면

 

위 사진의 1번 노드가 사라지면서

 

 

1번 노드의 자식노드였던 4번 노드, 5번 노드가 0번 노드에 붙게될 것 입니다.

 

이렇게 0번 노드의 자식노드에 1번 노드가 사라졌고, 1번 노드의 부모노드는 -1로 바뀌었고, 4번과 5번 노드의 부모노드는 0번 노드로 바뀌었다는 것을 알 수 있습니다.

 

 

트리의 순회는 나중에 작성하겠습니다...