[자료구조] 트리(Tree)란?

🚦 이번 포스팅에서는 〰️

▶️ 트리(Tree) 란?
▶️ 트리(Tree) 의 종류 - 일반트리, 이진트리, 이진탐색트리, 트라이
▶️ 트리(Tree) 구현 방법
▶️ 트리(Tree) vs 그래프(Graph)

 

📌 트리(Tree) 란?

---

: 그래프의 종류(연결된 graph이며 Cycle이 없다)로, 노드로 이루어진 자료구조이다. STL tree가 존재하나, 활용 상황이 다 달라 사용되기 어렵기 때문에 직접 구현해서 사용한다.

 

https://towardsdatascience.com/8-useful-tree-data-structures-worth-knowing-8532c7231e8c

 

🔆 Tree 종류 (큰 틀)

• Rooted Tree, Unrooted Tree : root의 존재 여부
• Ordered Tree, Unordered Tree : 자손의 순위가 있는지의 여부
• Directed Tree, Undirected Tree : 에지 방향이 있는지의 여부
• Binary Tree, k-ary Tree : rooted tree 중에서 차수의 정도

 

🔆 Tree 용어 정리

• root : 부모가 없는 노드, 하나만 존재하거나 없다.
• subtree : 루트를 제거했을 때 만들어지는 tree들
• parents, child
• sibling : 같은 부모를 가지는 노드
• depth, height : depth는 루트부터, height는 맨 아래부터
• level : 트리의 특정 깊이를 가지는 노드의 집합
• leaf node : 자식이 없는 노드, 말단노드라고도 불린다.
• internal node : leaf node가 아닌 노드
• degree : 하위 트리개수로, rooted에서는 밑에만 세고 unrooted에서는 다 센다.
• Least Common Ancestor(LCS) : 최단 공통 조상

 

 

📌 트리(Tree) 의 종류 - 일반트리, 이진트리, 이진탐색트리, 트라이

---

1. 일반트리 (General Tree) : 계층에 대한 제한이 없는 트리, 즉 둘 이상의 자식 노드를 가질 수 있는 트리

 

2. 이진트리 (Binary Tree) : 자식 노드의 개수가 0~2개인 트리

  1) 전 이진트리 (Full Binary Tree)

• 모든 노드가 0개 또는 2개의 자식 노드를 갖는 트리
•  

  2) 완전 이진트리 (Complete Binary Tree)

• 트리의 모든 높이에서 노드가 꽉 차있는 이진트리로, 마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있다.
• 마지막 레벨은 꽉 차있지 않아도 되지만, 반드시 노드가 왼쪽에서 오른쪽으로 채워져 있어야 한다.
• 따라서, 완전 이진트리는 마지막 레벨 h에서 1 ~ 2h-1개의 노드를 가진다.
• 완전 이진트리는 배열을 사용해 효율적인 표현이 가능하다.
•  

  3) 포화 이진트리 (Perfect Binary Tree)

• 전 이진트리이면서 완전 이진트리인 경우로, 모든 말단 노드는 같은 높이에 있어야 하며, 마지막 level에 노드의 개수가 최대여야 한다.
• 트리의 높이가 k일때, 노드의 개수가 정확히 2^(k-1) 개여야 한다.
•  

 

 

🔆 이진트리의 순회

  1) 중위 순회 (in-order traversal) : 왼쪽 가지 -> 현재 노드 -> 오른쪽 가지

void inOrderTraversal(TreeNode node)
{
  if(node != null)
  {
   inOrderTraversal(node.left);
   visit(node);
   inOrderTraversal(node.right);
  }
}

 

  2) 전위 순회 (pre-order traversal) : 현재 노드 -> 왼쪽 가지 -> 오른쪽 가지

void preOrderTraversal(TreeNode node) 
{
  if(node != null) 
  {
   visit(node);
   preOrderTraversal(node.left);
   preOrderTraversal(node.right);
  }
}

 

  3) 후위 순회 (post-order traversal) : 왼쪽 가지 -> 오른쪽 가지 -> 현재 노드

void postOrderTraversal(TreeNode node) 
{
  if(node != null) 
  {
   postOrderTraversal(node.left);
   postOrderTraversal(node.right);
   visit(node);
  }
}

 

3. 이진탐색트리 (Binary Search Tree)

: 모든 노드 n이 왼쪽 자식들 <= n < 모든 오른쪽 자식들을 만족하는 이진 트리

 

 

🔆 균형트리 vs 비균형 트리

균형 트리는 O(logN) 시간에 insert와 find를 할 수 있을 정도로 균형이 잘 잡혀있는 트리이다.

EX ) 레드-블랙 트리, AVL 트리

 

 

🔆 이진 힙 (최소힙 & 최대힙)

- 최소힙 (Min Heap)

• 트리의 마지막 단계에서 오른쪽 부분을 뺀 나머지 부분이 가득 채워진 완전 이진트리
• 각 노드의 원소가 자식들의 원소보다 작다
• 가장 작은 값 == 루트노드
• 힙에 N개가 있다면 트리의 높이 = log(N)

- 최대힙 (Max Heap)

• 트리의 마지막 단계에서 오른쪽 부분을 뺀 나머지 부분이 가득 채워진 완전 이진트리
• 각 노드의 원소가 자식들의 원소보다 크다
• 가장 큰 값 == 루트노드
• 힙에 N개가 있다면 트리의 높이 = log(N)

 

--> 힙(Heap)이란? 에서 더 자세히 다룬다.

 

🔆 트라이 (Trie) ?

: n-ary 트리의 변종으로, Prefix Tree라고도 부른다.

• 각 노드에 문자를 저장하는 자료구조
• 트리를 아래쪽으로 순회하면 단어 하나가 나온다.
• 접두사를 빠르게 찾아보기 위한 대표적 방식이다.
• 유효한 단어 집합을 이용하는 많은 문제들이 트라이를 이용한다.

 

 

📌 트리(Tree) 구현 방법

---

그래프의 한 종류이기 때문에 그래프 구현방법으로 구현할 수 있다. (인접 배열 or 인접 리스트 이용)

- 인접 배열

1. 1차원 배열에 자신의 부모 노드만 저장하는 방법
   • 트리는 부모 노드를 0개 또는 1개를 가지기 때문
   • 부모 노드가 0개 = 루트(root)노드
2. 이진트리의 경우, 2차원 배열에 자식 노드를 저장하는 방법
   • 이진트리는 각 노드가 최대 두개의 자식을 갖는 트리이기 때문
   • 예시 ) A[i][0] : 왼쪽 자식 노드, A[i][1] : 오른쪽 자식 노드

- 인접 리스트

1. 가중치가 없는 트리인 경우
   • ArrayList <ArrayList> list = new ArrayList<>();
2. 가중치가 있는 트리인 경우
   • class Node {int num, dist;} // 노드 번호, 거리 정의
   • ArrayList[] list = new ArrayList[정점의 수 + 1];

 

📌 트리(Tree) vs 그래프(Graph)

---

	그래프 (Graph)	트리 (Tree)
정의	노드(node)와 노드를 연결하는 간선(edge)을 하나로 모아놓은 자료구조	그래프의 한 종류
방향성	Directed, Undirected 둘다 존재	Directed만 존재
사이클	가능 자체간선(self-loop), 순환 그래프(cyclic), 비순환 그래프(Acyclic) 모두 존재	불가능 비순환 그래프(Acyclic)
루트 노드	루트 노드의 개념 X	한개의 루트 노드만 존재 모든 자식 노드는 한개의 부모 노드만 가짐
부모-자식	부모-자식 개념 X	top-down(하향식) 또는 botton-top(상향식) 으로 이루어짐
모델	네트워크 모델	계층 모델
순회	DFS, BFS	DFS, BFS 안의 Pre-order, In-order, Post-order
간선의 수	그래프에 따라 간선의 수가 다름 (없을 수도 있음)	노드가 N인 트리는 항상 N-1의 간선을 가짐
경로	X	임의의 두 노드 간의 경로는 유일
예시 및 종류	지도, 지하철 노선도의 최단 경로, 전기 회로의 소자들, 도로, 선수 과목	이진 트리, 이진 탐색 트리, 균형트리(AVL 트리, red-black 트리), 이진 힙(최대 힙, 최소 힙) 등

 

 

🔆 [자료구조] 다른 Posting 보러 가기 🔆

✅ 스택(Stack)이란?

✅ 큐(Queue)란?

✅ 힙(Heap)이란?

 

 

[Reference]

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