트리와 힙 (파이썬 네이티브 코드로 구현하기)

트리란?

뿌리와 가지로 구성되어 거꾸로 세워놓은 나무처럼 보이는 계층형 비선형 자료 구조.

트리는 비선형 구조다.
비선형 구조는 선형구조와는 다르게 데이터가 계층적 혹은 망으로 구성되어있다.
선형구조와 비선형구조의 차이점은 형태뿐만 아니라 용도에서도 차이점이 많다.

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

아래 폴더 구조가 대표적인 트리의 형태다

트리의 용어

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

트리의 종류는 이진 트리, 이진 탐색 트리, 균형 트리(AVL트리, red-black 트리),
이진 힙(최대 힙 최소 힙)등 다양하지만
이번 정리에선 이진 트리와 완전 이진 트리만 알아볼 예정

이진 트리(Binary Tree)의 특징은 바로
각 노드가 최대 두개의 자식을 가진다는 것
막 하위의 노드가 4~5개 일 수 없고 무조건 0, 1, 2 개만 있어야 한다.

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

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

완전 이진 트리(Complete Binary Tree)의 특징은 바로
노드를 삽입할 때 최하단 왼쪽 노드부터 차례대로 삽입해야 한다는 것

      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 값을 배열에 넣고 시작한다 [None]

      8      Level 0 -> [None, 8] 첫번째 레벨의 8을 넣고,
    6   3    Level 1 -> [None, 8, 6, 3] 다음 레벨인 6, 3을 넣고
   4 2 5     Level 2 -> [None, 8, 6, 3, 4, 2, 5] 다음 레벨인 4, 2, 5를 넣으면 된다!

자 그러면, [None, 8, 6, 3, 4, 2, 5] 라는 배열이 되는데
다시 역으로 이 배열을 활용해서 트리 구조를 분석해보자.
다음과 같은 방법으로 트리 구조를 파악할 수 있다.

1. 현재 인덱스 * 2 -> 왼쪽 자식의 인덱스
2. 현재 인덱스 * 2 + 1 -> 오른쪽 자식의 인덱스
3. 현재 인덱스 // 2 -> 부모의 인덱스

예를 들어서 1번째 인덱스인 8의 왼쪽 자식은 6, 오른쪽 자식은 3.
그러면 1 * 2 = 2번째 인덱스! 6!
그러면 1 * 2 + 1 = 3번째 인덱스! 3!
부모를 찾아보면, 3 // 2 = 1번째 인덱스 8 이므로 부모를 찾을 수 있다.

이를 다시 생각해보면
[None, 8, 6, 3, 4, 2, 5] 는
8 밑에 6, 3 이 있고, 6, 3 밑에 4, 2, 5가 있는 완전 이진 트리구나! 생각할 수 있다.

트리의 높이(Height)는, 루트 노드부터 가장 아래 리프 노드까지의 길이다
예를 들어 다음과 같은 트리의 높이는 2라고 할 수 있다.

      o      Level 0  # 루트 노드
    o   o    Level 1
   o o o     Level 2  # 가장 아래 리프 노드

이 트리의 높이는 ? 2 - 0 = 2!

그러면 한 번, 각 레벨에 노드가 꽉~~ 차 있으면 몇 개가 있는지 잠깐 생각해보자.

아래 예시를 보면, 레벨을 k라고 한다면
각 레벨에 최대로 들어갈 수 있는 노드의 개수는
2^k 개수 임을 알 수 있다.

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

만약 높이가 h 인데 모든 노드가 꽉 차 있는 완전 이진 트리라면
모든 노드의 개수는 2^(h+1) -1개다

최대 노드의 개수가 N이라면 h는
2^(h+1)-1 = N
h = log_2(N+1) -1 다

즉 완전 이진 트리 노드의 개수가 N일 때 최대 높이가 log_2(N+1) - 1이므로
이진트리의 최대 높이는 O(log(N))이라 생각하면 된다.

힙이란?

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

항상 최대의 값 혹은 최소의 값들이 필요한 연산이 있다면 힙을 쓰면된다.

힙은 항상 큰 값이 상위 레벨에 있고 작은 값이 하위 레벨이 있도록 하는 자료구조다.

즉 부모 노드의 값이 항상 자식 노드의 값보다 항상 커야한다. 그러면 가장 큰 값은 모든 자식보다 커야하기때문에

가장 위로 가있으므로 최대 값을 가져올때 트리의 맨 꼭대기(트리 노드)만 가져오면 되므로 빠르게 가져올 수 있다.

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

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


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

최댓값이 맨 위인 힙을 Max 힙

최소값이 맨 위인 힙을 Min 힙이라고 한다.

맥스 힙에 원소 추가

힙은 항상 큰 값이 상위에 있고 작은 값이 하위에 있어야한다.

따라서 원소를 추가하거나 삭제할때도 위의 규칙이 지켜져야 한다.

원소를 추가하는 과정

원소를 맨 마지막에 넣는다.
부모 노드와 비교한다. 만약 더 크다면 자리를 바꿈
부모 노드보다 작거나 가장 위에 도달하지 않을때까지 2.과정을 반복

이 맥스 힙에서 9를 추가
      8      Level 0
    6   3    Level 1  
   4 2 1     Level 2 

1. 맨 마지막에 원소를 넣는다.

      8      Level 0
    6   3    Level 1  
   4 2 1 9   Level 2 

2-1. 부모 노드와 비교. 3보다 9가 더 크니 둘의 자리를 변경.

      8      Level 0
    6   3    Level 1  
   4 2 1 9   Level 2 

      8      Level 0
    6   9    Level 1  
   4 2 1 3   Level 2 

2-2. 다시 부모 노드와 비교. 8보다 9가 더 크니까 둘의 자리를 변경.

      8      Level 0
    6   9    Level 1  
   4 2 1 3   Level 2 

      9      Level 0
    6   8    Level 1  
   4 2 1 3   Level 2 

3. 가장 위에 도달했으므로 그만. 힙의 특성을 그대로 유지해 데이터를 삽입완료.

      9      Level 0
    6   8    Level 1  
   4 2 1 3   Level 2

class MaxHeap:
    def __init__(self):  #배열에서 맨 처음값은 None
        self.items = [None]
    # 1. 새 노드를 맨 끝에 추가한다.
    # 2. 지금 넣은 새 노드를 부모와 비교한다. 만약 부모보다 큰다면 교체한다.
    # 3. 이 과정을 꼭대기까지 반복한다.

    def insert(self, value):
        self.items.append(value)
        cur_index = len(self.items)-1 #현재 인덱스의 값

        while cur_index > 1 : #꼭대기까지 반복
            parent_index = cur_index // 2
            if self.items[cur_index] > self.items[parent_index]:
                self.items[cur_index], self.items[parent_index] = self.items[parent_index], self.items[cur_index]
                cur_index = parent_index #인덱스 변경
            else :
                break
        return

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

즉 맥스 힙의 원소 추가는 O(log(N))만큼의 시간 복잡도를 가진다.

맥스 힙의 원소 제거

최대 힙에서 원소를 삭제하는 방법은 최댓값, 루트 노드를 삭제하고 삭제된 원소를 반환하는 것

원소를 삭제하는 과정

루트 노드와 맨 끝에 있는 원소를 교체한다.
맨 뒤에 있는 원소를(원래 루트 노드)를 삭제한다
변경된 노드와 자식 노드들을 비교한다. 두 자식 중 더 큰 자식과 비교해서 자신보다 자식이 더 크면 자리를 바꿈
자식 노드 둘 보다 부모 노드가 크거나 가장 바닥에 도달하지 않을때까지 3.과정을 반복
2.에서 제거한 원래 루트 노드를 반환

이 맥스 힙에서 원소를 제거보자 (항상 맨 위의 루트 노드가 제거 됩니다.)
      8      Level 0
    6   7    Level 1  
   2 5 4 3   Level 2 

1. 루트 노드와 맨 끝에 있는 원소를 교체한다.

      8      Level 0
    6   7    Level 1  
   2 5 4 3   Level 2 

      3      Level 0
    7   6    Level 1  
   2 5 4 8   Level 2 

2. 맨 뒤에 있는 원소를 (원래 루트 노드)를 삭제. 
이 값이 기존 맥스힙에 있던 가장 큰 값입. 따라서 이 값을 마지막에는 반환해줘야 한다

      3      Level 0
    6   7    Level 1  
   2 5 4 X   Level 2 

3-1. 변경된 노드를 더 큰 자식 노드와 비교해야 한다. 
우선 부모와 왼쪽 자식을 비교. 그리고 부모와 오른쪽 자식을 비교.
그리고 부모 보다 큰 자식 중, 더 큰 자식과 변경.
왼쪽 자식인 6과 오른쪽 자식인 7 중에서 7이 더 크고, 부모인 3보다 크니까 둘의 자리를 변경.

      3      Level 0
    6   7    Level 1  
   2 5 4     Level 2 

      7      Level 0
    6   3    Level 1  
   2 5 4     Level 2 

3-2. 다시 자식 노드와 비교. 
우선 부모와 왼쪽 자식을 비교.
왼쪽 자식인 4는 부모인 3보다 더 크니까 둘의 자리를 변경.

      7      Level 0
    6   3    Level 1  
   2 5 4     Level 2 

      7      Level 0
    6   4    Level 1  
   2 5 3     Level 2 


4. 가장 아래 레벨에 도달했으므로 멈춘다. 힙의 특성을 그대로 유지해 데이터를 삭제완료

      7      Level 0
    6   4    Level 1  
   2 5 3     Level 2 

5. 그리고, 아까 제거한 원래 루트 노드, 8을 반환

    def delete(self):
        self.items[1], self.items[-1] = self.items[-1], self.items[1]
        prev_max = self.items.pop()

        cur_index = 1 #루트 노드의 위치 1

        while cur_index <= len(self.items) -1: #마지막 인덱스까지
            left_child_index = cur_index * 2
            right_child_index = cur_index * 2 + 1
            max_index = cur_index

            if left_child_index <= len(self.items)-1 and self.items[left_child_index] > self.items[max_index]: 
                max_index = left_child_index

            if right_child_index <= len(self.items)-1 and self.items[right_child_index] > self.items[max_index]: 
                max_index = right_child_index

            if max_index == cur_index: # 현재 노드가 자식보다 크므로 교체하지 않아도 됨
                break

            self.items[cur_index], self.items[max_index] = self.items[max_index],self.items[cur_index]
            cur_index = max_index

        return prev_max

시간복잡도는 원소 추가와 마찬가지로 이진트리의 최대 높이가 O(log(N))이니까 반복하는 최대 횟수도 O(log(N))이다

즉 맥스 힙의 원소 삭제는 O(log(N))만큼의 시간 복잡도를 가진다

'공부기록 > 알고리즘 공부' 카테고리의 다른 글

파이썬 문법 정리 2. <내장함수, itertools, heapq, bisect, collections, math> (0)	2022.05.20
파이썬 문법 정리 1. <리스트, 문자열, 튜플,딕셔너리,Set> (0)	2022.05.19
그리디 알고리즘이란?, 백준 설탕배달 (0)	2022.04.23
1. 알고리즘 공부 배열, 리스트 (파이썬 네이티브 코드로 구현하기) (0)	2022.03.24
백준 1927번 <파이썬> (힙에 대해 공부하기) (0)	2022.03.16