정의

사이클이 없는 연결 그래프

루트

리프노드

지름(높이)
트리의 경로 중 가장 긴 경로

조상
자기 자신을 포함하여 상위에 있는 노드들

자손
자기 자신을 포함하여 하위에 있는 노드들

이진 트리
자식을 최대 2개만 가지고 있는 트리
부모 노드가 n인 경우 자식노드는 2n, 2n+1
힙, 세그먼트 트리 등에 사용

완전 이진 트리
리프노드를 제외한 노드의 자식의 수는 모두 2인 트리
리프노드의 자식 수는 0
모든 리프노드의 depth(h)가 동일
노드수 = 2^h-1개

저장

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

탐색

그래프 탐색 방법과 동일

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

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

기타

힙

완전 이진 트리의 일종으로 최댓값이나 최솟값을 빠르게 찾기 위한 자료구조
삽입, 삭제 시 O(LogN)의 시간이 걸림

최대 힙(max heap)
부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리
부모 노드 값 >= 자식 노드 값

최소 힙(min heap)
부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리
부모 노드 값 <= 자식 노드 값

우선순위 큐

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

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

이진 트리이면서, 다음과 같은 성질을 가지고 있음

• 루트 노드의 왼쪽 서브트리의 모든 key는 루트 노드의 key보다 작음
• 루트 노드의 오른쪽 서브트리의 모든 key는 루트 노드의 key보다 크거나 같음
• 각 서브트리 또한 이진 탐색 트리임