IM 7일차 TIL ( graph, tree & Binary Search Tree)

TIL(Today I Learned )

지에스정 2020. 5. 7. 01:02

Graph

그래프는 정점(Vertex)와 각 정점을 연결하는 변(Edge)로 나누어 진다.

변은 해당 정점들을 연결하여 자료를 탐색할 수 있게 만들어 준다.

변에는 방향성이 있는 변이 있고, 방향성이 없는 변이 있다.

방향성이 있는 변을 가지는 그래프를 유향 그래프라고 하며, 정점에서 해당 변의 방향만을 따라서 연결된 정점으로 이동 가능하다.

방향성이 없는 변을 가지는 그래프는 무방향 그래프라고 하며, 연결된 정점들 끼리 왕래할 수 있다.

각 정점들을 서로 연결하여 순환할 수 있는 것이 가장 큰 특징이다.

그래프의 구조는 SNS에서 가장 많이 사용되며, 통신망이나 친구관계등을 모델링할 수 있다.

Tree

트리구조는 그래프의 자료구조에 속하지만 그래프와는 다른 특징을 가진다.

그래프는 순환 구조를 가질 수 있지만, 트리는 순환 구조를 가질 수가 없다.

트리는 부모 노드와 자식 노드로 연결되어 있는 특징을 가지고 있기 때문이다.

부모가 없는 최상위 노드를 루트(root) 라고 표현 하며, 루트의 경로를 깊이(depth)라고 한다.

루트 노드(1) 부터 노드까지 연결된 엣지 수의 합을 레벨(level)이라고 한다.

가장 긴 노드 경로의 길이를 높이(height)라고 한다.

그리고 자식이 없는 노드를 리프(leaf)라고 한다.

Binary Search Tree

이진탐색트리는 트리의 일종으로 부모가 2개의 자식만 가지는 특징을 가진다.

이 자식들은 부모보다 작은 경우 왼쪽으로, 큰 경우는 오른쪽으로 배치된다.

트리를 탐색하기 위해서는 순회를 통해 탐색하며, 순회에는 4가지가 있다.

전위 순회는 노드 탐색 후 왼쪽 전위 순회를 한 후 오른쪽 전위 순회를 한다.

중위 순회는 왼쪽 서브 트리를 중위 순회한 후 노드 방문 후 오른쪽 전위 순회를 한다.

후위 순회는 왼쪽 서브 트리를 후위 순회 하고 오른쪽 후위 순회 하고 노드를 방문한다.

레벨 순서 순회는 낮은 레벨 부터 순회 한다.

위 그림을 순회하면 다음과 같다.