[면접 준비] 이진 트리, 이진 검색 트리, 힙의 차이점 / Binary Heap, Red-Black Tree, B+ Tree

학습 키워드: binary tree, binary search tree, heap, binary heap, red-black tree, b+ tree

 

2024-08-12 면접 카타 질문

이진트리, 이진 검색트리, 힙이 각각 무엇인지 설명하고, 차이점을 설명해주세요:

 이진 트리(Binary Tree)는 트리 구조에서 한 개의 노드가 항상 두 개 이하의 자식 노드를 가지는 구조를 말합니다. 일반적으로 부모 노드가 자식 노드로의 reference만 가지고 있는 방향성 그래프의 형태지만, 자식 노드가 부모 노드를 저장하는 경우는 무방향 그래프가 될 수도 있습니다.

 

 이진 검색 트리(Binary Search Tree, BST)는 이진 트리 구조에서 모든 노드의 두 개의 자식 노드 중 왼쪽에는 현재 노드보다 작은 값, 오른쪽에는 큰 값을 가지도록 배치된 구조를 말합니다. 이진 트리와는 다르게 BST에는 전순서(Total Order)가 있으며, 이는 BST의 모든 값이 서로 비교가 가능하며, 노드 n의 왼쪽 서브트리에는 n보다 작은 값만 있어야하고, 오른쪽 서브트리에는 n보다 큰 값만 있어야 함을 의미합니다.

 

 힙(Heap)은 최댓값과 최솟값을 빠르게 찾기 위해 고안된, 힙 속성(heap property)을 만족하는 트리 기반의 자료 구조를 말합니다. 힙 속성이란 힙의 특정 노드 P가 노드 C의 부모 노드라면, P 노드의 값은 C 노드의 값보다 크거나 같다(max heap의 경우이며, min heap은 작거나 같다)는 조건을 만족하는 것을 의미합니다. 이진 검색 트리에서는 형제 노드 간에도 대소관계가 성립하지만, 힙의 경우 부모 자식 노드 간의 대소관계만 성립합니다. 최댓값이나 최솟값이 root 노드에 존재한다는 특징 때문에 priority queue의 구현에 사용됩니다.

 

 이진 힙(Binary Heap)은 힙 구조 중 가장 많이 쓰이는 완전 이진 트리(Complete Binary Tree) 기반의 자료 구조입니다. 완전 이진 트리는 최하단의 leaf 노드를 제외한 모든 노드가 2개의 자식 노드를 온전하게 갖추고 있는 구조를 말하며, 리프 노드의 경우 가능한 한 왼쪽 자식 노드의 자리를 채웁니다.

 

 레드-블랙 트리(red-black tree)는 자가 균형(self-balancing) 이진 탐색 트리 형태의 자료 구조입니다. 자가 균형 이진 탐색 트리는 노드의 삽입과 삭제 시 트리의 높이를 최소로 유지하는 구조를 말합니다. 레드-블랙 트리의 특징은 다음과 같습니다.

 1. 모든 노드는 레드 혹은 블랙입니다. 

 2. 루트 노드는 블랙입니다.

 3. 모든 NIL 노드는 블랙입니다.

 4. 레드 노드는 레드 노드의 자식일 수 없습니다.

 5. 특정 노드에서 그 하위 리프 노드까지 가는 모든 경로에는 리프 노드 제외 같은 수의 블랙 노드가 있습니다.

 

 B+ 트리(B+ Tree)는 Key 값으로 정렬된 이진 트리에서 leaf 노드에만 value를 저장하는 구조입니다. Key 값은 유일해야하며, 중복을 허용하지 않습니다. 리프노드끼리는 연결 리스트의 형태로 이어져 있습니다.

 

 

--