Graph , Tree , Heap

Graph

노드(Node, 정점)들과 그 노드들을 연결하는 간선(Edge)들로 이루어짐 

노드(Node): 데이터를 담고 있는 개체
간선(Edge): 노드들을 연결하는 선으로, 노드와 노드 간의 관계를 나타냄

 

포털사이트 검색엔진 , sns에서 사람들과의 관계 , 네비게이션(길찾기)등에서 사용됨

 

Java에선 인접 리스트(Adjacency List)나 인접 행렬(Adjacency Matrix)을 사용하여 그래프를 구현

 

인접 리스트 : 각 정점에 연결된 정점들을 리스트로 표현하여 그래프를 나타내는 방법 중 하나

자료구조 라이브러리( JGraphT, GraphStream 등 )를 사용하면
그래프를 표현하고 다양한 그래프 알고리즘을 쉽게 구현할 수 있습니다. 

깊이 우선 탐색( DFS )

갈 수 있는 만큼 최대한 깊이 가고, 더 이상 갈 곳이 없다면 이전 정점으로 돌아가는 방식으로 그래프를 순회한다.
( 재귀 호출, 스택 등을 사용해서 구현 )

 

넓이 우선 탐색( BFS )

시작 정점을 방문한 후, 시작 정점에 인접한 모든 정점을 방문한다.
인접한 정점을 방문한 뒤, 다시 해당 정점의 인접한 정점을 방문하며 그래프를 순회한다.
( 큐, 반복문 등을 사용해서 구현 )

 

Tree

그래프(Graph)의 특수한 형태로 계층적인 구조를 나타내는 비선형 자료구조이다

트리 자료구조는 일반적으로 방향 그래프(Directed Graph)로 간주
, 트리의 각 간선이 부모 노드에서 자식 노드로의 방향성을 가지기 때문입니다. 

루트(root) 노드 : 맨 위에 위치한 노드 ex) dog 
리프(leaf) 노드 : 자식이 없는 노드 ex) canine, fox, wolf

서브트리(sub-tree): 트리에서 어떤 한 노드와 그 노드의 자손들로 이루어진 트리

간선/엣지/링크/브랜치: 노드와 노드를 연결하는 선

Binary Tree( 이진트리 )

각 노드가 최대 2명의 자식을 가지는 트리이다.
자식노드는 항상 자신이 부모의 왼쪽자식인지 오른쪽자식인지를 부여받는다.

이진 탐색 트리(Binary Search Tree)

이진 트리의 일종으로 탐색을 위한 자료구조

왼쪽 자식 노드 < 부모 노드 < 오른쪽 자식 노드

완전 이진 트리( Complete Binary Tree )

 

이진 트리의 한 형태로  
레벨 n-1까지는 모든 노드가 채워져 있고, 마지막 레벨 n에서는 왼쪽부터 오른쪽으로 노드가 순차적으로 채워져 있습니다.

 

노드를 삽입할 때 왼쪽부터 차례대로 삽입

 

 

 

Heap

완전 이진트리를 기본으로함

최소값 및 최대값을 빠르게 찾아내기 위해 고안된 자료 구조

 

힙은 최대힙(Max heap)과 최소힙(Min heap)으로 나뉘어진다. 

최대힙은 (자식 노드의 값 ) <= (부모 노드의 값)  ,  최소힙은 (자식 노드) >= (부모 노드)

 

일반적으로 배열로 구현된다

부모 노드의 인덱스는 1로, 왼쪽 자식 노드부터 2, 3 순서이다.
(부모 노드의 인덱스) = (자식 노드 인덱스) / 2
(왼쪽 자식 노드의 인덱스) = (부모 노드의 인덱스) * 2
(오른쪽 자식 노드의 인덱스) = (부모 노드의 인덱스) * 2 + 1

 

최솟값이나 최댓값을 찾기 위해 배열을 사용하면 Ο(n)만큼 시간이 걸린다.
하지만 힙을 사용하면 O(logn)만큼 소요되므로, 배열을 사용할 때보다 빠르게 최솟값과 최댓값을 구할 수 있다.

 

최대힙에 데이터 삽입

힙은 완전 이진 트리이기 때문에, 삽입할 노드는 기본적으로 왼쪽 최하단부 노드부터 채워진다.

 

 

최대힙의 데이터 삭제

최대 힙(max heap)에서 삭제 연산은 최댓값을 가진 요소를 삭제하는 것이다.

( 보통 루트 노드를 제거 )