[Data Structure] Tree

Tree(트리)?

• 트리는 값을 가진 노드(Node)와 이 노드들을 연결해주는 간선(Edge)으로 이루어진 자료구조이다.
  • 트리는 하나의 루트(Root) 노드를 가진다.
  • 루트 노드는 0개 이상의 자식 노드를 가진다.
  • 그 자식 노드 또한 0개 이상의 자식 노드를 갖고 있고, 이는 반복적으로 정의된다.

• 트리의 모든 노드들은 0개 이상의 자식 노드를 갖고 있으며, 보통 부모-자식 관계로 부른다.
  • 가족 관계도를 트리 형식으로 나타내며, 자료구조인 트리도 이 방식을 그대로 구현한 것

그래프 vs 트리

• 그래프와 트리의 차이점은 사이클(Cycle)의 유무로 설명할 수 있다.
  • 사이클이 존재하지 않는 그래프라고 하여 무조건 트리인 것은 아니다.
  • 사이클이 없는 그래프는 Forest라고 지칭한다.
  • 트리의 경우 사이클이 없고 모든 노드가 간선으로 연결되어 있다.

트리의 특징

• 트리에는 사이클이 존재할 수 없다.
  • 만약 사이클이 만들어진다면, 그것은 트리가 아니고 그래프다
• 모든 노드는 자료형으로 표현이 가능하다.
• 루트에서 한 노드로 가는 경로는 유일한 경로 뿐이다.
• 노드의 개수가 N개면, 간선은 N-1개를 가진다.
• 그래프의 한 종류이다. 최소 연결 트리 라고도 불린다.
  
  • 트리는 DAG(Directed Acyclic Graphs, 방향성이 있는 비순환 그래프)의 한 종류
  • loop나 circuit이 없다. 당연히 self-loop도 없다.
• 트리는 계층 모델이다.
• 한 개의 루트 노드만이 존재하며 모든 자식 노드는 한 개의 부모 노드만을 가진다.
  
  • 부모-자식 관계이므로 흐름은 top-bottom 아니면 bottom-top으로 이루어진다.
• 순회는 Pre-order, In-order 아니면 Post-order로 이루어진다. 이 3가지 모두 DFS/BFS안에 있다.

트리와 관련된 용어

• 루트 노드(Root Node)
  • 부모가 없는 노드, 트리는 하나의 루트 노드만을 가진다
• 단말 노드(Leaf Node)
  • 자식이 없는 노드, 말단 노드 혹은 잎 노드라고 부른다.
• 내부 노드(Internal Node)
  • 단말 노드가 아닌 노드
• 간선(Edge)
  • 노드를 연결하는 선
  • link 혹은 branch라고도 부름
• 형제(Sibling)
  • 같은 부모를 가지는 노드
• 노드의 크기(Size)
  • 자신을 포함한 모든 자손 노드의 개수
• 노드의 깊이(Depth)
  • 루트에서 어떤 노드에 도달하기 위해 거쳐야 하는 간선의 수
• 노드의 레벨(Level)
  • 루트에서 어떤 노드에 도달하기 위해 거쳐야 하는 간선의 수
• 노드의 차수(Degree)
  • 하위 트리 개수 / 간선 수 (degree)
  • 각 노드가 지닌 가지의 수
• 트리의 차수(Degree of Tree)
  • 트리의 최대 차수
• 트리의 높이(Height)
  • 루트 노드에서 가장 깊숙히 있는 노드의 깊이

트리의 순회 방식

• 트리를 순회하는 방식은 4가지가 존재한다.

전위 순회(Pre-order)

• 각 부모 노드를 순차적으로 먼저 방문하는 방식이다.
  • 부모 → 왼쪽 자식 → 오른쪽 자식
• 1 -> 2 -> 4 -> 8 -> 9 -> 5 -> 10 -> 11 -> 3 -> 6 -> 13 -> 7 -> 14

중위 순회(In-order)

• 왼쪽 하위 트리를 방문 후 부모 노드를 방문하는 방식이다.
  • 왼쪽 자식 → 부모 → 오른쪽 자식
• 8 → 4 → 9 → 2 → 10 → 5 → 11 → 1 → 6 → 13 → 3 →14 → 7

후위 순회(Post-order)

• 왼쪽 하위 트리부터 하위를 모두 방문 후 부모 노드를 방문하는 방식이다.
  • 왼쪽 자식 → 오른쪽 자식 → 부모
• 8 → 9 → 4 → 10 → 11 → 5 → 2 → 13 → 6 → 14 → 7 → 3 → 1

레벨 순회(Level-order)

• 부모 노드부터 계층 별로 방문하는 방식이다.
• 1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → 9 → 10 → 11 → 13 → 14

 

 

 

출처

https://gmlwjd9405.github.io/2018/08/12/data-structure-tree.html

[자료구조] 트리(Tree)란 - Heee's Development Blog

https://github.com/gyoogle/tech-interview-for-developer

GitHub - gyoogle/tech-interview-for-developer: 👶🏻 신입 개발자 전공 지식 & 기술 면접 백과사전 📖