• 비선형 구조
  • 원소들 간에 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에 대한 최소 개수의 노드를 가지면서 한쪽 방향의 자식 노드만을 가짐

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

수행방법

  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)

수행 방법

  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)

수행 방법

  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

  • 노드 번호를 배열의 인덱스로 사용
  • 노드가 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(오른쪽 서브트리)
  • 좌우의 서브트리도 이진 탐색 트리
  • 중위 순회하면 오름차순으로 정렬된 값

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

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

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

  • 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)
  • 추가 저장 공간 필요