Graph

그래프라고 하면 익히 수학에서 다루는 x축과 y축을 가진 그래프를 떠올릴 수 있다. 그러나 컴퓨터 공학에서 다루는 자료구조 그래프는 마치 거미줄처럼 여러개의 점들이 선으로 이어져 있는 복잡한 네트워크 망과 같은 모습을 하고 있다.

이 그래프는 정점(vertex)과 간선(edges)을 가지는데, 정점은 그래프에서 하나의 점이며, 간선은 이 점들을 잇는 선들을 말한다. 그래프는 간선이 방향을 가지고 있느냐에 따라 두 가지 종류로 나뉘는데, 일정 방향이 존재한다면 단방향(directed) 그래프, 방향이 없이 단순히 서로 이어져 있기만 하다면 무(방)향 그래프(undirected graph)라고 한다. 이 외에 두 정점 사이 간선 연결의 정도가 얼마나 되는지의 정보를 포함하고 있는 그래프를 가중치 그래프라고 하며, 두 정점 사이가 연결되어 있다는 정보 외에 다른 정보를 가지고 있지 않은 그래프는 비가중치 그래프라고 한다.

그래프와 관련하여 인접 행렬 및 인접 리스트에 관한 내용은 다음 업로드에서 자세히 다뤄볼 예정이다.

Tree

트리 구조는 자바스크립트로 html 문서를 조작하는 DOM에서도 자주 접했던 구조라서 다른 자료구조들 보다는 조금 친숙했던 것 같다. 트리 구조는 이름 그대로 나무의 형태와 비슷하다. 그래프의 여러 구조 중 무방향 그래프의 한 종류로, 하나의 뿌리로부터 가지가 사방으로 뻗은 형태가 나무와 닮아 있다고 하여 트리 구조라고 부른다. 트리 구조는 데이터가 바로 아래에 있는 하나 이상의 데이터에 무방향으로 연결된 계층적 자료구조이다. 따라서 트리 구조는 루트(Root) 라는 하나의 꼭짓점 데이터를 시작으로 여러 개의 데이터를 간선으로 연결하며 부모 노드(Parent Node) 와 자식 노드(Child Node) 가 존재하고, 같은 계층에 존재하는 노드는 형제 노드(Sibling) 라고 부른다.

Binary Search Tree(BST)

많은 트리 종류 중 가장 간단하고 많이 사용하는 트리 구조가 바로 이진 탐색 트리(Binary Search Tree)이다.
이진 트리는 한 부모 노드 당 자식 노드가 왼쪽 오른쪽 각 하나씩 총 두 개인 트리 구조이다. 이진 탐색 트리는 모든 왼쪽 자식 노드의 값이 루트나 부모 노드의 값보다 작고, 모든 오른쪽 자식 노드의 값이 루트나 부모 노드의 값보다 큰 값을 가지는 특징이 있다. 이진 탐색 트리를 이용한 알고리즘 중 가장 대표적인 알고리즘이 '숫자 맞추기 게임'인데, 진행자가 가진 숫자가 어떤 숫자인지 up & down으로 범위를 점점 좁혀가며 맞추는 게임이다. 자세한 알고리즘은 후에 따로 업로드 할 예정이다.