8. 8

0101011011010011000101001100

트리

비선형 자료구조.
다 대 다
"그래프"
  - 계층형 성질(상위, 하위)
  - 속에 '트리'가 있다.
  
이진트리
  - 자식 노드가 최대 둘.

-----

트리
  - 비선형 구조.
  - 원소 간에 1:n 관계
  - 원소 간에 계층 관계
  - 상위에서 하위로 내려가며 확장되는 나무 모양의 구조
  - 'root' -> 'branch' -> 'leaf'
  
노드, node
  - 트리의 원소
  - 트리는 한 개 이상의 노드로 이루어진 유한 집합.
  - 최상위 노드 -> 'root'
  - 나머지 노드들은 n(>=0)개의 분리 집합 T1,T2...Tn으로 분리될 수 있다.
  - 이들은 각각 하나의 트리가 되며(재귀적 정의) 루트의 부 트리,subtree라 한다.

간선, edge
  - 노드와 노드를 연결하는 선
  - 부모 노드와 자식 노드를 연결
  
노드 종류
  - 형제 노드, sibling node
  - 조상 노드 
    - 간선을 따라 루트 노드까지 이르는 경로에 있는 모든 노드들
  - 서브 트리
  - 자손 노드
    - 서브 트리에 있는 하위 레벨의 노드들.

차수, degree
  - 노드의 차수 : 노드에 연결된 자식 노드의 수
  - 트리의 차수 : 트리에 있는 노드의 차수 중에서 가장 큰 값
  - 단말 노드(리프 노드) : 차수가 0인 노드
  
높이
  - 노드의 높이 : 루트에서 노드에 이르는 간선의 수. 노드의 레벨
  - 트리의 높이 : 트리의 높이 중 가장 큰 값.

-----

이진트리
  - 특성
    - 높이 i에서의 노드의 최대 개수 -> 2^i개
    
포화 이진 트리, Perfect Binary Tree
  - 모든 레벨의 노드가 포화 상태
  - 높이가 h일 때, 최대 노드 개수인 2^(h+1)-1 의 노드를 가짐
  - 루트를 1번으로 하여 정해진 순서의 숫자를 가짐.

완전 이진 트리, Complete Binary Tree
  - 높이가 h이고 노드 수가 n개일 때,
  - 포화 이진 트리의 노드 번호 1번부터 n번까지 빈 자리가 없는 트리
  - 왼쪽 부터 채워져 있어야 함.

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

배열을 이용한 이진 트리의 표현
  - 루트의 번호 1
  - 레벨 n의 노드 : 왼쪽 부터 2^n 부터 2^(n+1) - 1 까지 번호 차례로 부여
  - 노드 번호가 i인 노드
    - 부모 노드 -> i/2
    - 왼쪽 자식 -> i*2
    - 오른쪽 자식 -> i*2+1

  - 단점
    - 편향 이진 트리의 경우 메모리 공간 낭비 발생
    - 트리의 중간에 새로운 노드를 삽입하거나 삭제할 경우 배열 크기 변경이 어려워 비효율적.
    
-----
완전탐색
  - 비선형구조인 트리, 그래프의 각 노드를 중복되지 않게 전부 방문.
  - 깊이 우선 탐색, DFS, Depth First Search
  - 너비 우선 탐색, BFS, Breadth First Search

너비 우선 탐색
  - 루트 노드의 자식들을 차례로 방문 후
  - 방문 했던 자식 노드들을 기준으로 다시 자식 노드 차례로 방문
  - 큐, QUEUE 이용..!

BFS() 수도코드
  - 큐 생성
  - 루트 v를 큐에 삽입
  - while(큐가 비어 있지 않다면)
    - t <- 큐의 첫 번째 원소 반환
    - t 방문
    - for(t의 모든 간선에 대해)
      - u <- t의 자식노드
      - u를 큐에 삽입.

보충

그래프는 시작점을 정해주지 않음.
트리는 루트 노드가 있음.

탐색 logn을 보장.

Swea1233. [S/W 문제해결 기본] 9일차 - 사칙연산 유효성 검사
  - String 일 때 "" 이걸로 감싸야 인정.
  
Swea4008. [모의 SW 역량테스트] 숫자 만들기
  - 재귀. 순열.

Swea9229. 한빈이와 Spot Mart D3
  - start를 정해서 조합 만들기.

바킹독 - BFS

Bj1926 - 그림
  - BFS
  - 술술.