트리, 힙, 이진탐색트리

정의

• 사이클이 없는 연결 그래프
• 루트
• 리프노드
• 지름(높이): 트리의 경로 중 가장 긴 경로
• 조상: 자기 자신을 포함하여 상위에 있는 노드들
• 자손: 자기 자신을 포함하여 하위에 있는 노드들

저장

그래프 저장 방법과 동일
또는 부모만 저장하는 방법 사용

탐색

그래프 탐색 방법과 동일

DFS는 루트를 언제 방문하는지에 따라 3가지로 나뉨(재귀 호출 시점 차이)

• 프리오더 (노드->왼쪽자식->오른쪽자식) : 그래프 풀 때 주로 사용
• 인오더 (왼쪽자식->노드->오른쪽자식) : 거의 사용 X (BST에서 사용)
• 포스트오더 (왼쪽자식->오른쪽자식->노드) : 자식 처리 한 뒤 그 값을 이용해 부모 값 처리하는 경우가 많음

이진 트리

• 자식을 최대 2개만 가지고 있는 트리
• 부모 노드가 n인 경우 자식노드는 2n, 2n+1
• 힙, 세그먼트 트리 등에 사용
• 완전 이진 트리
  • 리프노드를 제외한 노드의 자식의 수는 모두 2인 트리
  • 리프노드의 자식 수는 0
  • 모든 리프노드의 depth(h)가 동일
  • 노드수 = 2^h-1개
• 이진탐색트리(이진검색트리, Binary Search Tree, BST)
  • BST를 인오더순회하면 항상 정렬된 상태 리턴
  • 이진 트리이면서, 다음과 같은 성질을 가지고 있음
    • 루트 노드의 왼쪽 서브트리의 모든 key는 루트 노드의 key보다 작음
    • 루트 노드의 오른쪽 서브트리의 모든 key는 루트 노드의 key보다 크거나 같음
    • 각 서브트리 또한 이진 탐색 트리임
  • 삽입, 삭제, 검색 모두 O(h)
  • 아무 항목이나 삭제 가능

힙

• 완전 이진 트리의 일종으로 최댓값이나 최솟값을 빠르게 찾기 위한 자료구조
• 삽입, 삭제 시 O(logN)의 시간이 걸림
• 최대 또는 최소만 삭제 가능
• 검색 X
• 최대 힙(max heap)
  • 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리
  • 부모 노드 값 >= 자식 노드 값
• 최소 힙(min heap)
  • 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리
  • 부모 노드 값 <= 자식 노드 값

우선순위 큐

• 현재 우선순위 큐 안에서 우선순위가 가장 높은 데이터가 먼저 삭제 됨