🦋 Tree
- root : 시작노드
- edge : 간선
- node : 각 데이터
- 부모노드, 자식노드
- 리프노드 : 자식없는 노드
- 깊이 : 루트~특정노드까지, 0부터, d는 2임
- 레벨 : 같은깊이를 레벨로 표현, 1부터, d는 3임
- 높이 : 리프부터 높이, 0부터, B는 2, A는 3
🦋 이진트리
- 자식노드가 최대 두개인 트리=
- 정 이진트리 : 자식 0개 or 2개
- 포화 이진트리 : 모든 리프노드 레벨 동일, 리프빼고 다 2개
- 완전이진트리 : 마지막레벨 제외한 모든 노드가 가득 차 있어야 하고, 마지막은 전부 차 있지 않아도 되지만 왼쪽이 채워져야 함
🦋 이진 탐색 트리
- 오름차순된 정수배열을 두개로 쪼갠후 탐색이 필요한 부분만 탐색하는 알고리즘
🦋 트리 순회
탐색하는 우선순위
전위순회
부모>왼쪽자식>오른쪽자식
중위순회
왼쪽자식>부모>오른쪽자식
후위순회
왼쪽자식>오른쪽자식>부모
레벨순회
1레벨부터 아래로 봄
예시)
전위 (부모>왼쪽자식>오른쪽자식)
1 6 4 7 9 8 10 5 2 3 11
중위 (왼쪽자식>부모>오른쪽자식)
7 4 8 9 10 6 5 1 3 2 11
후위 (왼쪽자식>오른쪽자식>부모)
7 8 10 9 4 5 6 3 11 2 1
🦋 GRAPH
- 정점(vertex) : 노드
- 간선(edge) : 단방향간선, 양방향간선
- 인접정점 : 간선으로 직접 연결된 정점
- 가중치 그래프 : 연결강도적힘
- 무방향 그래프 : 방향없음
- 자기루프 : 정점에서 진출하는 자신이 바로 자신에게 진입하는경우
- 사이클 : 한 정점에서 출발하여 다시 해당 정점으로 돌아갈 수 있다면 사이클이 있는것
- 인접 : a랑b가 이어져있다면 1 아니면 0으로 표현한 표
A는 C, E 연결돼있으니 0, 0, 1, 1이런식
0,0,1,1
1,0,0,0
0,1,0,0
0,1,0,0 - 인접리스트
0번 노드는 1, 2, 3과 모두 이어져 있으므로
[0, *] -> [1, *] -> [2, *] -> [3, null]
1번 노드는 0과 2에 이어져 있으므로
[1, *] -> [0, *] -> [2, null]
2번 노드는 0과 1과 3에 이어져 있으므로
[2, *] -> [0, *] -> [1, *] -> [3, null]
3번 노드는 0과 2에 이어져 있으므로
[3, *] -> [0, *] -> [2, null]
🦋 DFS
- 그래프탐색방법
출처 https://developer-mac.tistory.com/64
- 최대한 깊이 내려간 뒤, 더이상 갈 곳이 없을경우 옆으로 이동
🦋 BFS
- 최대한 넓게 이동한 다음, 더이상 갈 수 없을 때 아래로 이동
