트리(Tree)/힙(Heap) 자료구조

[ 목차 ]

트리 (Tree)

정의 및 특징

• 트리는 계층적 데이터 구조로, 노드(Node)와 간선(Edge)으로 구성된다.
• 데이터를 순차적으로 저장하지 않기 때문에 비선형 자료구조이다.
• 트리는 사이클(Cycle) 또는 순환(Loop)을 갖지 않고 연결된 무방향 그래프 구조이다.
• 최상위 노드를 루트(Root)라고 하며, 각 노드는 0개 이상의 자식 노드를 가질 수 있다.
• 두 노드 간에는 하나의 경로만 존재하여, 노드가 n개인 트리는 항상 n-1개의 간선(edge)을 가진다.
• 순회는 Pre-order, In-order 아니면 Post-order로 이루어진다. 이 3가지 모두 DFS/BFS 안에 있다
• 트리는 이진 트리, 이진 탐색 트리, 균형 트리(AVL 트리, red-black 트리), 이진 힙(최대힙, 최소힙) 등이 있다.

 

트리의 용어

• 루트 노드(root node): 부모가 없는 노드, 트리는 하나의 루트 노드만을 가진다.
• 단말 노드(leaf node): 자식이 없는 노드, ‘말단 노드’ 또는 ‘잎 노드’라고도 부른다.
• 내부(internal) 노드: 단말 노드가 아닌 노드
• 간선(edge): 노드를 연결하는 선 (link, branch 라고도 부름)
• 형제(sibling): 같은 부모를 가지는 노드
• 노드의 크기(size): 자신을 포함한 모든 자손 노드의 개수
• 노드의 깊이(depth): 루트에서 어떤 노드에 도달하기 위해 거쳐야 하는 간선의 수
• 노드의 레벨(level): 트리의 특정 깊이를 가지는 노드의 집합
• 노드의 차수(degree): 하위 트리 개수 / 간선 수 (degree) = 각 노드가 지닌 가지의 수
• 트리의 차수(degree of tree): 트리의 최대 차수
• 트리의 높이(height): 루트 노드에서 가장 깊숙히 있는 노드의 깊이

 

---

 

이진 트리 (Binary Tree)

• 각 노드가 최대 두개의 자식을 찾는 트리
• 모든 트리가 이진 트리는 아니다.
• 이진 트리 순회
  • 중위 순회 (in-order traversal) : 왼쪽 가지 -> 현재 노드 -> 오른쪽 가지
  • 전위 순회(pre-order traversal): 현재 노드 -> 왼쪽 가지 -> 오른쪽 가지
  • 후위 순회(post-order traversal): 왼쪽 가지 -> 오른쪽 가지 -> 현재 노드
    

이진 트리의 유형

1. 전 이진 트리(Full Binary Tree): 모든 노드가 0개 또는 2개의 자식을 가지는 트리 .
2. 완전 이진 트리(Complete Binary Tree): 모든 레벨이 꽉 차 있으며, 마지막 레벨은 왼쪽부터 노드가 채워진 트리
3. 포화 이진 트리(Perfect Binary Tree): 전 이진 트리이면서 완전 이진 트리인 경우, 모든 레벨이 완전히 채워진 트리.

.

---

 

이진 탐색 트리 (Binary Search Tree, BST)

정의

• 이진 탐색 트리는 각 노드가 최대 두 개의 자식을 가지는 **이진 트리(Binary Tree)**의 한 형태로, 왼쪽 자식 노드의 값은 부모 노드보다 작고, 오른쪽 자식 노드의 값은 부모 노드보다 큽니다.

특징

• 정렬된 데이터 저장: 왼쪽 서브트리는 항상 부모보다 작고, 오른쪽 서브트리는 항상 부모보다 큼.
• 효율적인 탐색: 평균 O(log n)의 시간 복잡도로 탐색, 삽입, 삭제 가능.

장단점

• 장점:
  • 정렬된 데이터 저장.
  • 평균적으로 빠른 탐색, 삽입, 삭제.
• 단점 : 편향 트리가 될 경우(예: 정렬된 데이터 삽입) 시간 복잡도가 O(n)으로 증가.

 활용 사례

• 데이터베이스 인덱스.
• 정렬된 데이터 저장 및 검색.

 

---

 

AVL 트리 (Adelson-Velsky and Landis Tree)

정의

• AVL 트리는 이진 탐색 트리의 일종으로, 모든 노드에서 왼쪽과 오른쪽 서브트리 높이 차이가 -1, 0, 1로만 유지되도록 자동으로 균형을 맞춥니다.

특징

• 균형 유지: 높이 차이가 2 이상 발생할 경우 회전을 통해 균형을 유지.
• 탐색, 삽입, 삭제: O(log n).

삽입 및 삭제

• 삽입: 새 노드 삽입 후, 높이 차이를 점검하여 불균형이 발생하면 회전 수행.
• 삭제: 노드 삭제 후, 높이 차이를 점검하여 불균형이 발생하면 회전 수행.

균형 유지 방법

- LL 회전: 왼쪽 서브트리의 왼쪽에 삽입 시.

 

- RR 회전: 오른쪽 서브트리의 오른쪽에 삽입 시.

 

- LR 회전: 왼쪽 서브트리의 오른쪽에 삽입 시.

 

- RL 회전: 오른쪽 서브트리의 왼쪽에 삽입 시.

장단점

• 장점 : 항상 균형이 유지되어 탐색 성능 보장.
• 단점 : 삽입/삭제 시 회전 연산으로 추가 오버헤드 발생.

활용 사례

• 검색 시스템.
• 대규모 데이터 저장 및 관리.

 

---

 

레드-블랙 트리(Red-Black Tree)

정의

• 레드-블랙 트리는 자기 균형 이진 탐색 트리로, 각 노드에 색상(빨강 또는 검정)을 부여하여 균형을 유지합니다.

특징

• 균형 조건:
  1. 노드는 빨강 또는 검정.
  2. 루트 노드는 항상 검정.
  3. 모든 리프 노드(널 노드)는 검정.
  4. 빨강 노드의 자식은 항상 검정(연속된 빨강 노드 금지).
  5. 모든 경로에서 검정 노드의 개수는 동일.
• 탐색, 삽입, 삭제: O(log n).

삽입 및 삭제

• 삽입: 새 노드 삽입 후, 색상 및 구조를 수정하여 균형 유지.
• 삭제: 노드 삭제 후, 색상 및 구조를 수정하여 균형 유지.

장단점

• 장점:
  • 효율적인 균형 유지로 탐색 성능 안정적.
  • 회전 연산이 AVL 트리보다 적음.
• 단점 : AVL 트리에 비해 균형이 덜 정밀하여 탐색이 약간 느릴 수 있음.

활용 사례

• 자바의 TreeMap, TreeSet 구현.
• 데이터베이스 인덱스.

 

---

 

힙(Heap)

정의 

• 힙은 데이터의 최댓값과 최솟값을 빠르게 찾기 위해 고안된 완전 이진 트리이다.
  • 최대 힙(Max-Heap) : 부모 노드의 값이 자식 노드의 값보다 크거나 같음.
  • 최소 힙(Min-Heap) : 부모 노드의 값이 자식 노드의 값보다 작거나 같음.

• 힙은 우선순위 큐를 구현하거나 정렬 알고리즘에 사용되는 자료구조이다.

특징

• 힙 속성 유지: 삽입과 삭제 시 항상 힙 속성을 유지.
• 완전 이진 트리: 마지막 레벨을 제외한 모든 레벨이 채워지고, 마지막 레벨은 왼쪽부터 순서대로 채워짐.
• 효율적인 삽입/삭제: 삽입과 삭제는 O(log n)의 시간 복잡도를 가짐.
• 정렬되지 않은 노드 간 관계: 같은 레벨에 있는 노드 간에는 특정한 순서 관계가 없음.

 

삽입과 삭제

- 삽입:

• 트리의 가장 마지막 위치에 새 노드를 삽입.
• 힙 속성을 만족할 때까지 부모 노드와 비교하며 위치를 교환(상향식 조정, Up-Heap).

예시 (최대 힙):

예시 (최대 힙, 힙의 데이터보다 클 경우):

 

- 삭제:

• 루트 노드를 삭제(최대/최소 값 추출).
• 트리의 가장 마지막 노드를 루트로 이동.
• 힙 속성을 만족할 때까지 자식 노드와 비교하며 위치를 교환(하향식 조정, Down-Heap).

예시 (최대 힙):

 

활용 사례

• 우선순위 큐(Priority Queue):
  • 최소/최대 값을 빠르게 추출.
• 힙 정렬(Heap Sort):
  • 힙을 활용한 정렬 알고리즘.
• 다익스트라 알고리즘:
  • 최소 비용 경로 탐색.

 

---

 

트리의 비교

트리 유형	특징	시간 복잡도	활용 사례
일반 트리	계층적 구조, 제한 없음	-	디렉토리 구조, 네트워크 라우팅
이진 탐색 트리	왼쪽 자식 < 부모 <= 오른쪽 자식	평균-O(log n), 최악-O(n)	정렬된 데이터 저장/검색
AVL 트리	균형 유지(높이 차이 1이하 유지)	O(log n)	검색 시스템, DB 인덱스
레드-블랙 트리	균형 유지(색상 규칙 준수)	O(log n)	자바 TreeMap, TreeSet 구현
힙(Heap)	최대/최소 값 추출, 완전 이진 트리 구조	O(log n)	우선순위 큐, 힙 정렬

 

 

---

 

글로만 이해가 잘 안된다면, 해당 영상부터 레드-블랙트리를 설명해주는 영상까지 5개의 영상을 정주행한다면 아주 이해가 잘 될 것이다 !

https://www.youtube.com/watch?v=ohrwGtqeW-I&list=PLcXyemr8ZeoR82N8uZuG9xVrFIfdnLd72&index=8

 

 

출처

https://yoongrammer.tistory.com/68

[자료구조] 트리 (Tree)

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

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

https://velog.io/@agugu95/%EC%9D%B4%EC%A7%84-%ED%8A%B8%EB%A6%AC%EC%9D%98-%EA%B7%A0%ED%98%95-RED-BALCKAVL

이진 트리의 균형과 Red-Black & AVL 트리

https://gmlwjd9405.github.io/2018/05/10/data-structure-heap.html

[자료구조] 힙(heap)이란 - Heee's Development Blog

https://velog.io/@gnwjd309/data-structure-heap

[자료구조] 힙(Heap) 이해하기