트리
📢 데이터를 계층구조를 이용하여 표현하는 자료구조
아래와 같은 구조를 트리라고 해요. 트리에는 다양한 특징들이 있으니 아래에서 살펴보도록 해요!
앞으로 노드 라는 말이 많이 나올텐데 위의 그림에서 A, B, C 등등 각각을 하나의 노드 라고 합니다! 꼭 기억하세요!!
🎨 트리 용어 및 특징
1. Parent-Child 관계를 가진 노드 들의 집합을 트리라고 한다.
- 노드 F를 기준으로 위의 C를 부모(Parent) 아래 J와 K를 자식(Child)라고 해요.
- 모든 부모-자식 관계는 각 노드를 기준으로 상대적입니다.
- 자식이 없는 노드, 부모가 없는 노드도 있습니다.
2. 부모(Parent)가 같은 노드들을 형제(Sibling)노드라고 한다.
3. 자식(child)가 없다면 External node이다 & 자식(child)이 하나라도 있다면 Internal node이다.
- 노드 B는 Child가 없으므로 External Node**
- External Node는 leaf 라고 하기도 해요.
- 노드 C는 노드 F, G 2개의 Child가 있으므로 Internal Node
4. Tree의 최상위 node를 Root라 한다.
5. 특정 Node v를 Root로 하여 v의 자식들을 모두 포함한 Tree를 SubTree라 한다.
- SubTree의 Root는 어떤 Node든 가능해요.
6. Edge는 Node와 Node 사이를 연결 한 것을 말한다.
- 그림에서는 C와 F, G와 K를 연결한 것을 Edge라고 가리키지만 C와 G도 Edge입니다.
- 트리에서 연결되어 있는 선들을 Edge라고 생각하면 됩니다.
7. Size(크기)는 자기 Node와 자식의 수를 말한다.
8. Path는 임의의 Node v에서 Node w로 갈 때 나타나는 Node 순서를 말한다.
- Node A에서 H까지 가는 Path는 A -> D -> H입니다.
- 굳이 Root에서 시작하지 않아도 됩니다.
9. Depth(깊이)는 Root에서 해당 Node까지의 Edge 수를 의미한다.
10. 같은 Depth를 가지는 Node를 묶어 Level이라 한다.
- Root Node를 Level 1로 간주해요.
- 밑으로 내려갈수록 Level이 1씩 올라가요.
11. 각 Node가 가지고 있는 Edge 수를 Degree(차수)라 한다.
12. Tree에서 가장 큰 Depth값을 Height(높이)라 한다.
⏰ 시간 복잡도
삽입(Insert), 제거(Delete)
- 스택의 가장 윗부분에서 이루어지는 연산이에요.
- O(1)의 시간 복잡도를 가져요.
탐색(Search)
- 스택 내부에서 원하는 데이터를 찾을 때까지 연산을 수행해요.
- O(n)의 시간 복잡도를 가져요.
📋 예제
백준 9372 - 상근이의 여행
백준 9372 - 해답
백준 11725 - 트리의 부모 찾기
백준 11725 - 해답
내가 못할 게 뭐가 있지?