[Algorithm] 트리(tree)

TOC

• 트리(Tree)
  • 트리란?
  • 트리의 특징
  • 용어
• 이진트리
  • 이진트리란?
  • 이진트리의 특성
• 이진트리의 종류
  • 포화 이진 트리
  • 완전 이진 트리
  • 편향 이진 트리
• 이진트리의 순회
  • 순회(Traversal)
  • 전위순회(preorder traversal) : VLR
  • 중위순회(inorder traversal) : LVR
  • 후위순회(postorder traversal) : LRV
  • 특징
• 이진트리의 표현 : 배열
  • 노드 번호의 성질
  • 노드 번호의 성질 2
• 이진트리의 저장
  • 부모 번호를 인덱스로 자식 번호 저장
  • 자식 번호를 인덱스로 부모 번호 저장
  • 루트 찾기, 조상 찾기
  • 배열 이용의 단점
  • 단점 보완 : 연결리스트
• 수식 트리
• 이진 탐색 트리
  • 이진 탐색 트리의 특징
  • 연산1 : 탐색연산
  • 연산2 : 삽입연산
• 이진 탐색 트리 : 성능
  • 검색 알고리즘의 비교

트리(Tree)

트리란?

• 비선형 구조
• 원소들 간에 1:N 관계를 가지는 자료구조
• 원소들 간에 계층 관계를 가지는 계층형 자료구조
• 상위 원소에서 하위 원소로 내려가면서 확장되는 구조

트리의 특징

• 트리는 연결 컴포넌트(Connected component)
• 트리에 속한 두 정점 u, v 사이에 경로가 반드시 하나만 존재
• 트리는 싸이클(cycle; 순환)이 없다. 있다면 트리가 아닌 그래프(graph)
• 순회할 때 방문표시를 안한다. 구조상 한 번 갔던 노드를 또 가지 않음.

• 한 개 이상의 노드로 이루어진 유한 집합
• 최상위 노드 : 루트(root)
• 나머지 노드들은 n개의 분리집합 Tn으로 분리 가능(n은 0개 이상)
• 이 T1, T2, ... Tn은 각각이 하나의 트리(재귀적 정의) **루트의 부 트리(subtree)**라고 한다.

용어

요소

• 노드(Node) : 트리의 원소

• 간선(Edge) : 노드를 연결하는 선

• 루트 노드(Root node) : 트리의 최상위, 시작 노드

• 잎 노드(Leaf node) : 트리의 최하위, 종료 노드, 과거엔 **단말 노드(Terminal Node)**라고 불렸음

• 서브 트리(Subtree) : 부모 노드와 연결된 간선을 끊으면 생성되는 트리

관계

• 형제 노드(Sibiling node) : 같은 부모 노드의 자식 노드들
• 조상 노드 : 간선을 따라 루트 노드까지 이르는 최단 경로에 있는 노드들
• 자손 노드 : 서브 트리에 있는 하위 레벨의 노드들

크기(size)

• 노드의 크기 : 자신을 포함한 모든 자식 노드의 수

차수(degree)

• 노드의 차수 : 각 노드가 지닌 자식 노드의 수
• 트리의 차수 : 트리에 있는 노드의 차수 중 최댓값

높이 / 깊이

• 노드의 높이 : 루트~노드에 이르는 간선의 수. 노드의 레벨
• 트리의 높이 : 트리에 있는 노드 높이 중 최댓값(최대 레벨)

이진트리

이진트리란?

• 모든 노드들이 최대 2개의 서브트리를 갖는 형태
• 왼쪽/오른쪽 자식 노드(left/right child node)

이진트리의 특성

• 레벨 i에서의 노드 최대 개수는 2^i 개
• 높이가 h인 이진 트리가 가질 수 있는 노드: 최소 h+1개, 최대 2^(h+1)-1개

이진트리의 종류

포화 이진 트리

• 모든 레벨에 노드가 포화상태로 차 있는 이진 트리
• 높이가 h일 때, 최대의 노드 개수인 2^(h+1)-1의 노드를 가진 이진 트리
• 노드의 번호는 루트를 1번으로 하여 정해진 위치에 대한 노드 번호를 가진다.
• BFS 방식으로 왼쪽부터 노드 번호를 배치

완전 이진 트리

• 포화 이진트리의 노드 번호 1번부터 특정 n번까지 빈 자리가 없는 이진트리
• 포화 이진트리가 아님. 꽉 차면 안된다!
• 노드 번호는 연속되어야 함. 건너뛰면 안된다!

편향 이진 트리

• Skewed Binary Tree
• 높이 h에 대한 최소 개수의 노드를 가지면서 한쪽 방향의 자식 노드만을 가짐

이진트리의 순회

순회(Traversal)

• 각 노드를 중복되지 않게 체계적으로 전부 방문(visit)
• 트리는 비 선형 구조이므로 선형구조에서와 같이 선후 연결 관계를 알 수 없다.
• 트리에 특화된 탐색 방법 필요

전위순회(preorder traversal) : VLR

수행방법

1. V: 현재 노드 n을 방문하여 처리
2. L: 현재 노드 n의 왼쪽 서브트리로 이동
3. R: 현재 노드 n의 오른쪽 서브트리로 이동

알고리즘

def preorder_traverse(T):
  if T:                     # 노드가 있는 경우
    visit(T)
    preorder_traverse(T.left)
    preorder_traverse(T.right)

중위순회(inorder traversal) : LVR

수행 방법

1. L: 현재 노드 n의 왼쪽 서브트리로 이동
2. V: 현재 노드 n을 방문하여 처리
3. R: 현재 노드 n의 오른쪽 서브트리로 이동

알고리즘

def inorder_traverse(T):
  if T:
    inorder_traverse(T.left)
    visit(T)
    inorder_traverse(T.right)

후위순회(postorder traversal) : LRV

수행 방법

1. L: 현재 노드 n의 왼쪽 서브트리로 이동
2. R: 현재 노드 n의 오른쪽 서브트리로 이동
3. V: 현재 노드 n을 방문하여 처리

알고리즘

def postorder_traverse(T):
  if T:
    postorder_traverse(T.left)
    postorder_traverse(T.right)
    visit(T)

특징

• DFS(깊이우선탐색) 방식 사용
• 왼쪽 자식 먼저 탐색하는 것으로 약속

이진트리의 표현 : 배열

노드 번호의 성질

• 노드 번호가 i인 노드의 부모 노드 번호 : i/2
• 노드 번호가 i인 노드의 왼쪽 자식 노드 번호 : 2i
• 노드 번호가 i인 노드의 오른쪽 자식 노드 번호 : 2i+1
• 레벨 n의 시작 노드 번호 : 2^n

ex) 노드 번호가 5인 경우

부모 노드 번호 : 2
왼쪽 자식 번호 : 10
오른쪽 자식 번호 : 11

노드 번호의 성질 2

• 노드 번호를 배열의 인덱스로 사용
• 노드가 h인 이진 트리를 위한 배열의 크기는?
  • 레벨 i의 최대 노드 수 : 2^i
  • 1 + 2 + 4 + ... + 2^i = 2^(h+1)-1

이진트리의 저장

참고📢 : 항상 노드의 개수 = 간선의 개수 + 1

부모 번호를 인덱스로 자식 번호 저장

알고리즘

'''
input
4
1 2 1 3 3 4 3 5
'''

E = int(input())   # 간선(edge)의 개수
V = E + 1          # 정점(node)의 개수
arr = list(map(int, input().split()))

# 부모를 인덱스로 자식번호 저장
L = [0]*(V+1)
R = [0]*(V+1)

for i in range(E):
    p, c = arr[i*2], arr[i*2+1]    # 부모, 자식
    if L[p]==0:                    # 아직 자식이 없는 경우
        L[p] = c                   # 첫 번째 자식으로 저장
    else:                          # 자식이 하나 있으니까
        R[p] = c                   # 두 번째 자식으로 저장

결과

L : [0, 2, 0, 4, 0, 0]
R : [0, 3, 0, 5, 0, 0]

• 1번 노드의 자식 : 2번, 3번 노드
• 3번 노드의 자식 : 4번, 5번 노드

자식 번호를 인덱스로 부모 번호 저장

알고리즘

L = [0]*(V+1)
R = [0]*(V+1)
P = [0]*(V+1)

for i in range(E):
    p, c = arr[2*i], arr[2*i+1]
    if L[p]:
        R[p] = c
    else:
        L[p] = c
    P[c] = p

• L, R과 같은 P를 초기화/정의
• for문에서 자식 노드 번호 c를 인덱스로 하고 부모 노드 번호 p를 값으로

루트 찾기, 조상 찾기

알고리즘

# 5번 노드의 조상 찾기
root = 0
c = 5
ans = [c]
while P[c] != 0 :
  c = P[c]
  ans.append(c)
root = c

• 조상은 root 노드이므로, 부모가 없다.
• P[c]일 때까지 c를 P[c]로 계속 지정하며 트리를 올라감
• ans 배열에 root에 도달할 때까지의 노드 번호가 쌓임

배열 이용의 단점

• 편향 이진 트리 : 사용하지 않는 배열 원소에 대한 메모리 공간 낭비 발생
• 트리의 중간에 노드의 삽입/삭제 경우 배열의 크기 변경 어려워 비효율적

단점 보완 : 연결리스트

• 이진 트리의 모든 노드는 최대 2개의 자식 노드를 가짐
• 일정한 단순 연결 리스트 노드를 사용하여 구현
• 구현 생략

수식 트리

• 수식을 표현하는 이진 트리
• 수식 이진 트리(Expression Binary Tree)라고 부르기도 함
• 연산자는 루트 노드 또는 가지 노드
• 피연산자는 모두 잎 노드
• 중위/후위/전위 순회 가능

이진 탐색 트리

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

이진 탐색 트리의 특징

• 모든 원소는 서로 다른 유일한 키를 가짐
• key(왼쪽 서브트리) < key(루트 노드) < key(오른쪽 서브트리)
• 좌우의 서브트리도 이진 탐색 트리
• 중위 순회하면 오름차순으로 정렬된 값

연산1 : 탐색연산

• 루트에서 시작
• 탐색할 key값 x를 루트 노드의 key값과 비교
  • 탐색key값 x = 루트노드key값 : 원하는 원소 찾았으니 탐색연산 성공
  • 탐색key값 x < 루트노드key값 : 루트노드의 왼쪽 서브트리에 대해 탐색연산
  • 탐색key값 x > 루트노드key값 : 루트노드의 오른쪽 서브트리에 대해 탐색연산
• 서브트리에 대해 순환적으로 탐색연산 반복

연산2 : 삽입연산

• 삽입할 원소가 같은 트리에 있으면 삽입 불가
• 같은 원소가 트리에 있는지 선탐색 필요
• 먼저 탐색 연산 수행
• 탐색에서 탐색 실패되는 위치가 삽입 위치

이진 탐색 트리 : 성능

탐색, 삽입, 삭제 시간은 트리의 높이만큼 시간 소요

• O(h), h는 BST의 깊이

평균

• 이진트리가 균형적으로 생성
• O(log n)

최악

• 한쪽으로 치우친 경사 이진트리
• O(n)
• 순차탐색과 같은 시간 복잡도

검색 알고리즘의 비교

배열의 순차 검색

• 정렬된 경우 : O(N)
• 정렬되지 않은 경우 : O(N)

이진 탐색

• 정렬된 배열인 경우 : O(log N)
  • 고정 배열 크기와 삽입, 삭제 시 추가 연산 필요
• 이진 탐색 트리에서의 평균 : O(log N)
  • 최악의 경우 : O(N)
• 완전 이진 트리 또는 균형 트리로 바꿀 수 있다면 최악의 경우 회피 가능
  • 새로운 원소를 삽입할 때 삽입 시간 줄이기
  • 평균과 최악의 시간이 같다 : O(log N)

해쉬 검색

• O(1)
• 추가 저장 공간 필요