[Code Tree] Tree, Heap

OverView

• 트리
• 이진 트리
• 이진 트리 탐색
• 이진 탐색 트리
• Heap

---

1. 트리

 

: 두 지점의 연결 관계로 구성되어 있으며 계층 관계가 존재한다는 것이 특징

 

용어

• 노드: 각 지점을 의미, 정점
• 간선: 두 노드를 연결하는 선을 의미, 에지
• 루트 노드: 트리의 맨꼭데기를 의미
• 부모, 자식: 트리에서 연결된 두 노드의 관계를 의미, 더 위쪽에 있는 노드를 부모 노드, 아래쪽에 있는 노드를 자식 노드라고 한다. 
• 차수: 특정 노드를 기준으로, 자식의 수가 얼마나 되는지 의미
• 깊이: 루트 노드와 얼마나 떨어져 있는지를 가리키는 말
• 높이: 트리에서 깊이가 가장 깊은 노드의 깊이 혹은 1을 더한 값을 의미
• 리프 노드: 자식을 갖고 있지 않은 노드

 

트리의 본 정의

: 노드끼리 전부 연결되어 있으면서 사이클이 존재하지 않는 그래프

 

Unrooted tree

: 부모 자식 관계가 정의되지 않은 경우

- 차수: 노드에 연결된 간선의 개수 / 리프 노드: 차수가 1인 노드 

- 루트 노드는 사람이 정하기 나름이다. 

 

Rooted tree

: 루트 노드가 설정되어 있는 트리 

 

* 트리에 대한 설명 

- 루트가 정해져 있는 트리의 경우에도 루트는 단 하나만 존재할 수 있다. 

- 트리에서 루트는 정해져있지 않고, 상황별로 어떤 노드가 루트가 될 지 달라질 수 잇다. 

- 한 노드의 자식 노드 개수는 제한이 없지만, 자식 노드의 부모 노드는 단 1개만 존재한다. 

- 노드가 하나만 있어도 모든 노드가 이어져 있고 사이클이 존재하지 않으므로 트리이다. 

 

---

 

1. 이진트리 

 

: 자식의 수를 최대 2개로 제한(0개, 1개 가능) 

- 구현하기 쉽다는 특징을 가진다. 

 

특정 노드의 위치 : i

왼쪽 자식의 위치 : i * 2 / 오른쪽 자식의 위치 : i * 2 + 1

>> 이진 트리는 배열로 구현이 가능하다. 

 

* 반대로 부모 노드의 위치는 i / 2 이다. 

 

* 자식이 꽉 차있지 않더라도 비어있는 자식의 배열에도 칸을 비워두어야 한다. 

 

---

 

1. 이진 트리 탐색 

- 재귀를 사용하면 탐색을 비교적 쉽게 구현 가능

 

• 전위 탐색 (Preorder Traversal)
  • 부모 - 왼쪽 자식 - 오른쪽 자식 순으로 탐색
• 중위 탐색 (Inorder Traversal)
  • 왼쪽 자식 - 부모 - 오른쪽 자식 순으로 탐색
• 후위 탐색 (Postorder Traversal)
  • 왼쪽 자식 - 오른쪽 자식 - 부모 순으로 탐색

---

 

1. 이진 탐색 트리 (Binary Search Tree)

: 부모의 왼쪽 방향에 있는 노드들은 전부 부모보다 값이 작아야 하고, 부모의 우측 방향에 있는 노드들은 전부 부모보다 값이 커야 한다.

 

2. 이진 탐색 트리의 탐색

def bst_search(x):
    set node = bst.root
    while node != null and node.value != x:  
        if node.value > x:             
            node = node.left            
        else:
            node = node.right              
    
    return node

 

3. 이진 탐색 트리의 삽입

: 탐색 과정과 거의 유사

* null에 도달하기 전까지 계속 진행하여 값 x 가 들어갈 위치를 찾아줘야 한다. 

* 최종적으로 도달한 null 지점에서의 부모 정보를 알아야지만 삽입이 가능하다. 

 

새로운 노드를 추가하는 방법

• Case 1. 트리에 노드가 전혀 없는 경우
  • 이진 탐색 트리의 root = node(x)

• Case 2. parent에 적혀 있는 값 > 삽입하려는 값 
  • parent 왼쪽 node(x) 삽입
• Case 3. parent에 적혀 있는 값 < 삽입하려는 값 
  • parent 오른쪽 node(x) 삽입

def bst_insert(x):
	node = bst.root
    parent = bst.root
    
    while node != null: # nod가 null이 되기 전까지 반복
    	parent = node
        if node.value > x:
        	node = node.left
        else:
        	node = node.right
   
   	if parent == null: 		# Case 1.
   		bst.root = node(x)
    else if parent.value > x: 		# Case 2.
    	parent.left = node(x)
    else:				# Case 3. 
    	parent.right = node(x)

 

 

4. 이진 탐색 트리 삭제 

: 먼저 값 x를 찾는다. 

 

1. Case 1. 값을 찾았을 때 해당 노드의 왼쪽이 비어있다면, node의 오른쪽 노드를 위로 올려준다. 
2. Case 2. 값을 찾았을 때 해당 노드이 오른쪽이 비어있다면, node의 왼쪽 노드를 위로 올려준다. 
3. Case 3. 값을 찾았을 때 해당 노드의 왼쪽 오른쪽 노드가 전부 채워져 있다면, successor를 찾아야 한다. 
   1. successor란: 현재 노드를 기준으로 더 크면서 가장 작은 값을 갖는 노드 
   2. successor는 현재 노드의 오른쪽 자식인 node.right를 시작으로 계속 내려갈 수 있는 만큼 왼쪽으로 내려가는 방식으로 비교적 간단하게 구할 수 있음
   3. successor를 구하고 나면, successor에 있는 값을 node에 옮겨준 뒤 successor의 오른쪽 자식을 위로 올려준다. 
      1. 단, successor가 node의 오른쪽 자식인 경우, Case 1 처럼 단순히 노드의 오른쪽 노드를 위로 올려준다. 

def bst_search(x):
	node = bst.root
	while node != null and node.value != x:
		if node.value > x:
			node = node.left
		else:
			node = node.right

    return node

def bst_minimum(node):
    while node.left != null:
        node = node.left
    return node

def bst_delete(x):
    node = bst_search(x)
    if node.left == null:
        move(node.right, node)
    else if node.right == null:
        move(node.left, node)
    else:
        succ = bst_minimum(node.right)
        
        if succ == node.right:
            move(node.right, node)
        else:
            node.value = succ.value
            move(succ.right, succ)

 

 

5. 균형 잡힌 이진 탐색 트리

• Red Black Tree: 자가 균형 이진 탐색 트리, 연관 배열 등을 구현하는 데 쓰이는 자료구조

• AVL Tree: 자가 균형 이진 탐색 트리
  • 두 자식 서브 트리의 높이는 항상 최대 1만큼 차이 난다. 
  • 만약 어떤 시점에서 높이 차이가 1보다 커지면 스스로 균형을 잡는다. 

 

 

- 삽입, 삭제가 일어나는 순간 루트 노드와 주위에 있는 노드를 회전 등의 작업을 통해 적절하게 조절하므로서 왼쪽 자식과 오른쪽 자식에 있는 노드 간의 높이 차가 크게 벌어지지 않도록 하는 방법

- 삽입, 삭제, 탐색의 시간 복잡도 항상 O(logN) 유지 

---

 

1. Heap (max-heap, min-heap) 이진 트리 종류

: 특정 수가 추가되고 삭제되었을 때 원하는 heap 구조를 유지하는 데 O(logn) 만큼이 소요

- 주어진 수들 중 최대 최소값을 O(1)에 구할 수 있다. 

 

max-heap : 모든 노드에 대해 부모 노드가 자신의 자식 노드가 갖는 값보다 같거나 큰 경우를 만족하는 경우

- 루트 노드에는 전체 숫자 중 항상 최댓값이 들어 있다. 

- 삭제는 루트 노드에서만 가능하다. 

- k 번째 최댓값을 구할 수 없다. 항상 가장 큰 값이 무엇인지만 알 수 있는 자료구조

 

• 힙은 값을 넣는 순서와 상관 없이 맨위에 최댓값 또는 최솟값이 존재한다. 
• 힙 맨 아래의 값은 순서에 따라 변하는 것이 가능하다. 힙은 항상 가장 큰/작은 값이 무엇인지만 알 수 있는 자료 구조
• 힙에서 삭제는 루트 노드에서만 가능하다. 삭제 시간복잡도 O(logn)
• 힙을 만드는 시간 O(n) / 특정 원소를 삽입하는데 걸리는 시간 O(logn)

 

heapify: 현재 노드를 기준으로 이 노드가 heap 특성에 맞을 때까지 계속 밑으로 내려주는 과정

# heapify 과정 한 번 일어날 때 최대 logN번
def heapify(arr, n, i):
    largest = i
    l = i * 2
    r = i * 2 + 1
    
    # 왼쪽 자식이 크다면, 최대 번호 수정
    if l <= n and arr[l] > arr[largest]:
        largest = l
    
    # 오른쪽 자식이 크다면, 최대 번호 수정
    if r <= n and arr[r] > arr[largest]:
        largest = r
    
    # 최대 노드가 자식 노드라면 교환
    if largest != i:
        swap(arr[i], arr[largest])
        
        # 교환한 위치ㅔ서 다시 heapify 진행
        heapify(arr, n, largest) 
        
# max-heap 만들어주는 함수 -> O(N)
def build_heap(arr, n):
    for i in range(1, n//2 + 1): # 2번째 원소부터 1번째 원소까지
        heapify(arr, n, i)

 

 

2. 힙에서 삽입, 삭제

삽입: 현재 삽입된 기준으로 부모와 값을 계속 비교하며, 부모 값이 더 작다면 두 값을 교환해주는 것을 반복하면 된다.

- 시간복잡도: O(logN)

def insert(arr, n, x):
    arr.append(x)
    
    i = n + 1
    while i > 1 and arr[i//2] < arr[i]:
        swap(arr[i], arr[i//2])
        i = i // 2

 

삭제: 루트 값을 삭제한다. -> 맨 끝 값을 루트로 올린다. -> heapify를 실행해서 max/min-heap으로 만들어준다. 

- 시간복잡도: O(logN)

def remove(arr, n):
    arr[1] = arr[n] # 마지막 노드를 처음으로 옮김
    delete arr[n] # 마지막 노드 삭제
    heapify(arr, n-1, 1)