20220210 트리, BFS, DFS

트리

트리의 개념

• 비선형 구조
• 원소들간에 1:n 관례를 가지는 자료구조

트리의 정의

• 노드 - 트리의 원소
• 한개 이상의 노드로 이루어진 유한 집합이며 다음 조건을 만족
  • 노드 중 최 상위 노드를 루트(root)라고 한다.
  • 나머지 노드들은 n(≥0)개의 분리 집합으로 분리될 수 있다.
• 분리된 집합들을 각각 하나의 트리가 되며, 루트의 부 트리(subtree)라고 한다.
• 간선 - 노드와 노드를 연결하는 선으로 부모 노드와 자식 노드를 연결
• 형제 노드(sibling node) - 같은 부모 노드의 자식 노드들
• 조상 노드(ancestor node) - 간선을 따라 루트 노드까지 이르는 경로에 있는 모든 노드들
• 서브 트리(subtree) - 부모 노드와 연결된 간선을 끊었을 때 생성되는 트리
• 자손 노드(decedent node) - 서브 트리에 있는 하위 레벨의 노드들
• 차수(degree)
  • 노드의 차수 : 노드에 연결된 자식 노드의 수
  • 트리의 차수 : 트리에 있는 노드의 차수 중에서 가장 큰 값
  • 단말 노드(leaf node) : 차수가 0인 노드 즉, 자식 노드가 없는 노드
• 높이(height) == depth
  • 노드의 높이 : 루트에서 노드에 이르는 간선의 수
  • 트리의 높이 : 트리에 있는 노드의 높이 중에서 가장 큰 값

이진 트리

• 최대 차수가 2인 트리
• 각 노드가 자식 노드를 최대한 2개 까지만 가질 수 있는 트리
  • 왼쪽 자식 노드(left child node)
  • 오른쪽 자식 노드(right child node)
• 모든 노드들이 최대 2개의 서브트리를 갖는 특별한 형태의 트리
• 포화 이진 트리 (Full Binary Tree)
  • 모든 레벨에 노드가 포화 상태로 차 있는 이진 트리
  • 높이가 h일 때, 최대의 노드 개수인 ($2^{(h+1)}-1$)의 노드를 가진 이진 트리
• 완전 이진 트리 (Complete Binary Tree)
  • 높이가 h이고 노드 수가 n개일 때, 포화 이진 트리의 노드 번호 1번부터 n번까지가 빈자리가 없는 이진 트리
• 편향 이진 트리 (Skewed Binary Tree)
  • 높이 h에 대한 최소 개수의 노드를 가지면서 한쪽 방향의 자식 노드 만을 가진 이진 트리
• 배열을 이용한 이진 트리의 표현
  • 루트의 번호를 1로 함
  • 자식 노트는 자신의 번호2, 자신의 번호2+1이 됨
• 노드 번호의 성질
  • 노드 번호가 i인 노드의 부모 노드 번호? i/2
  • 노드 번호가 i인 노드의 왼쪽 자식 노드 번호? 2*i
  • 노드 번호가 i인 노드의 오른쪽 자식 노드 번호? 2*i+1
  • 레벨 n의 노드 번호 시작 번호는? 2^n

비선형 자료구조 완전탐색

너비 우선 탐색 BFS

• 루트 노드의 자식 노드들을 먼저 모두 차례로 방문한 후에, 방문한 자식 노드들을 기준으로 해당 노드의 자식 노드들을 차례로 방문하는 방식
• 인접한 노드들에 대해 탐색 한 후, 차례로 다시 너비우선탐색을 진행하므로, 큐를 활용

BFS()
	Queue q;
	q.add(root V)
	while(!q.isEmpty()){
		t = q.poll();
		t 방문
		for( t와 연결된 모든 간선에 대해){
			u <- t의 자식 노드
			q.add(u);
		}
	}
end BFS()

깊이 우선 탐색 DFS

• 루트 노드에서 출발하여 한 방향으로 갈 수 있는 경로가 있는 곳까지 깊이 탐색해 가다가 더 이상 갈곳이 없게되면, 가장 마지막에 만났던 갈림길 간선이 있는 노드로 되돌아와서 다른 방향의 노드로 탐색을 계속 반복하여 모든 노드를 방문하는 순회방법
• 가장 마지막에 만난 갈림길의 노드로 되돌아가서 다시 깊이 우선 탐색을 반복하므로, 재귀적으로 구현하거나 스택을 사용

DFS(v)
	v 방문;
	for(v의 모든 자식노드 w){
		DFS(w);
	}
end DFS()

순회 (traversal)

• 순회 (traversal) : 트리의 노드들을 체계적으로 방문하는 것
• 3가지의 기본적인 순회방법

1. 전위순회 : VLR, 근좌우
2. 중위순회 : LVR, 좌근우
3. 후위순회 : LRV, 좌우근

수식트리

• 수식을 표현하는 이진 트리 (Expression Binary Tree)
• 연산자는 루트 노드이거나 가지 노드
• 피연산자는 모두 leaf nodes

힙(heap)

• 완전 이진 트리에 있는 노드 중에서 키 값이 가장 큰 노드나 키 값이 가장 작은 노드를 찾기 위해서 만든 자료구조
• 최대 힙(max heap)
  • 키 값이 가장 큰 노드를 찾기 위한 완전 이진 트리
  • 부모 노드의 키 값 > 자식 노드의 키 값
  • 루트 노드 : 키 값이 가장 큰 노드
• 최소 힙(min heap)
  • 키 값이 가장 작은 노드를 찾기 위한 완전 이진 트리
  • 부모 노드의 키 값 < 자식 노드의 키 값
  • 루트 노드 : 키 값이 가장 작은 노드
• 힙 연산 - 삽입 ( 최대 힙의 경우 )
  • 가장 마지막 노드에 입력되는 값을 삽입
  • 부모 노드와 비교해서 작으면 삽입 종료
  • 부모 노드와 비교해서 크면 부모 노드와 Swap
    • 계속 반복해서 부모 노드보다 작을때까지 반복
• 힙에서는 루트 노드의 원소만을 삭제 가능
• 루트 노드의 원소를 삭제하여 반환
• 힙 연산 - 삭제 ( 최대 힙의 경우)
  • 루트 노드의 원소값 삭제 (실제로 삭제하지 않고 반환후, 루트에 덮어쓰는 형태)
  • 마지막 노드 삭제 ( 루트로 마지막 노드의 값을 덮어씀)
  • 루트 노드와 자식 노드를 비교하며 Swap
    • 계속 반복해서 자식 노드가 현재 노드보다 작을때까지 반복

Comparable VS Comparator

• Comparable : 인터페이스를 구현하여 자기 스스로 다른 원소들과 비교 가능
• Comparator : 비교도우미를 선언하여 기준에 따라 값을 비교