BasicAG_12.js

// 트리와 그래프
/*
트리

- 나무를 거꾸로 뒤집어 놓은 모양
- 뿌리(Rood Node), 가지(Edge), 잎(Leaf Node)으로구성
- '탐색'을 위한 자료구조
- Node와 Edge(branch라고도 부름)를 이용하여 데이터를 표현

차수 : 노드의 자식 노드 개수를 말하는 것

이진트리
이진트리란 자식노드가 최대 두 개인 노드들로 구성된 트리입니다.
// 이진트리에는 포화이진트리, 완전이진트리 등이 있습니다.

포화이진트리
모든 노드가 두 개의 자식 노드를 가지며, 모든 잎 노드가 동일한 깊이 또는 레벨을 갖습니다.

완전이진트리
마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있으며, 마지막 레벨에서는 왼쪽부터 노드가 순서대로 채워져 있습니다.

이진트리의 순회

전위순회
루트 노드부터 잎 노드까지 아래방향으로 방문
1. 자신 노드
2. 왼쪽 노드
3. 오른쪽 노드

전위순회
루트 노드부터 잎 노드까지 아래방향으로 방문
1. 왼쪽 노드
2. 자신 노드
3. 오른쪽 노드

후위순회
루트 노드부터 잎 노드까지 아래방향으로 방문
1. 왼쪽 노드
2. 오른쪽 노드
3. 자신 노드

탐색을 위한 이진트리
왼쪽 자식 노드는 나보다 작고, 오른쪽 자식은 나보다 크다는 특징이 있습니다.

레드블랙트리
값이 루트노드보다 작거나 큰 값만 들어올 경우
-> 불균형한 이진탐색트리 -> 검색 효율 저하

이를 보안해주는 것이 레드블랙트리입니다.

1) 트리의 모든 노드는 검정색 아니면 빨간색이다.
2) 루트 노드는 무조건 검정색이다.
3) 모든 잎 노드는 검정색이다.
4) 빨간색의 노드 자식들은 모두 검정색이지만, 검정색 노드 자식들은 어느 색깔이든 상관없다.
5) 루트 노드에서 모든 잎 노드 사이에 있는 검정색 노드의 수는 모두 동일하다.

트리 vs 그래프
그래프는 순환할 수 있다는 차이점이 있습니다.

그래프
DFS, Depth First Search (깊이우선 탐색) - Stack
현재 정점에서 한 방향으로 가면서 검사한다. 막힌 정점은 포기하고 마지막에 따라온 간선으로 되돌아 간다.

BFS, Breadth First Search (너비우선 탐색) - Queue
가까운 정점을 먼저 방문, 먼 정점은 나중에 방문
*/