Data Structure - Graph, Tree, Binary Search Tree

Graph (그래프)

• vertex(정점)와 edge(간선)로 구성된 한정된 자료구조

• 그래프는 무방향일 수 있음

• 간선에 의해 연결된 2개의 노드가 대칭일 수 있다는 의미

• 방향성을 가질 수 있는데, 이는 비대칭 관계를 의미

 

3개의 꼭짓점과 3개의 변으로 이루어진 그래프

자료출처 : 위키백과

 

Tree (트리)

• 트리는 노드로 구성된 계층적 자료구조

• 최상위 노드(루트)를 만들고, 루트 노드의 Child를 추가하고, Child에 또 Child를 추가하는 방식

자료출처 : 코드스테이츠

• A, B, C, D 등 트리의 구성요소를 노드(node)라고 합니다

• 위 그림의 A처럼, 트리 구조에서 최상위에 존재하는 노드를 root라고 합니다

• 루트를 기준으로, 다른 노드로의 접근하기 위한 거리를 depth라고 합니다

• 같은 depth에 존재하는 노드들은 sibling 관계에 있습니다

• 그림에서 A는 B와 C의 부모(parent) 이고, B와 C는 A의 자식(child) 입니다

• 노드와 노드를 잇는 선을 edge 라고 합니다

• 자식이 없는 노드는 leaf 라고 합니다

 

이진 트리

이진 트리 탐색

전위 순회 (Pre-order) : Self - Left - Right

중위 순회 (In-Order) : Left - Self - Right

후위 순회 (Post-Order) : Right - Left - Self

자료출처 : 위키백과

 

Binary Search Tree (BST)

• 이진 탐색 트리는 최대 2개의 자식만 갖는 트리

• 트리 구조는 재귀적이므로, 자식 노드 역시 최대 2개의 자식을 가짐

• 이진 탐색 트리에서는 노드의 값이 정렬 방법에 따라 순서가 존재

• 노드의 왼쪽 서브트리에는 노드의 값보다 작은 값이, 오른쪽 서브트리에는 노드의 값보다 같거나 큰 값이 존재

 

이진 탐색 트리를 순회하는 방법

 

• 깊이 우선 탐색 (DFS, Depth-First Search)

• 맹목적 탐색방법의 하나로 탐색트리의 최근에 첨가된 노드를 선택하고, 이 노드에 적용 가능한 동작자 중 하나를 적용하여 트리에 다음 수준(level)의 한 개의 자식노드를 첨가하며, 첨가된 자식 노드가 목표노드일 때까지 앞의 자식 노드의 첨가 과정을 반복해 가는 방식

자료출처 : 위키백과

• 너비 우선 탐색 (BFS, Breadth-First Search)

• 맹목적 탐색방법의 하나로 시작 정점을 방문한 후 시작 정점에 인접한 모든 정점들을 우선 방문하는 방법이다. 더 이상 방문하지 않은 정점이 없을 때까지 방문하지 않은 모든 정점들에 대해서도 너비 우선 검색을 적용한다. OPEN List 는 큐를 사용해야만 레벨 순서대로 접근이 가능

자료출처 : 위키백과

 

 

Reference

• 그래프
• 트리
• 이진 트리
• 깊이 우선 탐색
• 너비 우선 탐색