🙇🏻‍♂️

graph 란?

내가 알고 있던 그래프라고 하면 수학 시간에 함수에서 배웠던 그래프였다.
하지만, 프로그래밍에서는 수학 시간에 배운 그래프만을 그래프라고 하지 않았다.
어떠한 자료들 사이의 관계를 표현하기 위한 방법(?)들을 그래프라고 한ㄷ...

graph로 할 수 있는 것

앞서 언급한 바와 같이 그래프는 관계를 표현하기 위한 구조이다.

👥 사람 사이의 관계를 표현
🚊 지하철 노선
🚌 버스 노선
✈️ 항공 노선
🚢 해운 노선
etc

위와 같이 그래프 구조는 다양한 곳에서 사용되고 있다.
얼굴책, 인별그램에서도 위와 같은 자료 구조를 사용해서 팔로잉 관계를 구현하고 있다.

graph를 활용한 사람 사이의 관계

지하철 노선 사이의 관계

주요 개념

❓ 차수: 무방향 그래프에서 한 자료가 다른 자료와 연결된 선(edges)의 수
❓ 진입 차수: 방향성 그래프에서 from 노드에서 to 노드로 연결된 선(edges)의 수
❓ 진출 차수: 방향성 그래프에서 to 노드에서 from 노드로 연결된 선(edges)의 수

지하철 노선과 graph 형태에서는 edge로 역과 역 사이의 거리 or 소요 시간을 나타낼 수 있다.

tree란?

tree란 나무와 같이 하나의 뿌리(root)에서 시작해 여러 갈래의 가지(child)를 가지는 구조를 말한다. 가장 흔하게 접할 수 있는 트리 구조로는 돔 트리 구조가 있다.

돔 트리 구조

트리구조

주요 개념

❓ 노드: 트리의 구성 요소 (그림에서의 각각의 원)
❓ root: 최상단에 존재하는 노드 (모든 노드의 뿌리 역할)
❓ depth: 루트를 기준으로 다른 노드에 접근하는 거리
❓ sibling: 같은 부모 노드를 가지면서 같은 depth에 있는 노드들의 관계
❓ edge: 노드와 노드를 잇는 선
❓ leaf: 자식이 없는 노드

binary search tree란?

이진트리 중에 하나로 이진트리에서 탐색을 빠르게 할 수 있도록 재가공한 형태를 나타낸다. 일반적인 이진 트리로 구성된 경우에는 자식 노드를 설정할때에 어떤 조건도 없지만 binary search tree로 자료 구조를 형성할 경우에는 노드를 연결할때에 조건이 생기게 된다.

이진 트리

바이너리 서치 트리

위와 같이 이진 트리에서는 정해진 조건없이 부모와 자식 관계를 형성해 줄 수 있지만, 바이너리 서치 트리에서는 좌측엔 부모 노드보다 작은 value가 우측엔 부모 노드보다 큰 value가 자리 잡게 된다.