Binary Tree, BST, Binary Heap

Tree

• 비선형 자료구조

• 계층적 관계(Hierarchical Relationship)을 표현하는 자료구조

트리 관련 요소(용어)

• Node (노드) : 트리를 구성하고 있는 각각의 요소를 의미

• Edge (간선) : 트리를 구성하기 위해 노드와 노드를 연결하는 선을 의미

• Root Node (루트 노드) : 트리 구조에서 최상위에 있는 노드를 의미

• Terminal Node ( = leaf Node, 단말 노드) : 하위에 다른 노드가 연결되어 있지 않은 노드를 의미

• Internal Node (내부노드, 비단말 노드) : 단말 노드를 제외한 모든 노드로 루트 노드를 포함

Binary Tree (이진 트리)

루트 노드를 중심으로 두 개의 서브 트리(큰 트리에 속하는 작은 트리)로 나뉘어 지는데, 이 과정에서 나뉘어진 두 서브 트리들 또한 모두 이진이여야 함

트리에서는 각 층별로 숫자를 매겨서 이를 트리의 Level(레벨)이라고 한다. 

레벨의 값은 0 부터 시작하고 따라서 루트 노트의 레벨은 0 이다. 

그리고 트리의 최고 레벨을 가리켜 해당 트리의 height(높이)라고 한다.

Perfect Binary Tree (포화 이진 트리), Complete Binary Tree (완전 이진 트리), Full Binary Tree (정 이진 트리)

모든 레벨이 꽉 찬 이진 트리를 가리켜 포화 이진 트리라고 한다

그리고 위에서 아래로, 왼쪽에서 오른쪽으로 순서대로 차곡차곡 채워진 이진 트리를 가리켜 완전 이진 트리라고 한다

모든 노드가 0개 혹은 2개의 자식 노드만을 갖는 이진 트리를 가리켜 정 이진 트리라고 한다.

BST (Binary Search Tree)

이진 탐색 트리는 이진 트리의 일종이다. 단 이진 탐색 트리에는 데이터를 저장하는 규칙이 있다

규칙 1. 이진 탐색 트리의 노드에 저장된 키는 유일하다.
규칙 2. 부모의 키가 왼쪽 자식 노드의 키보다 크다.
규칙 3. 부모의 키가 오른쪽 자식 노드의 키보다 작다.
규칙 4. 왼쪽과 오른쪽 서브트리도 이진 탐색 트리이다.

이진 탐색 트리의 탐색 연산은 O(log n)의 시간 복잡도를 갖는다.

정확히 말하면 O(h)라고 표현하는 것이 맞다. 트리의 높이를 하나씩 더해갈수록 추가할 수 있는 노드의 수가 두 배씩 증가하기 때문이다.

하지만 이러한 이진 탐색 트리는 Skewed Tree(편향 트리)가 될 수 있다.

저장 순서에 따라 계속 한 쪽으로만 노드가 추가되는 경우가 발생하기 때문이다.

이럴 경우 성능에 영향을 미치게 되며, 탐색의 Worst Case 가 되고 시간 복잡도는 O(n)이 된다.

이를 해결하기 위해 Rebalancing 기법이 등장하였다. 균형을 잡기 위한 트리 구조의 재조정을 Rebalancing이라 한다.

Binary Heap

자료구조의 일종으로 Tree 의 형식을 하고 있으며, Tree 중에서도 배열에 기반한 Complete Binary Tree이다

배열에 트리의 값들을 넣어줄 때, 0 번째는 건너뛰고 1 번 index 부터 루트노드가 시작된다.

이는 노드의 고유번호 값과 배열의 index 를 일치시켜 혼동을 줄이기 위함이다

힙(Heap)에는 최대힙(max heap), 최소힙(min heap) 두 종류가 있다.

Max Heap이란, 각 노드의 값이 해당 children 의 값보다 크거나 같은 complete binary tree를 말한다. ( Min Heap 은 그 반대이다.)

Max Heap에서는 Root node 에 있는 값이 제일 크므로, 최대값을 찾는데 소요되는 연산의 time complexity 이 O(1)이다. 

그리고 complete binary tree이기 때문에 배열을 사용하여 효율적으로 관리할 수 있다. 

(즉, random access 가 가능하다. Min heap 에서는 최소값을 찾는데 소요되는 연산의 time complexity 가 O(1)이다.) 

하지만 heap 의 구조를 계속 유지하기 위해서는 제거된 루트 노드를 대체할 다른 노드가 필요하다. 

여기서 heap 은 맨 마지막 노드를 루트 노드로 대체시킨 후, 다시 heapify 과정을 거쳐 heap 구조를 유지한다. 

이런 경우에는 결국 O(log n)의 시간복잡도로 최대값 또는 최소값에 접근할 수 있게 된다.

출처 : https://github.com/JaeYeopHan/Interview_Question_for_Beginner/tree/master/DataStructure