[SW Intermediate] Tree

Tree

---

Tree

[Tree의 특징]

1) 한 개 이상의 노드로 이루어진 유한 집합

- 루트(Root): 노드 중 최상위 노드

- 나머지 노드들: n(>=0) 개의 분리 집합 T1....Tn 으로 분리 될 수 있다.

2) 이들 T1...Tn 은 각각 하나의 트리가 되며(재귀적 정의) 루트의 서브 트리(Sub Tree) 라고 한다.

 

[Tree의 구성 요소]

1) 노드

- 트리의 원소

2) 간선

- 노드를 연결하는 선

- 부모 노드와 자식 노드를 연결

3) 차수

- 노드에 연결된 자식 노드의 수

- 트리의 차수:  트리에 있는 노드의 차수들 중 가장 큰 값

- 단말 노드(리프노드): 차수가 0인 노드, 자식 노드가 없는 노드

 

---

이진 트리(Binary Tree)

[Binary Tree의 특징]

1) 모든 노드들이 2개의 서브 트리를 갖는 특별한 형태의 트리

2) 노드가 자식 노드를 최대 2개까지만 가질 수 있는 트리

- 왼쪽 자식 노드(left child node)

- 오른쪽 자식 노드(right child node)

3) 레벨 L 에서의 노드의 최대 개수는 2^L 개

4) 높이가 h 인 이진 트리가 가질 수 있는 노드의 최소 개수는 (h+1) 개, 최대 개수는 2^(h+1) -1 개가 된다.

 

---

포화 이진 트리

모든 레벨의 노드가 포화 상태로 차 있는 트리

1) 최대의 노드 개수인 (2^(h+1)-1)의 노드를 가진 트리

2) 루트를 1번으로 하여 2^(h+1)-1 까지 정해진 위치에 대한 노드 번호를 갖는다.

 

---

완전 이진 트리

높이가 h 이고 노드 수가 n개 일 때 Full 이진 트리의 노드 번호 1번 부터 n 번까지 빈자리가 없는 이진 트리이다.

 

---

편향 이진 트리

높이 h에 대한 최소 개수의 노드를 가지면서 한쪽 방향의 자식 노드 만을 가진 이진 트리이다.

 

---

순회

트리의 각 노드를 중복되지 않게 전부 방문(visit) 하는 것을 순회 라고 한다.

 

[3가지의 순회 방법]

 

1) 전위 순회

-  VLR

- 자손 노드보다 루트 노드 먼저 방문

2) 중위 순회

- LVR

- 왼쪽 자손, 루트, 오른쪽 자손 순으로 방문

3) 후위 순회

- LRV

- 루트 노드보다 자손 노드 먼저 방문 

 

---

전위 순회

1) 현재 노드 n을 방문하여 처리: V

2) 현재 노드 n의 왼쪽 서브 트리 이동: L

3) 현재 노드 n의 오른쪽 서브 트리 이동: R

 

def preorder_traverse(T):
	if T: # T is not None
    	visit(T) # print(T.item)
        preorder_traverse(T.left)
        preorder_traverse(T.right)

---

중위 순회

1) 현재 노드 n의 왼쪽 서브 트리로 이동: L

2) 현재 노드 n을 방문하여 처리: V

3) 현재 노드 n의 오른쪽 서브 트리로 이동: R

 

def inorder_traverse(T):
	if T:
    	inorder_traverse(T.left)
        visit(T) # print(T.item)
        inorder_traverse(T.right)

---

후위 순회

1) 현재 노드 n의 왼쪽 서브 트리로 이동: L

2) 현재 노드 n의 오른쪽 서브 트리로 이동: R

3) 현재 노드 n을 방문하여 처리: V

def postorder_traverse(T):
	if T:
    	postorder_traverse(T.left)
        postorder_traverse(T.right)
        visit(T) # print(T.item)

---

Expression Tree

List 또는 Linked List 를 이용하여 Tree 를 구현할 수 있다.

 

[노드 번호의 성질]

1) 노드 i 의 부모 노드 번호: i//2

2) 노드 i 의 왼쪽 자식 노드 번호: ix2

3) 노드 i의 오른쪽 자식 노드 번호: ix2+1

 

---

이진 탐색 트리(Binary Search Tree)

- 탐색 작업을 효율적으로 하기 위한 자료구조

- 모든 원소는 서로 다른 유일한 key를 가짐

- key(왼쪽 서브 트리) < key(루트 노드) < key(오른쪽 서브 트리)

- 왼쪽 서브 트리, 오른쪽 서브 트리도 이진 탐색 트리

- 중위 순회하면 오름 차순으로 정렬된 값을 얻을 수 있음

 

[탐색 연산]

1) 루트에서 시작

2) 탐색할 키 값 x를 루트 노드의 키 값과 비교

- 키 값 x == 루트 노드의 키 값:

   원하는 원소를 찾았으므로 탐색 연산 성공

- 키 값 x  < 루트 노드의 키 값:

   루트 노드의 왼쪽 서브 트리에 대해 탐색 연산 수행

- 키 값 x > 루트 노드의 키 값:

   루트 노드의 오른 쪽 서브 트리에 대해 탐색 연산 수행

3) 서브 트리에 대해서 순환적으로 탐색 연산을 반복

 

[삽입 연산]

1) 먼저 탐색 연산을 수행

- 삽입할 원소와 같은 원소가 트리에 있으면 삽입할 수 없으므로 같은 원소가 있는지 탐색하여 확인

- 탐색 시 탐색 실패가 결정되는 위치가 삽입 위치가 됨

2) 탐색 실패한 위치에 원소를 삽입

 

---

힙(Heap)

완전 이진 트리에 있는 노드 중에서 키 값이 가장 큰 노드나 가장 작은 노드를 찾기 위해서 만든 자료구조이다.

- 최대 힙(Max heap)

- 최소 힙(Min heap)

---

문1: subtree

from collections import defaultdict

def count_nodes(n):
    global count

    if len(tree_map[n]) == 0:
        return
    for item in tree_map[n]:
        count_nodes(item)
        count += len(tree_map[item])

T = int(input())
for test_case in range(1, T + 1):
    e, n = map(int, input().split())
    tree = list(map(int, input().split()))
    tree_map = defaultdict(list)


    for i in range(0, len(tree)-1, 2):
        tree_map[tree[i]].append(tree[i+1])
        
    # count 변수를 n과 n 자식 노드 수의 합으로 초기화 해준다.
    count = len(tree_map[n]) + 1
    count_nodes(n)

    print(f'#{test_case} {count}')

 

문2: 이진탐색

def make_tree(n):
    # 1~ n+1 까지 순회 하면서 위치를 찾아 넣어준다.
    # binary_search_tree: left < 현재노드 <right
    # 현재노드 : index , left : index*2, right: index*2 +1
    # 중위 순회로 구현한다.
    global number
    if n < N + 1:
        make_tree(2 * n)
        tree[n] = number
        number += 1
        make_tree(2 * n + 1)


T = int(input())

for test_case in range(1, T + 1):
    N = int(input())
    tree = [0 for _ in range(N + 1)]
    number = 1

    make_tree(1)
    print(f'#{test_case} {tree[1]} {tree[N // 2]}')

 

문3: 이진 힙

'''
heapify와 heappush 결과가 다를 수 있다는 점을
몰랐어서 잘못 된 풀이로 시간이 꽤 걸렸던 문제이다..

heapify는 리스트를 heap 구조로 바꿀 때 사용하는 함수인데
최소 값을 반환 하는데는 문제 없지만 heap 구조로 바꾼 상태에서 데이터를 가져와야하는 상황에서는
적합하지 않을 수 있다. 

heappush를 한 경우와 결과 값이 다를 수 있다.

'''



T = int(input())

import heapq
for test_case in range(1, T + 1):
    n = int(input())
    num_list = list(map(int, input().split()))
    heap_list = []
    sum_nums = 0
    
    for item in num_list:
        heapq.heappush(heap_list, item)
    heap_list = [0]+heap_list


    while n > 0:
        # 이진트리 부모 인덱스 = (자식노드 인덱스)//2
        n = n//2
        sum_nums += heap_list[n]

    print(f'#{test_case} {sum_nums}')

 

문4: 노드의 합

T = int(input())
for test_case in range(1, T + 1):
    n, m, l = map(int, input().split())
    tree_list = [0 for _ in range(n+1)]
    for _ in range(m):
        index, data = map(int, input().split())
        tree_list[index] = data
    for i in range(n, 0, -1): # n~1 까지 -1 씩 감소하며 반복
        if not tree_list[i]:
            if i*2+1 > n:
                tree_list[i] = tree_list[i*2]
                continue
            tree_list[i] = tree_list[i*2] + tree_list[i*2 + 1]
        else:
            continue
    print(f'#{test_case} {tree_list[l]}')