Tree
단방향 그래프의 한 구조로 하나의 뿌리로 가지가 사방으로 뻗은 형태. 하나의 데이터 아래로 여러 개의 데이터가 존재할 수 있는 비선형 구조.
-
깊이(depth) : 루트가 0. 밑으로 갈수록 1, 2, 3....
-
레벨(Level) : 루트가 level1, 밑으로 갈수록 2,3....
-
높이(height) : 리프 노드로부터 루트까지 높이 표현. 부모노드는 가장 높은 height값 가진 자식노드 +1
-
서브트리(subtree) : 트리 내 트리구조 갖춘 작은 트리
-
예) 컴퓨터 디렉토리 구조, 가계도
용어 정리
노드(Node) : 트리 구조를 이루는 개별 데이터
루트(Root) : 트리 구조의 시작점 노드
부모 노드(Parent node) : 두 노드가 상하관계로 연결되어 있을 때 상대적으로 루트에서 가까운 노드
자식 노드(Child node) : 두 노드가 상하관계로 연결되어 있을 때 상대적으로 루트에서 먼 노드
리프 노드(Leaf) : 트리 구조의 끝 지점이고, 자식 노드가 없는 노드
트리순회(Tree traversal)
트리의 모든 노드를 한 번씩 방문하는 것을 의미한다.
트리 순회하는 방법에는 전위 순회, 중위 순회, 후위 순회 3가지 방법이 있다.
(트리 구조에서 노드를 순차적으로 조회할 때의 순서는 항상 왼쪽부터 오른쪽으로)
전위 순회 (preorder traverse) :
1. 노드를 방문한다.
2. 왼쪽 서브 트리를 전위 순회한다.
3. 오른쪽 서브 트리를 전위 순회한다
중위 순회 (inorder traverse) :
1. 왼쪽 서브 트리를 중위 순회한다.
2. 노드를 방문한다.
3. 오른쪽 서브 트리를 중위 순회한다.
후위 순회 (postorder traverse) :
1. 왼쪽 서브 트리를 후위 순회한다.
2. 오른쪽 서브 트리를 후위 순회한다.
3. 노드를 방문한다.
Graph
여러 개의 점들이 서로 복잡하게 연결되어 있는 관계를 표현한 자료구조
-
하나의 점을 그래프에서는 정점(vertex)이라하고, 선은 간선(edge)이라고 합니다.
-
인접행렬 : 서로 다른 정점들이 인접한 상태인지를 표시한 행렬로 2차원 배열 형태로 나타냄. 이어져 있으면 1(true), 아니면 0(false)으로 표시한 표
가장 빠른 경로를 찾고자 할 때 주로 사용
- 인접리스트 : 각 정점이 어떤 정점과 인접하는지를 리스트의 형태로 표현. 메모리 효율적으로 사용하고 싶을 때 사용한다
(인접행렬은 연결 가능한 모든 경우의 수 저장해서 메모리 많이 차지)
- 예) 네비게이션
용어정리
정점(vertex) : 노드라고도 하며 데이터가 저장되는 그래프의 기본 원소
간선(edge) : 정점을 이어주는 선
인접 정점(adjacent vertex) : 간선에 의해 직접 연결되어 있는 정점
가중치 그래프(weighted Graph) : 연결의 강도(추가적인 정보)가 얼마나 되는지 적혀져 있는 그래프
비가중치 그래프(unweighted Graph) : 연결의 강도가 적혀져 있지 않는 그래프
무(방)향 그래프(undirected graph) : 단방향 그래프
진입차수(in-degree) / 진출차수(out-degree) : 한 정점에 진입(들어오는 간선)하고 진출(나가는 간선)하는 간선이 몇 개인지를 나타냄
자기 루프(self loop) : 정점에서 진출하는 간선이 곧바로 자기 자신에게 진입하는 경우
사이클(cycle) : 한 정점에서 출발하여 다시 해당 정점으로 돌아갈 수 있다면 사이클이 있다고 표현
