[Datastructure] 트리구조, 힙

참고 자료

😇 신찬수 교수님 자료구조 강의

💡 트리구조

연결리스트는 각 노드들이 한 줄로 연결된 선형적인 자료구조이다.

하지만 트리는 부모-자식 관계를 계측정으로 표현한 일반적인 자료구조라고 할 수 있다.

트리 구조 중에 자식 노드가 1개인 것을 트리구조의 특별한 경우라고 말할 수 있다.

✏️ 구조

출처권희정님 github

✏️ 용어

부모/자식 노드 : A는 B의 부모노드, B는 A의 자식노드 (1레벨)  

조상/자손 노드 : A는 D의 조상노드, D는 A의 자손노드 (N레벨)  

루트 노드 : 모든 노드의 조상노드, (A)  

리프 노드 : 자식이 없는 노드, 트리의 끝 노드(H,I,J,F,G)  

레벨 : 루트노드의 레벨을 0으로 시작한다. 한 세대씩 내려가면서 1씩 증가  

깊이 : 루트노드에서 다른 노드를 연결하는 에지(선)의 개수 (노드 H의 깊이 = 3)  

경로 : 두 노드 사이를 연결하는 에지의 시퀀스 

    C와 H 사이의 경로 = H -> D -> B -> A -> C
    경로의 길이는 에지의 수, 위의 경우 경로의 길이는 4

높이 : 노드의 높이는 자식 노드까지의 가장 큰 깊이

    A노드의 높이 -> H,I가 가장 깊은 곳에 있으므로 3

트리 높이 : 루트 노드의 높이가 트리 높이, 여기서는 A노드가 루트노드이므로 트리 높이는 3

분지수 : 가지의 개수
        노드의 분지수 = 자신의 자식 수(B노드의 분지수는 2)
        트리의 분지수 = 트리에서 가장 큰 분지수(위의 경우 2)

부트리 : 어떤 노드와 그 노드의 자손노드들로 구성된 부분 트리

💡 이진트리

이진트리 : 트리 중, 모든 노드의 자식이 2개를 넘지 않는 트리

실제 자료구조에서 사용되는 트리는 이진트리가 대부분이다.

✏️ 표현법

❗️ 리스트를 중복해서 표현

`[15, [11, [8, [6, [], []], [9, [], []]], [12, [], [14, [], []]] ],  
[26,[20, [], []],[30, [], [35, [], []]] ]]`

[루트, [루트의 왼쪽 부트리], [루트의 오른쪽 부트리]] 형식으로 재귀적으로 정의한다.

❗️ 연결 리스트로 표현

부모 노드를 제외한 각 노드가
key, parent, left, right에 대한 정보를 가진다.  

부모노드는 부모노드가 없으므로 key, left, right에 대한 정보를 가진다.
각 노드는 parent, left, right 노드로 접근할 수 있는 메서드를 가진다.

❗️ 하나의 리스트로 표현

H = [15, 11,26 8,12,20,30, 6,9,None,14,None,None,None,35]

레벨 0부터 차례대로, 왼쪽에서 오른쪽 순서로 작성한다.
자식노드가 없는 경우는 None으로 작성한다.

장점
이렇게 상수시간의 연산으로 자식노드와 부모노드를 찾을 수 있다.

왜냐하면 현재 노드의 인덱스번호를 알고 있다면, 자식노드와 부모노드의 인덱스번호를 계산할 수 있기 때문이다.

자식노드 : H[인덱스N * 2 + 1] or H[인덱스N * 2 + 2]
부모노드 : H[(인덱스N - 1) // 2]

부모노드의 인덱스 N이 3일때 (노드8)

(노드8)의 왼쪽 자식노드는 H[3 * 2 + 1] (노드6)
오른쪽 자식노드는 H[3 * 2 + 2] (노드 9)

노드8의 부모노드는 H[(3-1)//2]

단점
불필요한 메모리 낭비가 발생한다.

위의 예시와 같이, 노드가 없는 공간을 None으로 표시하는데, 리스트에 길이가 쓸데없이 늘어나며 메모리가 증가하게된다.(None도 메모리공간을 차지한다)

이런 불필요한 공간낭비를 줄이려면 None으로 표현되는 것을 모두 채워야한다.

💡 힙(heap)

모양 성질과 힙 성질을 만족하는 리스트에 저장된 값의 시퀀스

모양 성질: 
        1. 마지막 레벨을 제외한 각 레벨의 노드가 모두 채워져 있어야 한다.
        2. 마지막 레벨에선 노드들이 왼쪽부터 채워져야한다.

힙 성질:
        1. 루트 노드를 제외한 모든 노드에 저장된 값(key)은 자신의 부모노드의 값보다 크면 안된다.

보통 리스트의 데이터는 힙성질, 모양성질을 갖춘 데이터가 주어지지 않는다.
따라서 힙 성질을 갖춘 데이터가 되도록 리스트의 데이터들을 재정렬해주어야하는데, 이를
makeheap()함수라고 한다.

✏️ heap 클래스

class Heap:
    def __init__(self, L): #L은 리스트
        self.A = L
        self.make_heap()

    def __str__(self):
        return str(self.A)

✏️ maekheap함수

makeheap는 불규칙하게 주어진 데이터를 heap성질을 만족하게 하는 함수는 heapify_down()이라는 함수를 반복하면서 이루어진다.

H = [2,8,6,1,10,15,3,12,11]
def makeheap(self):
    n = len(self) 
    #데이터의 각 요소에 대해서, 마지막 요소부터 heapify_down함수를 실행
    for k in range(n-1, -1, -1):
        self.heapify_down(k,n) #매개변수로 대상 노드의 인덱스와 전체 데이터의 길이가 주어진다.

✏️ heapify_down함수

def heapify_down(self, k,n):
    #두 자식노드의 값이 자기자신보다 작을거나 리프노드에 도달할때까지 반복
    while 2*k + 1 < n:
        #왼쪽 자식노드와 오른쪽 자식노드의 인덱스번호 계산
        L, R = 2 * k + 1, 2 * k + 2
        # 부모노드와 자식노드들 중 가장 큰 값의 인덱스 찾기
        if self.A[L] > self.A[k]:
            m = L
        else:
            m = k

        if R < n and self.A[R] > self.A[m]:
            m = R
        
        if m != k: #현재 k가 heap 성질 위배하는 경우
            self.A[k], self.A[m] = self.A[m], self.A[k]
            k = m #k에 m값을 줌으로써 m인덱스를 부모노드로하는 heap성질 검증 실행한다.
        else:
            break #현재 노드가 heap 성질을 만족한다면 break건다. 왜냐하면 makeheap()에 의해 k가 작아지면서 윗 노드에서 heap성질을 위반하면 아래 노드들에 대해 알아서 검증해주기 때문이다.

❗️ make_heap함수의 수행시간

최악의 경우, heapify_down()연산은 가장 아래의 노드가 가장 위로 올라와야하는 경우이다.
이때, 연산의 시간복잡도는 O(logN)이다.

makeheap()연산에서 각 노드들에 대해서 O(N)번 O(logN)의 연산을 하므로
makeheap()연산의 전체 시간 복잡도는 O(NlogN)이다.

✏️ heapifyup, insert함수

heapifyup함수는 insert연산을 위한 함수이다.
insert연산은 힙 리스트의 마지막에 값을 추가하고, 이 값이 힙 성질을 가지도록
부모노드들을 타고 올라가면서 정렬을해야한다.
따라서 시간복잡도는 O(logN)이다.

def heapify_up(self, k):
    #k가 양수이고, 현재노드의 부모노드의 값 < 현재노드일때 실행
    while k > 0 and self.A[(k-1)//2] < self.A[k]:
        #부모노드와 현재노드의 위치를 바꾸고
        self.A[k], self.A[(k-1)//2] = self.A[(k-1)//2], self.A[k]
        #k에 부모노드의 인덱스번호를 주고 while문 반복
        k = (k-1) // 2
    
def insert(self, key):
    #힙 리스트의 마지막에 값을 추가한다.
    self.A.append(key)
    #현재 리스트가 4개 -> len(A) = 4, indexnum = 3 이므로 -1해준다.
    self.heapify_up(len(self.A) - 1)

✏️ delete_max

현재 힙 리스트의 값 중 가장 큰 값을 삭제하고 리턴한다.
삭제하고 리턴 -> pop연산을 해야하므로
A[0]을 A[n-1]의 값으로 대체하고 pop, 이후 0번 인덱스 노드부터 재배치한다-> heapify_down(0, len(A))

def delete_max(self):
    if len(self.A) == 0:
        return None
    #리턴할 max값 저장
    key = self.A[0]
    #대체
    self.A[0], self.A[len(self.A) - 1] = self.A[len(self.A) - 1],self.A[0]
    #삭제
    self.A.pop() 
    self.heapify_down(0,len(self.A))
    return key

✏️ heap_sort

정렬알고리즘이다.
주어진 데이터를 make_heap으로 힙 정렬을 한다.
heap정렬의 특징은 가장 큰 값이 root노드가 된다는 것이므로,
힙 리스트의 첫값을 마지막값과 대체, 그리고 마지막 값을 제외한 리스트에 대해 heapify_down으로 정렬 을 반복한다.

make_heap => O(N)
heapify_down => O(logN)
따라서
heap_sort => O(NlogN)

def heap_sort(self):
    n = len(self.A)
    #현재 리스트의 길이의 인덱스번호를 큰값부터 -1부여
    for k in range(len(self.A) - 1, -1, -1)
        #대체
        self.A[0], self.A[k] = self.A[k],self.A[0]
        
        #뒤로 대체된 값을 제외한 값들에 대해 heap정렬
        n = n-1
        heapify_down(0,n)

💡 연산시간 정리(n개의 값을 저장한 리스트와 힙에 대해)

make_heap : O(NlogN) or O(N) <N개 데이터에 heapify_down, 분석상 N에 가까움>
heapify_down, up : O(logN)
insert : O(logN) <추가되는 각 값에대한 heapify_up>
delete_max : O(logN) <처음값과 마지막 값 대체 후, 새로운 root에 대해 heapify_down>
find_max : O(1) <처음값 리턴>
heap_sort : O(NlogN) <make_heap하고, delete_max N번 실행>

이처럼 힙 자료구조는 insert, find-max, delete-max 를 많이하는 어플리케이션에
최적화되어있다.(min연산은 파이썬의 heapq모듈을 사용하도록하자)

반면 search연산은 O(N)의 시간복잡도가 걸리므로 힙 자료구조를 통해 특정 값을
search하기 위해서는 O(N^2)의 비효율적인 시간복잡도가 걸리게 된다.