Tree랑 Graph 배웠는데 그래프는 어디에 어떻게 써먹어야할지 감이 안잡히네
트리 : 무방향으로 연결된 계층적 자료 구조, 비선형 구조
-루트Root : 시작하는 꼭지점 데이터
-노드Node : 각 데이터
-부모 노드Parent Node
-자식 노드Child Node
-리프 노드Leaf Node : 자식이 없는 노드
-형제 노드Sibling Node : 같은 레벨의 노드들
-서브 트리Sub Tree : 트리 내부에 트리 구조를 갖춘 작은 트리
트리의 장점
-효과적인 계층 구조 표현
-정렬과 탐색을 위한 알고리즘을 구현하는 데에 사용됨
-삽입과 삭제가 쉽다
-시각화가 쉬우므로, 구조 파악이 용이하다
+추가 공부할 것들
이진 트리, 이진 탐색 트리, 힙, 트라이, 레드-블랙 트리
힙 트리 : 가장 크거나 작은 값을 빠르게 찾기 위한 이진트리. 완전 이진 트리이다. 루트에는 항상 가장 큰 값(최대 힙) 혹은 가장 작은 값(최소 힙)이 있다. 부모 노드는 항상 자식 노드의 값보다 크거나 같다 (혹은 작거나 같다).
트라이 트리Trie Tree : 문자열 탐색에 빠른 트리. 루트를 비워두고, 부모 노드부터 자식 노드까지 이어서 찾으면 단어 하나 완성. 단어의 끝마다 표시를 해준다.
자식 노드 하나하나 다 포인터를 저장한다는 점에서 메모리 비효율적일 수 있지만, 문자열 탐색이 빠르다는 장점이 있다.
정 이진 트리Full binary tree : 각 노드가 0개 혹은 2개의 자식 노드를 갖는다
완전 이진 트리Complete binary tree : 마지막 레벨을 제외한 모든 노드가 가득 차 있고, 마지막 레벨의 노드는 왼쪽이 채워져야 한다
포화 이진 트리Perfect binary tree : 모든 리프 노드의 레벨이 같고, 모든 레벨이 가득 채워져 있다.
이진 탐색 트리Binary Search Tree : 모든 왼쪽 자식 노드의 값이 부모 노드보다 작고, 모든 오른쪽 자식 노드의 값이 부모 노드보다 큰 값을 갖는다.
BST에서 노드의 삭제는, 삭제 후 해당 노드의 왼쪽에서 가장 큰 값으로 대체하는 것으로 한다. 왼쪽 노드가 없다면 오른쪽 노드에서 가장 작은 값을, 리프 노드라면 삭제로 끝.
중위순회inorder : left - root - right
전위순회preorder : root - left - right
후위순회postorder : left - root - right
그래프Graph : 여러 개의 점이 서로 연결되어 있는 관계를 표현한 자료 구조
-정점vertex : 노드. 그래프의 기본 원소
-간선edge : 정점을 이어주는 선. 정점 간의 관계
-인접 정점adjacent vertex : 간선에 의해 직접 연결되어 있는 정점
-가중치 그래프weighted Graph
-비가중치 그래프 unweighted Graph
-무방향 그래프undirected graph : 1과 2가 연결되어 있다면 1에서 2로, 2에서 1로 연결 가능한, 방향이 없는 그래프
-단방향 그래프 directed graph : 방향이 있는 그래프. 1에서 2로 연결되어 있어도 2에서 1로 연결되지 않을 수 있다.
-진입차수in-degree : 한 정점에 들어오는 간선의 개수
-진출차수out-degree
-자기 루프self loop : 간선이 곧바로 정점 자기 자신에게 진입하는 경우
-사이클cycle : 한 정점에서 출발하여 해당 정점으로 돌아올 수 있다면 사이클이 있다고 표현한다.
그래프의 표현방식 1. 인접행렬
int[] matrix = new int[][]{
{0, 1, 1}, //0번은 1, 2번으로 이동 가능하다
{1, 0, 0}, //1번은 0번으로 이동 가능하다
{0, 1, 0}}; //2번은 1번으로 이동 가능하다
위 그래프는 비가중치 그래프.
1이 아닌 다른 값들을 넣어서 가중치 그래프로 다른 정보를 담을 수도 있다.
그래프의 표현방식 2. 인접 리스트
ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
graph.add(new ArrayList<>(Arrays.asList(1, 2, null)));
graph.add(new ArrayList<>(Arrays.asList(0, null)));
graph.add(new ArrayList<>(Arrays.asList(1, null)));
graph.get(0) == [1, 2, null] // 0 -> 1 -> 2 -> null
graph.get(1) == [0, null] // 1 -> 0 -> null
graph.get(2) == [1, null] // 2 -> 1 -> null
