🔵 트리 (tree)
나무를 뜻하는 그 트리. 나무를 뒤집어놓은 거 처럼 생겨서 그랬대
◼ 트리 조건 및 용어
◾ 트리의 조건 ①, ②
트리는 그래프의 하위집합인데,
①연결 그래프이다. (컴포넌트가 하나)
②방향을 무시하였을 때, 싸이클이 존재하지 않는다.
-> ex
이건 ①을 충족하지 못하므로 트리가 아님. {A, B}, {C, D, E}로 컴포넌트가 나뉨.
얘 역시 ②를 충족하지 못하므로 트리가 아님. 방향을 무시했을 때 싸이클이 존재해..
◾ 트리의 성질 ③
①과 ② 두 가지 조건이 만족되면 자연스럽게
③ 트리의 간선 개수는 반드시 트리의 정점 개수 -1 이다 이라는 성질이 생긴다.
◾ 트리 용어
트리에서 제일 위에 그려진, 가장 상위의 노드를 루트 노드(root node) / 루트라고 한다. 또한 루트 노드와의 거리를 보통 그 정점의 깊이(depth), 레벨(level)이라고 부르며
깊이는 루트가 1일 때도.. 0일 때도 매번 다르지만 0부터 시작하는 경우가 많대
트리의 높이(height)는 보통 가장 깊은 정점의 깊이 또는 그에 1을 더한 값이다.
예를 들어 이 트리를 보면 루트는 제일 위에 그려진 A다.
A는 깊이 0, B와 E는 깊이 1, 나머지는 깊이 2이다.
또한 서로 인접해있는 두 정점이 있을 때 깊이가 작은 쪽을 부모노드(parent), 큰쪽을 자식노드(child)라고 한다.
또한 거리가 2이상 차이나는 관계에 대해서는 조상노드(ancestor)와 자손노드(descendant)로 부르기도 한다.
여기서는 A의 자식이 B와 E고, C의 부모는 B이다. ...
이렇게 루트를 제외하면 모든 노드가 자기 자신의 부모노드와 이어진 간선을 1개 갖기 때문에 ③이 성립한다.
몇가지 용어가 더 있는데,
형제자매 노드(sibling) : 같은 부모 노드를 둔 서로 다른 자식 노드들의 관계
리프 노드(leaf node) : 자식이 하나도 없는 노드
숲(forest) : 트리의 집합
차수 :
다른 그래프와 달리 차수(degreee)가 조금 달라졌음.
자신의 자식의 수로 보면 무방하다.
서브트리(subtree)라는 용어도 존재한다. 이는 부분트리라고도 하는데, 말 그대로 위 그림처럼 트리 속에 포함되어있는 또다른 트리를 말한다. 1의 두 자식 노드 2, 4가 있는데 여기서 4를 루트로 하는 또다른 부분 트리가 존재하는 것이다. 즉 어떤 노드의 자식들은 그 자체가 어떤 부분트리의 루트가 될 수 있다.
트리의 성질
여기서 가장 중요히 다뤄야 할 성질은 트리가 재귀적인 구조를 띈다는 것이다. 쉽게는 트리의 자식이 또 트리이고... 이런 말임.
때문에 트리는 DP나 분할 정복 등의 기법과 죽이 잘맞음.
분할 정복을 예로 들어 설명하자면, 어떤 정점의 서브트리들은 서로 절대 영역이 겹치지 않기 때문에 각 서브트리에 대한 문제를 풀어 합치면 큰 트리의 문제를 풀 수 있다.
◼ 트리 순회
- 전위순회 (preorder traversal)
- 중위순회 (inorder traversal)
- 후위순회 (postover traversal)
- 레벨순회 (level-order traversal)
5. 스레드순회
전위 순회 : 모든 정점에 대해서, 자기자신을 먼저 방문한 후에 자식들을 방문한다.
루트인 0을 먼저 방문해야 그 자식들인 1, 2를 방문할 수 있다.
후위 순회 : 전위순회와는 반대로 자식들부터 모두 방문하고서야 루트를 방문할 수 있다.
중위 순회 : 자식들 중간에 루트를 방문하는 그야말로 중간적인 면모를 보인다. 이렇게 자식이 최대 2개까지 있는 트리의 경우 왼쪽 자식->루트->오른쪽 자식순으로 순회한다. (이진트리에서만 쓰임)
레벨 순회 : 깊이가 작은 것부터 순회한다. 루트를 먼저 방문한 후 루트의 자식들을 큐에 넣는다. 그리고 큐에 들어있던 노드를 하나씩 방문할 때마다 그의 자식들을 큐에 넣는다. 이렇게 해서 큐가 빌 때까지 순회한다. ? BFS자나? 맞아~~ 같아~
⚫ 이진트리 (Binary Tree)
: 차수가 최대 2인 트리
에서 순회를 해봅시다.
void preorder(int root){
cout << root << ' ';
if(lc[root] != -1) preorder(lc[root]);
if(rc[root] != -1) preorder(rc[root]);
}
void inorder(int root){
if(lc[root] != -1) inorder(lc[root]);
cout << root << ' ';
if(rc[root] != -1) inorder(rc[root]);
}
void postorder(int root){
if(lc[root] != -1) postorder(lc[root]);
if(rc[root] != -1) postorder(rc[root]);
cout << root << ' ';
}
void levelorder(int root){
queue<int> Q;
Q.push(root);
while(!Q.empty()){
int curr = Q.front();
Q.pop();
cout << curr << ' ';
if(lc[curr] != -1) Q.push(lc[curr]);
if(rc[curr] != -1) Q.push(rc[curr]);
}
}
⚫ 트리 예제
트리의 높이 구하기
int getHeight(int root) {
int result = 1;
for (int c : children[root]) {
result = max(result, getHeight(c) + 1);
}
return result;
}이런 재귀함수를 통해 문제를 해결할 수 있다. 서브트리들의 답을 모두 알아야 자신의 답도 알 수 있으므로 후위 순회에 가깝다.
