트리(Tree), 힙(Heap)

소개

• 트리: 계층 구조의 데이터를 쉽게 표현 가능
• 힙: 최솟값과 최댓값을 쉽게 뽑을 수 있다. ex) Min Heap, Max Heap

 

트리(Tree)

스택(Stack), 큐(Queue)는 선형 구조인 반면, 

(선형 구조란 자료를 구성하고 있는 데이터들이 순차적으로 나열시킨 형태를 의미)

트리는 비선형 구조. 선형 구조와는 다르게 데이터가 계층적 혹은 망으로 구성되어 있다. 

형태뿐만 아니라 용도에서도 차이점이 있는데,

선형 구조는 자료를 저장하고 꺼낼 때 좋고 비선형 구조는 표현에 초점이 맞춰져 있다. 

 

트리를 다루는 용어

• Node: 트리에서 데이터를 저장하는 기본 요소
• Root Node: 트리 맨 위에 있는 노드
• Level: 최상위 노드를 Level 0으로 하였을 때, 하위 Branch로 연결된 노드의 깊이를 나타냄
• Parent Node: 어떤 노드의 상위 레벨에 연결된 노드
• Child Node: 어떤 노드의 하위 레벨에 연결된 노드
• Leaf Node(Terminal Node): Child Node가 하나도 없는 노드
• Sibling: 동일한 Parent Node를 가진 노드
• Depth: 트리에서 Node가 가질 수 있는 최대 Level

 

트리의 종류

• 이진 트리(Binary Tree)
  • 각 노드가 최대 두 개의 자식을 가진다
  • 하위의 노드가 4~5개 이럴 수 없이 무조건 0, 1, 2개만 있어야 한다.
• 완전 이진 트리(Complete Binary Tree)
  • 노드를 삽입할 때 최하단 왼쪽 노드부터 차례대로 삽입해야 한다
• 이진 탐색 트리
• 균형 트리(AVL 트리, red-black 트리)
• 이진 힙(최대힙, 최소힙) 등 

      o      Level 0 
    o o o    Level 1
   o  o  o   Level 2 # 이진 트리(X)

      o      Level 0
    o   o    Level 1
     o o     Level 2  # -> 이진 트리 O 완전 이진 트리 X

      o      Level 0
    o   o    Level 1
   o o o     Level 2  # -> 이진 트리 O 완전 이진 트리 O

 

트리의 표현

트리 구조를 표현하는 방법으로는

직접 클래스를 구현해서 사용하는 방법이 있고

완전 이진 트리를 쓰면 왼쪽부터 데이터가 쌓이기 때문에 이를 순서대로 쌓는 방법을 통해

배열로 표현하는 방법이 있다. 

 

완전 이진 트리를 배열로 구현해보기

트리를 구현할 때는 편의성을 위해 0번째 인덱스는 사용되지 않는다. 그래서 None 값을 배열에 넣고 시작한다. 

      8		-> Level 0
    6   3	-> Level 1
   4 2 5	-> Level 2

위와 같은 트리가 있을 때, 배열로 나타내면 [None, 8, 6, 3, 4, 2, 5]가 된다.

 

또한, 이렇게 배열을 이용하면 간단한 공식을 통해 현재 인덱스에서 부모와 자식 노드의 인덱스가 어떤건지도 알 수 있다.

# 부모 인덱스
현재 인덱스 // 2
# 왼쪽 자식의 인덱스
현재 인덱스 * 2
# 오른쪽 자식의 인덱스
현재 인덱스 * 2 + 1

 

완전 이진 트리의 높이

트리의 높이(Height)는 루트 노드부터 가장 아래 리프 노드까지의 길이란걸 알 수 있다. 

 

Q1. 그러면 각 레벨에 노드가 꽉 차 있을 경우 레벨에 노드가 총 몇 개 있을까?

      1            Level 0 -> 1개 = 2^0개
    2   3          Level 1 -> 2개 = 2^1개
   4 5 6 7         Level 2 -> 4개 = 2^2개
 8 9....... 14 15  Level 3 -> 8개 = 2^3개 ...
                   Level k -> 2^k 개

위 예시를 통해 높이가 k라고 한다면 각 레벨에 최대로 들어갈 수 있는 노드의 개수는 2^k인 것을 알 수 있다. 

 

Q2. 만약 높이가 h인데 모든 노드가 꽉 찬 완전 이진 트리라면 모든 노드의 개수는 몇개일까?

1 + 2^1 + 2^2 + 2^3 + ... + 2^h가 되겠다.

이를 수식으로 표현하면 다음과 같다.

2^(h+1) - 1 

 

근데 아래 부분이 이해안되서 일단 사진으로 남긴다.

이해가 되질 않는다..

시그마 공식으로 높이 h인 모든 노드의 개수가 2^(h+1)-1이라는데

왜 다음 줄에는 높이가 h일 때 최대 노드의 개수가 2(h+1)-1로 바뀌는질 모르겠다..

 

일단 완전 이진 트리는 높이를 최대로 해봤자 O(log(N))의 시간 복잡도를 가지는구나 라고 외우고 넘어가야 할 것 같다.

 

힙(Heap)

힙은 데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리(Complete Binary Tree)다.

부모의 값이 항상 자식의 값보다 크기 때문에 최대의 값들을 빠르게 구할 수 있는 것이다. 

그리고 최댓값이 맨 위인 힙을 Max Heap, 최솟값이 맨 위인 힙을 Min Heap 이라고 한다. 

참고로 Max Heap은 원소를 최댓값에 빠르게 추가하거나 삭제하는 문제에서 사용하면 좋은 자료구조인 것을 알아두면 좋다.

      8      Level 0
    6   3    Level 1
     2 1     Level 2  # -> 이진 트리 O 완전 이진 트리 X 이므로 힙 X

      8      Level 0
    6   3    Level 1  # -> 이진 트리 O 완전 이진 트리 O 
   4 2 1     Level 2  # & 모든 부모 노드의 값이 자식 노드보다 크니까 힙 O


      8      Level 0
    6   3    Level 1  # -> 이진 트리 O 완전 이진 트리 O 
   4 2 5     Level 2  # But, 모든 부모 노드의 값이 자식 노드보다 크지 않아서 힙 X

 

 

코드 구현

Max Heap에 노드 추가

Max Heap에서 원소를 추가할 때는 다음과 같은 과정을 거치면 된다.

1. 원소를 맨 마지막에 넣는다.
2. 부모 노드와 비교한다. 만약 더 클 경우 자리를 바꾼다.
3. 부모 노드보다 작거나 가장 위에 도달할 때까지 위 과정을 반복한다. 

class MaxHeap:
    def __init__(self):
        self.items = [None]

    def insert(self, value):
        self.items.append(value)
        # 새로 들어온 인덱스를 new_index에 넣어준다.
        new_index = len(self.items) - 1

        while new_index > 1: # root node의 인덱스가 1이므로 1이 되면 while문을 멈춘다. 
            parent_index = new_index // 2 # 현재 인덱스 // 2는 부모 노드의 인덱스
            if self.items[new_index] > self.items[parent_index]:
                self.items[new_index], self.items[parent_index] = self.items[parent_index], self.items[new_index]
                new_index = parent_index
            else:
                break
        return

max_heap = MaxHeap()
max_heap.insert(3)
max_heap.insert(4)
max_heap.insert(2)
max_heap.insert(9)
print(max_heap.items)  # [None, 9, 4, 2, 3] 가 출력되어야 한다.

시간 복잡도 분석

추가되는 원소가 배열 내 제일 큰 수일 경우 원소를 맨 밑에 넣어서 꼭대기까지 비교하며 올리고 있다. 

완전 이진트리의 최대 높이는 O(log(N))이므로 반복하는 최대 횟수도 O(log(N))이다. 

즉, Max Heap의 원소 추가는 O(log(N)) 만큼의 시간 복잡도를 가진다. 

 

Max Heap에서 노드 제거

Max Heap에서 원소를 삭제하는 방법은 최댓값 즉, 루트 노드를 삭제하는 것이다.

스택과 같이 맨 위에 있는 원소만 제거할 수 있고 다른 위치의 노드를 삭제할 수 없다. 

또한 Max Heap에 원소를 추가했던 것과 마찬가지로 원소를 삭제할 때도 규칙이 지켜져야 한다. 

따라서 아래와 같은 과정을 거친다. 

1. 루트 노드와 맨 뒤에 있는 원소를 교체한다. 
2. 맨 뒤에 있는 원소(원래 루트 노드)를 제거한다. ex) .pop()
3. 변경된 노드와 자식 노드들을 비교한다.
4. 두 자식 중 더 큰 자식과 비교해서 자식이 더 크다면 자리를 바꾼다.
5. 부모가 더 크거나 가장 바닥에 도달할 때까지 위 과정을 반복한다. 
6. 마지막으로 제거한 원래 루트 노드를 반환한다. 

class MaxHeap:
    def __init__(self):
        self.items = [None, 8, 6, 7, 2, 5, 4]
        # self.items = [None, 10, 6, 7, 1, 2, 5]

    def delete(self):
        # 루트 노드와 맨 끝에 있는 노드 교체
        self.items[1], self.items[-1] = self.items[-1], self.items[1]
        prev_max = self.items.pop() # 제거할 값을 리턴해야 하므로 따로 저장해둔다.

        curr_i = 1

        while curr_i <= len(self.items)-1:
            left_i = curr_i * 2
            right_i = curr_i * 2 + 1

            # 비교하며 바로 바꾸는게 아니라 세 값 중 제일 큰 값만 찾는 것이므로
            # 큰 값에 대한 인덱스를 max_i 로 저장해둔다.
            max_i = curr_i
            if left_i <= len(self.items)-1 and self.items[left_i] > self.items[max_i]:
                max_i = left_i
            if right_i <= len(self.items) - 1 and self.items[right_i] > self.items[max_i]:
                max_i = right_i
            if max_i == curr_i: # 맥스 값이 최상단 값이면 while문을 더 이상 돌 필요가 없다.
                break

            self.items[curr_i], self.items[max_i] = self.items[max_i], self.items[curr_i]
            curr_i = max_i

        return prev_max

max_heap = MaxHeap()
print(max_heap.items)  # [None, 8, 6, 7, 2, 5, 4]
print(max_heap.delete())  # 8 을 반환해야함
print(max_heap.items)  # [None, 7, 6, 4, 2, 5]

시간 복잡도 분석

Max Heap에서 원소를 삭제하는 것도 결국 원소가 가장 낮은 수면 맨 위에 올려서부터 바닥까지 비교하며 내려와야 한다. 

완전 이진트리의 최대 높이는 O(log(N))이므로 반복하는 최대 횟수도 O(log(N))이다. 

즉, Max Heap의 원소 삭제는 O(log(N)) 만큼의 시간 복잡도를 가졌다고 분석할 수 있다.