Tree (Binary Tree, BST, Heap) 종류 정리

헷갈리기 쉬운 개념들 간략하게 정리. 새로 배우는 내용 있으면 추가할 예정

 

Tree는 굉장히 매력적인 자료구조. 인덱싱이 아닌 keyword Look-up에 logN 밖에 안걸리고, 자유롭게 삽입/삭제가 가능.

트리 자료구조를 활용해서, 제한 시간 내에 못 풀법한 복잡한 문제를 풀 수 있기도 함 (ex. 세그먼트 트리)

시스템 상에서도 트리를 굉장히 많이 활용하고 있음 (ex. File directory)

꼭 잘 이해하고 넘어가자.

 

Tree

0개 이상의 다른 노드에 대한 레퍼런스 (또는 포인터)가 들어 있는 노드로 구성

* 각 노드의 부모는 반드시 하나 (children은 여러 개 가능)

 

Child를 떼서 보면 또 다른 Tree가 나오는 재귀적인 구성이므로, tree method (look-up, insert, delete)는 재귀로 구현하면 편함 (이걸 꼬아서, 면접 때 iterative tree method 구현하는 문제가 나올 수도 있음)

 

* Binary Tree

한 노드에 자식이 최대 두 개 (left, right) 까지만 있는 트리.

보통 '트리'라고 하면 binary tree를 지칭함.

 

 

이진 트리가 어떻게 생겼느냐에 따라 다른 이름이 붙는다.

이 중, complete/perfect binary tree의 경우엔 배열로 구현이 가능하기 때문에 주목해야 함.

Complete/Perfect Binary Tree를 배열로 구현

 

생각해볼만한 문제)

- Look-up / insert / delete★ 의 recursive/iterative★ method -> 둘의 차이에 대한 insight 얻기 가능

- Balancing (Pivoting)

---

Binary Search Tree (BST)

Specialized Binary Tree;

Left child <= 현재 노드가 저장하고 있는 값 <= Right child 을 만족하는 Binary tree

 

특징)

- Look-up 연산 Avg O(logN)

한 번에 절반씩의 노드를 검색 대상에서 제외하기 때문;

 

※ 주의) 노드가 한쪽에 쏠려있는 Unbalanced BST 같은 경우엔 Worst case O(N)일수도

(ex. 다음 BST에서 9 찾기 (루트 1) - 2 - 3 - 4 - 5 - 6 - 7 - 8 - 9 → Left tree가 없으므로, right를 선택해도 여전히 탐색해야 하는 노드 개수는 줄어들지 않음)

 

- 삭제 삽입 O(logN)

 

이외에도..

- 계속 left/right만 따라가면 min/max 값 구하기 가능

- 모든 노드를 정렬된 순서로 출력 (In-order traversal 활용) O(N)

- 어떤 노드 A 다음으로 높은 노드 찾기 (= A의 parent 찾기) O(logN)

---

Heap

또 다른 Specialized Binary Tree;

 

현재 노드의 값이 Children 노드 값보다 크면/작으면 max/min heap

→ Root 노드에 항상 트리의 최대값/최솟값이 저장됨; O(1)

 

힙은 우선순위(키) 정렬에, 이진탐색트리(BST)는 탐색에 강점을 지닌 자료구조

 

특징)

- 항상 최소/최대값을 필두로 데이터를 정리하기 때문에, min/max 값 찾는데 유용.

이 특성을 이용해서 sorting에도 사용 가능 (heap sort)

- 기본적으로 배열을 활용해서 complete/perfect binary tree로 구현함.

- Priority Queue 구현에 주로 사용.

사실 배열, Linked list로도 구현할 수 있는데, 삽입 혹은 삭제에 O(N) 걸리는데에 비해 heap은 항상 O(logN)이니.

 

❓ C++ std::priority_queue 보면, container가 vector 혹은 deque인데 삽입 혹은 삭제가 O(logN)이다?

> vector 혹은 deque로 heap을 만든 거라서.

 

Python의 경우 list에 heapq를 적용시켜 priority queue 구현 가능 C++은?

공부) Heap을 내가 직접 구현해볼 필요가 있을까? 언어별로 제공된 heap과 priority queue 구현 정리해보기

> Python - heapq (min heap), queue.PriorityQueue

C++ - make_heap (<algorithm>), priority_queue (max heap) 

 

 

관련 Method 정리

1. Heapify (= shiftDown) : 현재 Tree의 root가 heap 성질을 만족하도록 수정

그냥 root에 있던 수가 자기 자리 찾아갈 때 까지, 두 child중 더 큰 것과 swap 해주면 됨;

트리의 높이($h=log_2 n$)에 의존적 : O(logN)

 

❓ BuildHeap과의 차이점?

삽입과 삭제로 깨진 힙을 재구조화하기(heapify);

• heapify의 경우 기본적으로 힙을 만족하는 경우에서 삽입 또는 삭제가 발생할 때 O(logn)의 시간복잡도로 다시 힙으로 만드는 과정
• build heap은 이와 다르게 아예 힙의 조건을 만족하지 않는 배열을 힙으로 만드는 과정

 

2. BuildHeap : 수 배열 → Heap

무식한 방법 : N번 heap insert; O(NlogN)

똑똑한 방법 : Leaf 바로 위 노드들부터 차례대로 shiftDown하면 O(N)에 Heap 만들기 가능; O(N)

참고) C++ std::make_heap 

 

2. Insert / (root) Delete : O(logN)

Insert는 맨 마지막에 새 노드 추가한 뒤, 그 노드가 제 자리를 찾아가도록 아래에 위로 root까지 Heapify

 

루트 delete는, 루트를 삭제하고 맨 마지막 레벨의 맨 마지막 노드 (아마 가장 크거나 가장 작은)를 루트 자리로 옮기고,

위에서 아래로 Heapify 

 

4. HeapSort : O(NlogN)

(보통 max heap 사용해서 정렬)

max heap에서는 root가 항상 max이므로, 루트 값을 빼서 맨 마지막으로 옮기고 heap의 원소 개수 cnt를 1개 줄임.

즉, 맨 마지막에 max값이 저장되어있지만, 이 값은 정렬된 상태로, 더 이상 heap에서 원소로 취급을 안함.

이렇게 반복하다보면, 맨 뒤에서 앞으로 내림차순으로 숫자들이 정렬됨

 

정리 : root 삭제 (배열의 맨 마지막 숫자와 swap) 후, heapify down하는 과정을 반복

 

 

 

아래 두 참고자료 보고 공부.

 

참고한 자료)

👍 그림으로 알아보는 힙

그림으로 알아보는 힙정렬(Heap Sort)

[자료구조] 그림으로 알아보는 힙(Heap).mhtml

0.96MB

 

 

ratsgo.github.io/data%20structure&algorithm/2017/09/27/heapsort/ 

힙 정렬(Heap Sort) · ratsgo's blog

힙 정렬(Heap Sort) &middot; ratsgo's blog.mhtml

2.15MB

 

★ BuildHeap이 O(N)이 되는 이유 자세히 설명

stackoverflow.com/questions/9755721/how-can-building-a-heap-be-on-time-complexity

 

 

---

이외에도 많은 종류의 Tree들이 있다. 

AVL tree, RB tree, ...

ratsgo.github.io/data%20structure&algorithm/2017/10/27/avltree/

ratsgo.github.io/data%20structure&algorithm/2017/10/28/rbtree/

 

급하지 않을 때 공부하고 정리해보기!

그리고 직접 구현해보는게 가장 좋다.