Tree
단방향 그래프 구조
Root로 시작되는 node를 edge로 연결
Child Node가 없는 노드를 LeafNode라 한다
계층 구조로 깊이, 높이, 레벨등을 측정 할 수 있다
depth
루트를 0으로 했을 때의 하위 노드 하나마다 +1이 된다
깊이가 같은 노드를 같은 레벨의 Sibling Node라 볼 수 있다
Height
리프 노드를 0으로 했을 때의 상위 노드마다 +1이 된다
Sub tree
큰 트리 내부에 작은 트리
정렬, 탐색에 유리하고 삽입과 삭제가 쉬움
쉬운 시각화로 구조파악이 용이
ex) 디렉토리 구조, 조직도
Binary Tree
'2진'에 주목
1. 정 이진 트리(Full binary tree)
자식 노드가 0개 또는 2개 인 경우
한쪽이 빈 곳이 없다는 의미의 full
2. 포화 이진 트리(Perfect binary tree)
모든 리프 노드의 레벨이 같고, 모든 레벨이 채워진 상태
3. 완전 이진 트리(Complete binary tree)
리프노드 외에 모든 노드가 채워지고, 리프노드가 왼쪽 이상이 채워진 상태
정렬, 탐색에 유리하고 삽입과 삭제가 쉬움
이진 탐색 트리와 이진 힙 구현에 사용
Binary Search Tree
특정한 값 찾기에 특화된 탐색 알고리즘
모든 값의 왼쪽은 크고 오른쪽은 작다
- 중간 값 확인(Root~)
- 중간 값보다 큰가? 작은가?
- 범위 축소 후 반복(재귀)
조건
중복되지 않는 키(값)가 있을것
양 트리가 모두 이진 탐색 트리 일 것
node 삭제
가장 근접한 양 노드(좌측 서브트리 최대값 or 우측 서브트리의 최소값) 자리 교환 후 삭제
자식 노드가 없을 경우 그냥 삭제
실습문제
트리구현
이진트리구현
왼쪽과 오른쪽은 다음단계의 자신이 됨
재귀사용시 save값은 어짜피 자신을 save하기 때문에 호출되는 순서대로 save된다
전위순회
자신->왼쪽->오른쪽
중위순회
왼쪽->자신->오른쪽
후위순회
왼쪽->오른쪽->자신
Graph
정점(vertex)이 간선(edge)으로 이어진다면 인접(adjacency) 관계에 있다(true, +1)
인접 리스트
정점끼리 이어지는 관계를 리스트화
메모리를 효율적으로 사용하고 싶을 때 인접 리스트를 사용
가중치 그래프/비가중치 그래프
가중치(거리, 비용 등 추가적인 정보)가 없다면
모든 간선의 가중치가 동일하게 1로 가정
연산 속도가 빠르다
무향(양방향) 그래프/방향(단방향) 그래프
진입차수/진출차수
한 정점에 진입(들어오는 간선)하고 진출(나가는 간선)하는 간선이 몇 개인지를 나타냅니다.
자기 루프
진출한 간선이 바로 자기자신에게 진입하는 경우, 다른 정점을 거치지 않는다
사이클: 한 정점에서 출발하여 다시 해당 정점으로 귀환시
실습문제
인접 매트릭스 그래프 구현
0 1 2
graph = [[1, 2, 3], 0
[4, 5, 6], 1
[7, 8, 9]] 2인접 리스트 구현
size(3)일 경우
List<List<Integer>> graph = new List<List<Integer>>();
graph =[[],[],[]] 생성
from, to가 size보다 크거나, 음수일 경우 추가하지 않음
추가시 from list에도 to를 추가하고 to list에도 from을 추가
graph =[from[to],to[from],[]]
graph =[[],from[to],to[from]]
여기서 from과 to는 리스트 처음과 끝을 말하는게 아니라 점과 점을 말하는거임 여기서는 인덱스
결과로 graph = [정점[인접정점, 인접정점], 정점[인접정점, 인접정점]..] 의 구조로 출력