Graph, Tree, BST

 

Graph

 

그래프는 Node (노드)와 Edge (간선)으로 구성되어 있다.

 

그래프는 엣지가 노드 자기 자신을 가리킬 수도 있고, 한 노드가 다른 노드만 가리키기도 하고, 서로 가리키기도 하고 복잡한 형태를 가졌다.

 

그래서 그래프는 무방향(undirected - 대칭), 방향성(directed - 비대칭) 그래프로 나뉠수도 있고

그래프의 엣지가 원을 만드는 cyclic, 그리고 그렇지 않은 Acyclic 그래프로 나뉠 수 있고

 

 

그래프를 표현하는 방법

-Adjacency Matrix (인접 행렬 방식)

: 그래프를 표에 표현하는 방식

노드끼리 연결이 되었다면 1, 그렇지 않다면 0을 표에 적어서 표현하는 방식이다.

 

-Adjacency list (인접 리스트 방식)

: 배열 방에 있는 모든 노드를 집어넣고 각 배열 방에 있는 해당 노드와 인접한 노드들을 linked list로 쭉 나열해서 저장하는 방식이다.

 

 

그래서 edge가 n 개라면, list에 들어간 총 node의 갯수는 2n 개라고 볼 수 있다.

 

 

 

Tree

 

트리는 노드로 구성된 계층적 자료구조이다.

즉 노드가 하나 이상의 자식을 가지면 트리라고 부른다.

최상위 노드를 root라고 하고, root node의 child를 추가하고, 그 child에 또 child를 추가하는 방식으로 구현할 수 있다.

트리의 맨 끝에 더이상 자식이 없는 노드를 leaf 라고 부른다.

 

 

 

 

binary tree (이진 트리)

자식이 최대 두 개 까지만 붙는 트리를 binary tree (이진 트리)라고 부른다.

이진 트리에는 세가지 종류가 있다.

 

출처 : https://sewonkimm.github.io/data%20structure/2019/09/12/Heap.html

full binary tree (정이진트리) : 노드의 자식이 하나도 없거나 2개인 트리 (1개는 안됨)

complete binary tree (완전이진트리) : 모든 노드들이 level 별로 왼쪽부터 채워진 트리

perfect binary tree (포화이진트리) : 양 쪽으로 빈공간 없이 모든 노드가 2개의 자식을 가지고 level도 정확하게 맞아 떨어진 피라미드 구조의 트리

 

binary search tree (이진 탐색 트리)

왼쪽 자식 노드가 현재 노드보다 작고 오른쪽 자식 노드가 현재 노드보다 크게 된 트리를  binary search tree (이진 탐색 트리)라고 부른다.

 

이진 탐색 트리의 탐색 방법에는 3 가지 방법이 있는데

 

전위순회 (preorder) : root -> left -> right

중위순회 (inorder) : left -> root -> right

후위순회 (postorder) : left -> right -> root

 

순으로 탐색하는 방법들이 있다.

 

연습 문제는 여기 참고!