이진트리, 이진 검색트리, 힙

https://javacpp.tistory.com/128

그래프(Graph)와 트리(Tree)

여기서 트리구조를 알아봤고 오늘은 이진트리다.

 

이진 트리 (binary tree)

이진 트리(binary tree)는 각각의 노드가 최대 두 개의 자식 노드를 가지는 트리 자료 구조로(그래서 이름이 이진트리다), 자식 노드를 각각 왼쪽 자식 노드와 오른쪽 자식 노드라고 한다.

 

트리와 이진 트리의 차이점

• 이진 트리의 모든 노드는 차수가 2이하이다. 즉, 자식 노드의 개수가 2 이하이다. 반면 일반 트리는 자식 노드의 개수에 제한이 없다.
• 이진 트리는 노드를 하나도 갖지 않을 수도 있다.
• 이진 트리는 서브 트리 간에 순서가 존재한다. 따라서 왼쪽 서브 트리와 오른쪽 서브 트리를 구분한다.

이진 트리의 종류

정 이진트리

정 이진 트리(Full Binary Tree)는 모든 내부 노드가 두 개의 자식 노드를 가지며, 모든 리프 노드(마지막 단계의 노드)가 같은 깊이에 있는 이진 트리이다. 따라서, 모든 노드의 차수가 2인 이진 트리라고도 할 수 있다.

포화 이진 트리

포화 이진 트리(Perfect Binary Tree)는 용어 그대로 트리의 각 레벨에 노드가 꽉 찬 이진 트리이다. 높이가 kk인 포화 이진 트리는 정확하게 2k−12k−1개의 노드를 가진다.

완전 이진 트리

완전 이진 트리(Complete Binary Tree)는 높이가 kk일 때 레벨 1부터 k−1k−1까지는 노드가 모두 채워져 있고 kk레벨에서는 왼쪽부터 오른쪽으로 노드가 순서대로 채워져 있는 이진 트리이다. 마지막 레벨에서는 노드가 꽉 차 있지 않아도 되지만 중간에 빈 노드가 있어서는 안 된다.

 

포화 이진 트리는 항상 완전 이진 트리이지만 그 역은 항상 성립하지 않는다.

 

 

이진 탐색 트리

이진 탐색 트리(binary search tree)는 이진 트리 기반의 탐색을 위한 자료구조다.

이진 탐색 트리는 정렬된 트리로, 노드의 왼쪽 서브 트리에는 그 노드의 값보다 작은 값들을 지닌 노드들로 이뤄져 있고 오른쪽 서브 트리에는 노드의 값과 같거나 큰 값들을 지닌 노드들로 이루어져 있는 트리다. 따라서 찾고자 하는 값이 루트 노드의 값과 비교하여 루트 노드보다 작으면 찾고자 하는 값은 왼쪽 서브 트리에 있고 루트 노드보다 크면 오른쪽 서브 트리에 있음을 쉽게 알 수 있다.

즉, 이진 탐색 트리는 왼쪽 자식 노드 < 부모 노드 < 오른쪽 자식 노드가 성립되며 중복되는 값을 허용하지 않는다.

 

힙(Heap)

데이터에서 최댓값과 최솟값을 빠르게 찾기 위해 고안된 완전 이진 트리(Complete Binary Tree)

힙을 사용하는 이유

최솟값이나 최댓값을 찾기 위해 배열을 사용하면 Ο(n)만큼 시간이 걸린다.
하지만 힙을 사용하면 O(logn)만큼 소요되므로, 배열을 사용할 때보다 빠르게 최솟값과 최댓값을 구할 수 있다.

우선순위 큐와 같이 최댓값 또는 최솟값을 빠르게 찾아야하는 알고리즘 등에 활용된다.

 

정리하자면, 힙은 다음 조건을 만족하는 자료구조이다.

1. 힙은 최대힙(Max heap)과 최소힙(Min heap)으로 나뉘어진다. 최대힙은 자식 노드보다 부모 노드의 값이 크고, 최소힙은 자식 노드보다 부모 노드의 값이 작다.
2. 노드가 왼쪽부터 채워지는 완전 이진 트리 형태를 가진다.
3. 중복을 허용한다.

이진 탐색 트리와 힙의 차이점

• (최대힙의 경우) 힙은 각 노드의 값이 자식 노드보다 크거나 같다.
• 이진 탐색 트리는 각 노드의 왼쪽 자식은 더 작은 값으로, 오른쪽 자식은 더 큰 값으로 이루어져있다.
  왼쪽 자식 노드 < 부모 노드 < 오른쪽 자식 노드
• 힙은 왼쪽 노드의 값이 크든 오른쪽 노드의 값이 크든 상관 없다.
• 힙은 최대/최소 검색을, 이진 탐색 트리는 탐색을 위한 구조이다.