11.22 자료구조-Tree, 그래프, BinarySearchTree(BST), BFS/DFS

ㅇ Tree

루트 라는 꼭지점 데이터에서 시작해 간선(edge)로 연결시킨다. 부모노드, 자식노드가 존재하고 자식이 없는 노드는 리프노드라고 한다.

깊이 : 루트 - 0, 그밑의 노드들 - 1, . . . 

레벨 : 같은 깊이를 가진 노드들을 묶음

높이 - 리프노드를 기준으로 루트까지의 길이

서브트리 - 루트에서 뻗어 나오는 큰 트리의 내부에 트리구조를 갖춘 작은 트리

 

ㅇ 그래프

우리가 흔히 아는 수학적인 그런 그래프와는 거리가 멀다.

여러개의 점들이 복잡하게 연결되어 있는 관계를 표현한 자료구조다.

직접적 관계는 두 점 사이를 이어주는 선이 있고, 간접적인 관계는 몇개의 점과 선에 걸쳐 이어진다.

하나의 점은 정점(vertex), 하나의 선은 간선(edge)라고 함.

 

ㅇ 그래프의 표현 방식

인접행렬 - 두 정점을 이어주는 간선이 있으면 두 정점은 인접하다고 한다. 인접행렬은 서로 다른 정점들이 인접한 상태인지를 표시한 행렬로 2차원 배열의 형태로 나타냄. 가장 빠른 경로를 찾을 때 사용한다.

A -> C [0][2] == 1,  B ->A,B->C [1][0] == 1, [1][2] == 1, C-> A [2][0] == 1

 

인접 리스트 - 각 정점이 어떤 정점과 인접하는지를 리스트로 표현한다. (메모리 효율 좋음)

 

ㅇ BST(Binary Search Tree)

이진트리 - 자식 노드가 최대 두개인 노드들로만 구성됨.(정 이진 트리, 포화 이진트리, 완전 이진트리)

이진 탐색트리 - 모든 왼쪽의 자식이 루트나 부모보다 작고, 모든 오른쪽 자식의 값이 루트나 부모보다 큰값을 가지는 특징있음.

 

ㅇ BFS/DFS

BFS(Breadth-First-Search) - 가장 가까운 정점부터 탐색하는 너비우선 탐색

DFS(Depth-First-Search) - 하나의 경로를 끝까지 탐색후, 다음으로 넘어가는 깊이우선 탐색

 

자료구조들을 배우고 아, 이런것들이구나 했는데 이것들을 자바로 표현해보려니 너무 힘들었다. 연습이 필요하다.