트리란?
나무를 뒤집은것처럼 생긴 데이터 구조. 각각의 데이터는 노드라고 불리며 상하 관계를 기준으로 위를 부모노드, 부모노드에 속해있는 아래쪽 노드를 자식노드라고 한다. 그리고 각각의 노드는 간선으로 연결되어있다.
이진트리? 자식 노드가 최대 두개 뿐인 트리이다. 자료의 삽입, 삭제 방법에 따라 정 이진 트리(Full binary tree), 완전 이진 트리(Complete binary tree), 포화 이진 트리로 나뉜다.
정 이진 트리 : 각각의 노드가 0~2개의 자식 노드를 갖는 구조
완전 이진 트리 : 정 이진 트리이면서 완전 이진 트리인 경우
포화 이진 트리 : 마지막 레벨을 제외한 모든 노드가 가득 차 있고 최소 마지막 레벨의 왼쪽 노드는 차있는 구조.
> 이진 탐색 트리 특징
트리의 모든 왼쪽 자식의 값이 루트나 부모보다 작고, 모든 오른쪽 자식의 값이 루트나 부모보다 큰 값을 가진다.
트리 순회란? 특정 목적을 위해 트리의 모든 노드를 한 번씩 방문하는 것
트리를 순회할 수 있는 세 가지 방법 : 전위 순회, 중위 순회, 후위 순회
전위 순회란? 루트를 시작으로 A>B>D>F>C>G>H순으로 노드를 조회하는 것이다. 루트 >왼쪽 >오른쪽 순으로 순회한다.
중위 순회란? 루트를 중점으로 왼쪽 노드를 순회한 후 루트를 순회하고 오른쪽 노드를 순회하게 된다. 위 예시에서는 B>D>F>A>C>G>H 순으로 조회한다고 보면 된다.
후위 순회란? 후위 순회는 루트를 가장 마지막에 순회한다. 제일 왼쪽 끝 아래에 있는 노드를 시작으로 순회가 끝나면 오른쪽 노드로 넘어가고 루트로 넘어가는 방식이다. 순서는 D>F>B>G>H>C>A순이다.
Graph란?
여러개의 점들이 서로 복잡하게 연결되어 있는 관계를 표현한 자료구조이다. Graph은 직접적인 관계 및 간접적인 관계로 구성된다. 또 그래프의 탐색은 하나의 정점에서 시작해 모든 정점들을 한 번씩 탐색하는 것이 목적이다. 데이터는 정렬이 되어 있아서 하나씩 모두 방문하여 찾아야 한다.
직접적인 관계란 ? 두점을 이어주는 하나의 선이 존재하는 것을 의미한다.
간적접인 관계란 ? 두점을 이어주는 하나의 선이 아닌 몇개의 점과 선을 거쳐 존재하는 것을 의미한다.
BFS와DFS?
정점들을 탐색하는 방법이다.
BFS(Breadth-First Search)?
원하는 곳까지 가는 가장 가까운 방법을 탐색하는 것이다. 그리고 더는 탐색할 정점이 없을 때, 그다음 떨어져 있는 정점을 순서대로 방문한다. 주로 최단거리를 찾을때 사용한다.
DFS(Depth-First Search)?
하나의 경로를 끝까지 탐색한 후, 원하는 데이터가 아니라면 다음 경로로 넘어가 탐색한다. 한 정점에서 시작해서 다음 경로로 넘어가기 전에 해당 경로를 완벽하게 탐색할 때 사용한다. 시간은 오래 걸려도 모든 노드를 확인하기 때문에 상황에 맞춰 사용하는 것이 좋다.
