Tree

• 트리의 개념

비선형 구조

원소들 간에 1:n 관계를 가지는 자료구조

원소들 간에 계층관계를 가지는 계층형 자료구조

상위 원소에서 하위 원소로 내려가면서 확장되는 트리(나무)모양의 구조

 

한 개 이상의 노드로 이루어진 유한 집합이다.

즉, 한 개의 노드로만 이루어져도 트리다!

노드 중 최상위 노드를 루트(root)라고 한다.

각 노드는 각각 하나의 트리가 되며 루트의 부 트리(subtree) 라고 한다.

 

노드 : 트리의 원소

간선 : 노드를 연결하는 선

루트 노드 → 맨 위에서 트리의 시작이 되는 노드

단말노드(리프 노드) = 잎 노드 → 맨 아래에 있는 노드, 자식 노드가 없는 노드, 차수가 0인 노드

형제 노드 → 같은 부모 노드의 자식 노드들

조상 노드 → 간선을 따라 루트 노드까지 이르는 경로에 있는 모든 노드들

서브 트리 : 부모 노드와 연결된 간선을 끊었을 때 생성되는 트리

자손 노드 → 서브 트리에 있는 하위 레벨의 노드들

 

노드의 차수 = 노드에 연결된 자식 노드의 수

트리의 차수 = 트리에 있는 노드의 차수 중에서 가장 큰 값

cf) 단말 노드는 자식 노드가 없기 때문에 차수가 0이다.

 

노드의 높이 = 루트에서 노드에 이르는 간선의 수 = 노드의 레벨

트리의 높이 = 트리에 있는 노드의 높이 중에서 가장 큰 값, 최대 레벨

 

• 이진 트리

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

각 노드가 자식 노드를 최대한 2개까지만 가질 수 있는 트리 (왼쪽 + 오른쪽)

 

레벨 i 에서의 노드의 최대 개수는 2**i 개

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

 

• 포화 이진 트리

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

높이가 h일 떄, 최대의 노드 개수인 (2**(h+1) - 1)의 노드를 가진 이진 트리

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

 

• 완전 이진 트리

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

 

• 편향 이진 트리

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

왼쪽 편향 이진 트리 / 오른쪽 편향 이진 트리

 

• 이진 트리 - 순회

순회 : 트리의 각 노드를 중복되지 않게 전부 방문하는 것을 말하는데, 트리는 비선형 구조이기 때문에 선형구조와 같이 선후 연결 관계를 알 수 없다. 따라서 노드들을 체계적으로 방문하는 특별한 방법이 필요하다.

 

• 기본적인 3가지 순회방법

전위순회 (pre_order) → 부모 노드 방문 후 자식 노드를 좌우 순서로 방문

중위순회 (in_order) → 왼쪽 자식 노드 방문 후 부모노드, 오른쪽 자식 노드 순으로 방문

후위순회 (post_oreder) → 좌우 자식 노드를 방문 후 부모노드를 방문

 

• 노드 번호의 성질

노드 번호가 i인 노드의 부모 노드 번호 = i//2

노드 번호가 i인 노드의 왼쪽 자식 노드 번호 = i * 2

노드 번호가 i인 노드의 오른쪽 자식 노드 번호 = i * 2 + 1

레벨 n의 시작 노드 번호 = 2**n

 

• 배열을 이용한 이진 트리의 표현

노드 번호를 배열의 인덱스로 사용

 

• 배열을 이용한 이진 트리 표현의 단점

편향 이진 트리의 경우, 사용하지 않는 배열 원소에 대한 메모리 공간 낭비가 발생

트리 중간에 새로운 노드를 삽입하거나 기존 노드를 삭제할 경우, 배열의 크기 변경이 어려움

 

트리 → 연결 컴포넌트 (친구의 친구는 나랑도 친구)

정점의 개수가 N개일 때 모든 정점이 연결되는데 필요한 간선의 수는 N-1 개다.

따라서 간선의 개수가 N-1 개보다 많다면 반드시 싸이클이 발생하는 곳이 있다.

싸이클이 발생하면 트리가 아니다!

 

트리는 그래프의 일종이다.

트리만의 특성 부모 노드가 자식 노드(인접 정점)를 저장함.

이때 부모와 자식은 계층성이 있기 때문에 마치 유향 그래프처럼 부모 노드가 일방적으로 자식 노드 정보를 저장한다.

 

각 노드의 방문시점 3개

1. 처음 노드에 진입했을 때 (전위)
2. 왼쪽 자식 노드를 갔다 올 때 (중위)
3. 오른쪽 자식 노드를 갔다 올 때 (후위)

( 자식 노드가 없어 보여도 공백 노드가 있기 때문에 무조건 위 3가지 순간이 있다!)

 

# 13
# 1 2 1 3 2 4 3 5 3 6 4 7 5 8 5 9 6 10 6 11 7 12 11 13

N = int(input())
arr = list(map(int, input().split()))
left = [0] * (N+1)  # 1번부터 N번
right = [0] * (N+1)
par = [0] * (N+1)
E = N - 1   # 간선 수

for i in range(E):
    p, c = arr[i*2], arr[i*2 + 1]
    # p의 왼쪽 자식을 확인
    if left[p] == 0:
        left[p] = c
    else:
        right[p] = c
    # c의 부모 p도 저장
    par[c] = p

    # 단말 노드 -> 왼쪽, 오른쪽 자식이 둘다 없어서 0 이다.
    # 루트 노드 -> 부모 노드가 없어서 0 이다.
count = 0

def inorder(v):     # v = 부모 노드
    # 재귀호출 종료
    if v == 0:  # 공백 노드인지 체크
        return
    global count
    count += 1  # 노드 수를 세야할 경우 글로벌 변수를 넣는다.
    # 시작점 v를 루트 노드로 하는 서브 트리의 노드 수도 셀 수 있다.

    # 처음 진입한 경우 -- 전위
    # 재귀호출 진행
    inorder(left[v])
    print(v, end=' ')   # 중위순회할 경우 이 자리에서 방문표시
    # 왼쪽 자식에서 돌아온 후 -- 중위
    inorder(right[v])

    # 오른쪽 자식에서 돌아온 후 -- 후위

inorder(1)  # 처음 시작하는 노드는 루트!

 

• 완전 이진 트리와 포화 이진 트리의 차이

완전 이진 트리 안에 포화 이진 트리가 들어간다.

즉, 모든 포화 이진 트리는 완전 이진 트리이다.

완전 이진 트리는 모든 노드가 최대 개수의 자식 노드를 갖고 있지는 않지만, 마지막 높이만 빼면 포화 이진 트리이다. 그리고 마지막 높이도 왼쪽부터 순서대로 채워져있다.

중간에 빈 노드가 없기 때문에 앞에서 본 노드 번호의 성질을 사용하여 배열에 써먹기 좋다.

노드 개수를 알면 필요한만큼 배열 크기를 마련하고 바로 사용 가능하다.

N = 10  # 완전 이진 트리 노드수, 마지막 노드

def inorder(v):     # v = 부모 노드
    if v > N:
        return

    inorder(v * 2)
    print(v, end=' ')
    inorder(v * 2 + 1)

inorder(1)

# 8 4 9 2 10 5 1 6 3 7

트리 정보가 없는데도 순회가 된다!

트리가 완전 이진 트리이기 때문에 루트 노드와 총 노드 수만 알아도 노드 번호 생성이 가능한 것!