Graph & Tree

Syoee·2023년 12월 3일

Graph algorithm tree

Algorithm

목록 보기

3/6

Graph

Graph는 노드와 edge의 관계를 나타내는 추상적인 개념입니다.

특징

• 노드(node) 는 일반적으로 점으로 표시됩니다.
도시를 나타내는 노드는 지도에서 점으로 표시됩니다.

• edge는 노드 사이의 관계를 나타냅니다.
ex ) 도로망에서 edge는 도로를 나타냅니다.

• edge는 방향성이 없는 경우를 undirected graph, 방향성이 있는 경우를 directed graph라고 합니다.

• edge에 가중치(weight)가 있을 수도 있습니다.
ex ) 길이 또는 비용을 나타내는 값이 할당될 수 있습니다.

• Graph는 매우 다양한 형태로 사용됩니다.
네트워크, 지도, 계획, 추상 데이터 구조 등에서 사용됩니다.
또한 그래프 이론은 최단 경로, 흐름, 컷 등과 같은 다양한 문제를 연구합니다.

Tree

Tree는 노드와 edge의 집합으로 이루어져 있습니다.

특징

• Tree는 비순환 그래프입니다.
즉, 어떤 노드에서 시작하여 어떤 다른 노드로 이동할 때, 한 번 이상 이동하지 않고 도달할 수 있는 모든 노드의 집합이 하나의 트리를 형성합니다.
• Tree는 하나의 루트 노드(root node)가 있습니다.
루트 노드는 트리의 가장 상위 노드로, 다른 모든 노드는 루트 노드에서부터 시작하는 경로 상에 있습니다.
• 루트 노드를 제외한 모든 노드는 단 하나의 부모 노드(parent node)를 갖습니다.
• 부모 노드와 자식 노드(child node)라는 용어를 사용합니다.
부모 노드는 자식 노드를 가지지만, 자식 노드는 부모 노드를 가지지 않습니다.
• 트리에서 노드의 깊이(depth)는 루트 노드에서부터 해당 노드까지의 edge의 수입니다.
• 트리에서 노드의 레벨(level)은 트리에서 루트 노드로부터 몇 번째 레벨에 있는지를 나타냅니다.
즉, 루트 노드의 레벨은 0이며, 레벨이 1인 노드는 루트 노드의 자식 노드입니다.
• 트리는 여러 종류의 트리가 존재하며, 대표적인 것으로 이진 트리, 이진 탐색 트리, AVL 트리, 레드-블랙 트리 등이 있습니다.
• 이진 트리(Binary Tree)는 각 노드가 최대 두 개의 자식 노드를 가지는 트리입니다.
이진 트리는 탐색, 정렬, 암호화, 해시 테이블 등 다양한 분야에서 사용됩니다.
• 이진 탐색 트리(Binary Search Tree)는 이진 트리의 일종으로, 모든 노드에서 왼쪽 서브트리의 값이 부모 노드의 값보다 작고, 오른쪽 서브트리의 값이 부모 노드의 값보다 큰 속성을 만족합니다.
이진 탐색 트리는 탐색, 정렬, 범위 검색 등에서 사용됩니다.
• AVL 트리(AVL Tree)는 균형 이진 탐색 트리의 일종으로, 모든 노드의 서브트리 높이 차이가 1 이하인 속성을 만족합니다.
AVL 트리는 탐색, 정렬 등에서 사용됩니다.
• 레드-블랙 트리(Red-Black Tree)는 균형 이진 탐색 트리의 일종으로, 모든 노드가 레드 또는 블랙인 속성을 만족합니다.
레드-블랙 트리는 키를 기반으로 하는 검색 구조, 맵 및 딕셔너리와 같은 데이터 구조에서 사용됩니다.