트리
-
나무를 거꾸로 뒤집은 형태의 구조
-
단방향 그래프의 한 구조
-
데이터가 바로 아래에 있는 하나 이상의 데이터에 무방향으로 연결된 계층적 자료구조
-
데이터가 순차적으로 나열된 선형 구조가 아닌 여러 개의 데이터가 존재할 수 있는 비선형 구조
이미지 출처 링크
- 깊이
depth: 루트로부터 하위 계층의 특정 노드까지의 깊이를 표현 가능- 레벨
Level: 같은 깊이를 가지고 있는 노드를 묶어 레벨로 표현 가능
- 같은 레벨의 노드를 형제 노드
Sibling Node라고 부름- 높이
Height: 리프 노드를 기준으로 루트까지의 높이르 표현 가능
용어 정리
-
노드(Node)
트리 구조를 이루는 모든 개별 데이터 -
루트(Root)
트리 구조의 시작점이 되는 노드 -
부모 노드(Parent node)
두 노드가 상하관계로 연결되어 있을 때 상대적으로 루트에서 가까운 노드 -
자식 노드(Child node)
두 노드가 상하관계로 연결되어 있을 때 상대적으로 루트에서 먼 노드 -
리프(Leaf)
트리 구조의 끝 지점이고, 자식 노드가 없는 노드
실사용 예시
-
컴퓨터 디렉토리 구조
-
대진표
-
가계도 등
이진 탐색 트리
-
자식 노드가 최대 두 개인 노드들로 구성된 트리
-
자식 노드는 왼쪽, 오른쪽 자식 노드로 나뉨
-
모든 왼쪽 자식의 값이 루트나 부모보다 작으며, 모든 오른쪽 자신이 루트나 부모보다 큰 값을 가지는 특징을 가짐
-
균형 잡힌 트리가 아닐 때, 입력되는 값의 순서에 따라 한쪽으로 노드가 몰리게 되는데 균형 잡힌 트리가 아닐 때 시간이 더 걸리는 경우가 생김
| 이진 트리 종류 | 설명 |
|---|---|
| 정 이진 트리 (Full binary tree) | 각 노드가 0 개 혹은 2개의 자식 노드를 가짐 |
| 포화 이진 트리 (Perfect binary tree) | 정 이진 트리이면서 완전 이진 트리인 경우로 모든 리프 노드의 레벨이 동일하고, 모든 레벨이 가득 채워져 있는 트리 |
| 완전 이진 트리 (Complete binary tree) | 마지막 레벨을 제외한 모든 노드가 가득 차 있어야 하고, 마지막 레벨의 노드는 전부 차 있지 않아도 되지만 왼쪽이 채워져야 함 |
이미지 출처 링크
그래프
-
자료구조의 그래프는 일상적으로 사용하는 그래프와는 다르다
-
여러개의 점들이 복잡하게 연결되어 있는 관계를 표현한 자료 구조
-
직접적인 관계의 경우 두 점 사이를 이어주는 간선이 있음
-
간접적인 관계는 몇 개의 정점과 간선에 걸쳐 이어짐
-
하나의 점을
정점, 하나의 선을간선이라고 함
그래프의 표현 방식
인접 행렬
- 2차원 배열의 형태로 그래프를 표시하는 것
- 한 개의 큰 표와 같은 모습을 한 인접 행렬은 두 정점 사이에 관계가 있는지, 없는지 확인하기에 용이
- 가장 빠른 경로를 찾고자 할 때 사용
인접 리스트
- 각 정점이 어떤 정점과 인접하는지를 리스트의 형태로 표현
- 각 정점마다 하나의 리스트를 가지며, 이 리스트는 자신과 인접한 다른 정점을 담는다.
- 메모리를 효율적으로 사용하고 싶을 때 사용
이미지 출처 링크
그래프 용어
-
정점 (vertex)
노드(node)라고도 하며 데이터가 저장되는 그래프의 기본 원소 -
간선 (edge)
정점 간의 관계를 표현 (정점을 이어주는 선) -
인접 정점 (adjacent vertex)
하나의 정점에서 간선에 의해 직접 연결되어 있는 정점 -
가중치 그래프 (weighted Graph)
연결의 강도(추가적인 정보)가 얼마나 되는지 적혀져 있는 그래프를 말함 -
비가중치 그래프 (unweighted Graph)
연결의 강도가 적혀져 있지 않는 그래프를 말함 -
방향 그래프 (undirected graph)
정점 A에서 정점 B로, 정점 B에서 정점 A로 방향에 상관 없이 갈 수 있는 그래프를무방향 그래프라고 하며, 방향이 정해진 그래프를단방향 그래프라고함 -
진입차수 (in-degree) / 진출차수 (out-degree)
한 정점에진입(들어오는 간선)하고진출(나가는 간선)하는 간선이 몇 개인지를 나타냄 -
인접 (adjacency)
두 정점 간에 간선이 직접 이어져 있으면 두 정점은 인접한 정점 -
자기 루프 (self loop)
정점에서 진줄하는 간선이 곧바로 자기 자신에게 진입하는 경우를자기 루프를 가졌다라고 표현, 다른 정점을 거치지 않는 것이 특징 -
사이클 (cycle)
한 정점에서 출발하여 다시 돌아올 수 있다면사이클이 있다라고 표현
