알기쉬운 알고리즘 4주차(1) - 트리

📍 트리

비선형구조, 계층형, 망의 형태로 표현 ex) 파일

✏️ 용어 정리

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)의 특징은 각 노드가 최대 두 개의 자식을 가진다는 것입니다. (0,1,2개)

ex)

      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)의 특징은 노드를 삽입할 때 최하단 왼쪽 노드부터 차례대로 삽입해야 한다는 것 입니다!

ex)

      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

예를 들어, [None, 8, 6, 3, 4, 2, 5] 배열로 트리 구조를 분석해보겠습니다.
다음과 같은 방법으로 트리 구조를 파악할 수 있습니다.

      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를 넣으면 됩니다!

✏️ 풀이방법
1. 현재 인덱스 2 -> 왼쪽 자식의 인덱스
2. 현재 인덱스 2 + 1 -> 오른쪽 자식의 인덱스
3. 현재 인덱스 // 2 -> 부모의 인덱스

• [None, 8, 6, 3, 4, 2, 5] 는
  8 밑에 6, 3 이 있고, 6, 3 밑에 4, 2, 5가 있는 완전 이진 트리

각 레벨에 노드가 꽉 차 있다면 , 노드의 개수는 2의 k승 개가 있다!
Q. 만약 높이가 h 인데 모든 노드가 꽉 차 있는 완전 이진 트리라면
모든 노드의 개수는 몇개일까요?

1 + 2^1 + 2^2 + 2^3 + 2^4 ..... 2^h

즉, 이를 수식으로 표현하면 2^(h+1) - 1 이 됩니다!

즉, 높이가 h 일 때 최대 노드의 개수는 $2^(h+1) -1$

그러면 이 때 최대 노드의 개수가 N이라면, h 는 뭘까요?

$2^(h+1) -1 = N$

라고 할 수 있습니다!
즉 완전 이진 트리 노드의 개수가 N일 때 최대 높이가 $log_2(N+1) - 1$

이진 트리의 높이는 최대로 해봤자 $O(log(N))$ 이다!

📍 힙

힙은 데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리(Complete Binary Tree)
힙은 항상 큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있도록 하는 자료구조입니다. = 부모 노드의 값이 자식 노드의 값보다 항상 커야 합니다.

• 힙은 다음과 같이 최대값을 맨 위로 올릴수도 있고,
  최솟값을 맨 위로 올릴 수도 있습니다! 최댓값이 맨 위인 힙을 Max 힙,
  최솟값이 맨 위인 힙을 Min 힙이라고 합니다!
  

💡 Max힙의 원소 추가

1. 원소를 맨 마지막에 넣습니다.
2. 그리고 부모 노드와 비교합니다. 만약 더 크다면 자리를 바꿉니다.
3. 부모 노드보다 작거나 가장 위에 도달하지 않을 때까지 2. 과정을 반복합니다.
   (= 부모노드와 계속 비교하면서 위치 바꾸기!)

class MaxHeap:
    def __init__(self):
        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

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)) 만큼의 시간 복잡도를 가진다

💡 Max힙의 원소 제거

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

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

 def delete(self):
        # 구현해보세요!
        self.items[1] , self.items[-1] = self.items[-1] , self.items[1]
        prev_max = self.items.pop() #맨 끝 원소 반환
        # 여기부터 힙의 규칙을 지키기 위한 코드
        cur_index = 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[cur_index]:
                max_index = left_child_index

            # 오른쪽 자식이 있고, 오른쪽 자식이 부모노드 보다 더 클 경우
            if right_child_index <= len(self.items)-1 and self.items[right_child_index] > self.items[cur_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]


        return prev_max

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