트리(Tree)와 자료 구조의 힙(Heap)

자료 구조를 쓰는 이유는 결국 탐색해서 다시 사용하기 위해서이다

데이터를 넣을 때 정렬되고, 정렬된 데이터를 가져오는 것이 바로 알고리즘이다

이번에는 대표적인 자료 구조인 트리(Tree)와 힙(Heap)에 대해서 정리해보자

힙(Heap)은 무엇인가를 차곡차곡 쌓아올린 더미란 의미기 때문에 CS에서 다양한 곳에서 사용된다
여기서는 자료 구조로서의 힙(Heap)에 대해서 정리한다

트리(Tree)

수학, 특히 그래프 이론에서 회로(Cycle)가 없는 연결된 무향의 그래프를 트리라고 한다(by 나무위키)

트리 구조는 비선형적이지만 현실 세계에 있는 익숙한 구조이다

트리는 탐색기, 책의 목차 등에 주로 사용된다

용어 정리

출처 : 나무위키

노드(Node) : 트리를 구성하는 기본 원소, 값과 다음 노드에 대한 정보를 가짐

• 루트 노드(Root Node) : 최상위 노드, 트리의 시작점
• 부모 노드(Parent Node) : 루트 노드 방향으로 직접 연결된 노드
• 자식 노드(Child Node) : 루트 노드 반대방향으로 직접 연결된 노드
• 형제 노드(Siblings Node) : 같은 부모 노드를 갖는 노드들
• 리프 노드(Leaf Node) : 자식이 없는 노드

간선(Edge) : 노드와 노드를 연결하는 선

레벨(Level) : 루트 노드(level=0)부터 노드까지 연결된 간선 수의 합

높이(Height) : 가장 긴 루트 경로의 길이

차수(Degree) : 각 노드의 자식의 개수

트리 순회(Tree Traversal) : 트리의 모든 노드들을 방문하는 과정(알고리즘)

 

링크드 리스트를 예로 들면 노드는 값 + 다음 노드에 대한 정보를 가지는 트리라고도 볼 수 있다

다음 노드에 대한 정보는 보통 포인터로 구현하지만, 배열(!)로도 구현할 수 있다

트리의 종류

Binary Tree(이진 트리) : 부모 노드 밑의 자식 노드 개수(=차수, degree)를 최대 2개로 제한하는 가장 간단한 형태의 트리 구조

Binary Search Tree(이진 탐색 트리) : 이진 트리의 일종으로, 노드의 왼쪽 가지에는 노드의 값보다 작은 값들만 있고 오른쪽 가지에는 큰 값들만 있도록 구성

 

Binary Tree V.S Binary Search Tree

이진 트리는 순서는 신경 쓰지 않고 트리라는 자료 구조만 성립하지만, 이진 탐색 트리는 데이터를 삽입할 때 부모 노드의 값을 기준으로 작은 것은 왼쪽으로 큰 것은 오른쪽으로 정렬해야 한다

트리에 데이터를 삽입할 때의 부모 자식의 관계, 혹은 조건에 따라 트리의 종류가 달라진다

 

https://www.cs.usfca.edu/~galles/visualization/Algorithms.html

Data Structure Visualization

이진 탐색 트리는 일반적으로 O(log n)의 시간 복잡도를 가진다

그러나 데이터가 정렬, 혹은 역정렬된 순서로 삽입될 경우는 O(n)를 피할 수 없다

이진 트리의 종류

1. 이진 트리의 정의
   부모 노드 밑의 자식 노드 개수를 최대 2개로 제한하는 트리를 이진 트리(Binary Tree)라고 한다.
2. 이진 탐색 트리(Binary Search Tree)란?
   이진 탐색 트리(Binary Search Tree)란 이진 트리의 한 종류로, 특정 노드의 왼쪽에는 작은 값의 노드들만 있고, 오른쪽에는 큰 값의 노드들만 있도록 구성된 트리이다.
   이러한 트리 구성은 이름에서도 알 수 있듯이 이진 탐색(Binary Search)하기에 적합한 구성이다.
3. 완전 이진 트리(Complete Binary Tree)란?
   완전 이진 트리(Complete Binary Tree)는 부모 => 왼쪽 자식 => 오른쪽 자식 순으로 채워지는 트리를 뜻한다. 즉, 특정 노드가 오른쪽 자식 노드를 가지고 있으면 반드시 왼쪽 자식 노드도 가지고 있는 구성이라고도 할 수 있다.
   참고로 완전 이진 트리(Complete Binary Tree)는 포화 이진 트리(Perfect Binary Tree)의 부분집합이다.
4. 포화 이진 트리(Perfect Binary Tree)?
   포화 이진 트리(Perfect Binary Tree)는 모든 잎 노드(Leaf Node)의 레벨이 같고, 잎 노드가 아닌 노드는 모두 2개의 자식 노드를 가지는 트리를 말한다. 이진 트리는 레벨이 n일 때, 최대 n^2 – 1의 노드 수를 가질 수 있는데, 포화 이진 트리(Perfect Binary Tree)는 최대 노드 수를 모두 채운 이진 트리라고도 할 수 있다.
   참고로 포화 이진 트리(Perfect Binary Tree)는 정이진트리(Full Binary Tree)이면서 완전 이진 트리(Complete Binary Tree)의 구성을 갖는다.
5. 정 이진 트리(Full Binary Tree)란?
   정 이진 트리(Full Binary Tree)는 잎 노드가 아닌 노드의 자식 노드 수가 0개이나 2개를 가지는 형태인 트리를 말한다. 홀수 개의 자식 노드는 가질 수 없다.
6. 번외
   변질 이진 트리(Degenerate binary tree)
   각 부모 노드가 오직 한 개의 연관 자식 노드를 갖는 트리. 구조면에서나 성능 면에서 연결 리스트와 그다지 차이가 없다고 할 수 있다.
   균형 이진 트리(Balanced binary tree)
   왼쪽 자식, 오른쪽 자식 노드의 개수가 지나치게 한쪽으로 치우치지 않은 트리 구조를 말한다. 균형 잡힌 트리를 구성할 경우, 트리가 한 쪽으로 치우치면서 시간 복잡도가 악화되는 상황을 방지할 수 있다.

완전 이진 트리와 힙

Complete binary tree = Heap
완전 이진 트리를 줄여서 힙이라고 부른다

마지막 레벨 외의 모든 노드는 가득 차 있어야 한다

마지막 레벨 노드의 경우는 왼쪽은 반드시 채워져야 한다

완전 이진 트리에서 각 노드와 자식 노드의 인덱스의 관계는 다음과 같다

• 부모 노드 : n
• 왼쪽 자식 노드 : 2n + 1
• 오른쪽 자식 노드 : 2n + 2

Min Heap과 Max Heap

트리 - 검색을 위해 사용하는 자료 구조

선형 구조보다 이점은?

데이터가 많을 때 다음과 같은 상황에서 효과적으로 사용된다

1. 특정 값을 찾아라

2. 몇 번째 값을 찾아라

3. 가장 큰(작은) 값을 찾아라

트리를 빌드하는 비용은 필요하지만 탐색의 비용은 줄어든다

힙 자료 구조의 구현

참고 사이트
https://www.geeksforgeeks.org/building-heap-from-array/?ref=rp 

Building Heap from Array - GeeksforGeeks

// To heapify a subtree rooted with node i which is
// an index in arr[]. N is size of heap
void heapify(int arr[], int n, int i)
{
    int largest = i; // Initialize largest as root
    int l = 2 * i + 1; // left = 2*i + 1
    int r = 2 * i + 2; // right = 2*i + 2
 
    // If left child is larger than root
    if (l < n && arr[l] > arr[largest])
        largest = l;
 
    // If right child is larger than largest so far
    if (r < n && arr[r] > arr[largest])
        largest = r;
 
    // If largest is not root
    if (largest != i) {
        swap(arr[i], arr[largest]);
 
        // Recursively heapify the affected sub-tree
        heapify(arr, n, largest);
    }
}

// Function to build a Max-Heap from the given array
void buildHeap(int arr[], int n)
{
    // Index of last non-leaf node
    int startIdx = (n / 2) - 1;
 
    // Perform reverse level order traversal
    // from last non-leaf node and heapify
    // each node
    for (int i = startIdx; i >= 0; i--) {
        heapify(arr, n, i);
    }
}

C++에서 제공하는 STL의 priority_queue도 Max Heap으로 구현되어 있다

 

SSS