트리

트리

그래프의 한 종류로 사이클이 없는 계층적 관계를 표현할 수 있는 비선형 자료구조

이진 트리

• 정의

자식 노드가 최대 2개인 트리

• 종류

1. 완전 이진 트리
   • 트리의 마지막 레벨을 제외한 모든 레벨에 노드가 채워져 있으며 마지막 레벨은 왼쪽에서부터 오른쪽으로 노드가 채워져 있는 이진 트리
2. 포화 이진 트리
   • 트리 마지막 레벨까지 노드가 모두 채워져 있는 이진 트리
3. 이진 탐색 트리
   • 왼쪽 서브 트리는 해당 노드의 값보다 작은 값을 가진 노드로 구성되고, 오른쪽 서브 트리는 해당 노드의 값보다 큰 값을 가진 노드로 구성된 트리

이진 트리 순회

1. 전위 순회(Preorder Traversal)

   • root → left → right

   

   • 1 2 4 8 9 5 10 11 3 6 12 13 7 14 15

2. 중위 순회(Inorder Traversal)

   • left → root → right

   

3. 후위 순회(Postorder Traversal)

   • left → right → root

   

우선순위 큐

우선순위 큐는 우선순위가 높은 데이터가 먼저 나오는 자료구조

• 구현 방식

1. 배열
2. 연결 리스트
3. 완전 이진 트리 (힙)

• 구현 방식에 따른 시간 복잡도

  구현 방법	삽입	삭제
  배열(sorted)	O(n)	O(1)
  연결 리스트(sorted linked list)	O(n)	O(1)
  힙(heap)	O(logN)	O(logN)

힙

완전 이진 트리. 최댓값 또는 최솟값을 빠르게 찾을 수 있는 자료구조

• 종류
  1. 최대힙(Max heap)
     • 부모 노드의 값이 자식 노드의 값보다 크거나 같은 완전 이진 트리
  2. 최소힙(Min heap)
     • 부모 노드의 값이 자식 노드의 값보다 작거나 같은 완전 이진 트리
• 연산
  1. 삽입 연산
     • 힙의 맨 끝단에서 이루어짐. 삽입 후 부모 노드와 우선순위(최댓값 또는 최솟값)을 비교해 부모 노드보다 우선순위가 높으면 위치를 바꾸면서 루트노드까지 비교
  2. 삭제 연산
     • 힙에서 우선순위가 가장 높은 노드를 삭제. 즉 루트노드 삭제. 이후 루트 노드 자리에 힙의 마지막 노드를 옮긴 후 힙을 재정렬한다