5. 트리 [tree] basic

Tree

트리는 노드로 이루어진 자료 구조

계층적 구조의 자료구조를 말한다. "root 노드" 부터 "leaf노드" 까지 계층적 구조로 되어있다.

nodes

root : 부모가 없는 노드, 트리는 하나의 루트 노드만을 가진다.
leaf : 자식이 없는 노드. external 노드라고도 부른다.
internal nodes : leaf 노드를 제외한 노드들

realation

parent - child : 부모 자식 관계. 부모와 자식은 이어져 있다.
siblings : 형제관계. 같은 부모를 가진 노드를 말한다.
ancestors : 조상 노드. 부모 혹은 부모의 조상을 말한다.
descendants : 자손 노드. 자식 혹은 자식의 자손을 말한다.

노드가 가지는 값

depth : root 로 부터의 거리 (root의 depth는 0)
parent : 부모를 가리키는 포인터
childs : 자식을 가리키는 포인터들의 집합
degree : 노드의 자식 수 (손자 X)
subTree : 본인을 root로 하는 tree
size : subTree의 size
height : subTree의 height

others

level : 같은 depth를 가진 노드의 집합
height : 트리의 높이. depth 중 가장 큰값.
size : 노드의 개수

수행시간

worst case

find : O(n)
-> insert,erase, update : O(n)

구현

Node

class Node {
public:
    Node *parent;
    vector<Node *> childList;
    int val;
    int depth;

    Node(Node *p, int val) {
        this->parent = p;
        this->val = val;
        this->depth = parent->depth + 1;
    }

    Node(int val, int depth) {
        parent = nullptr;
        this->val = val;
        this->depth = depth;
    }
};

Tree

class Tree {
public:
    Node *root;
    vector<Node *> nodeList;

    Tree() {
        root = new Node(1, 0);
        nodeList.emplace_back(root);
    }
    
    Node *findNode(int x) {
        for (auto node: nodeList) {
            if (node->val == x) {
                return node;
            }
        }
        return nullptr;
    }

    void insert(int x, int y) {
        Node *parentNode = findNode(x);
        if (parentNode == nullptr || findNode(y) != nullptr) {
            cout << -1 << '\n';
            return;
        }
        Node *newNode = new Node(parentNode, y);
        parentNode->childList.emplace_back(newNode);
        nodeList.push_back(newNode);
    }

    void erase(int x) {
        Node *delNode = findNode(x);
        if (delNode == nullptr) {
            cout << -1 << '\n';
            return;
        }
        for (auto node: delNode->childList) {
            delNode->parent->childList.emplace_back(node);
            node->parent = delNode->parent;
        }
        for (int i = 0; i < delNode->parent->childList.size(); i++) {
            if (delNode->parent->childList[i] == delNode) {
                delNode->parent->childList.erase(delNode->parent->childList.begin() + i);
                break;
            }
        }
        for (int i = 0; i < nodeList.size(); i++) {
            if (nodeList[i] == delNode) {
                nodeList.erase(nodeList.begin() + i);
                break;
            }
        }

    }

    void parent(int x) {
        Node *targetNode = findNode(x);
        if (targetNode == nullptr) {
            cout << -1 << '\n';
            return;
        }
        cout << targetNode->parent->val << '\n';

    }

    void child(int x) {
        Node *targetNode = findNode(x);
        if (targetNode == nullptr || targetNode->childList.empty()) {
            cout << -1 << '\n';
            return;
        }
        for (auto node: targetNode->childList) {
            cout << node->val << ' ';
        }
        cout << '\n';

    }
};