비선형 구조란?
- 데이터를 비연속적으로 연결한 자료 구조
- 비선형 구조 의 종류 : 트리, 그래프
트리(Tree)
- 데이터들을 계층화시킨 자료 구조
- 인덱스를 조작하는 방법으로 가장 많이 사용되는 구조
- 노드
Node 와 노드를 연결하는 링크 Link 로 구성
- 배열과 달리 노드들이 포인터로 연결되어 노드의 상한선이 없음
트리 용어
- 루트 노드
Root Node : 최상위 노드, 트리의 시작점, {P}
- 단말 노드
Leaf Node : 자식이 없는 노드, 트리의 가장 말단, {E, F, G, H, I}
- 레벨
level : 루트 노드를 기준으로 특정 노드까지의 경로 길이, E의 레벨 5
- 조상 노드
Ancestor Node : 특정 노드에서 루트에 이르는 경로상 모든 노드, M의 조상 노드 {C, R, P}
- 자식 노드
Child Node : 특정 노드에 연결된 다음 레벨의 노드, L의 자식 노드 {E, F, G}
- 부모 노드
Parent Node : 특정 노드에 연결된 이전 레벨의 노드, E의 부모 노드 {L}
- 형제 노드
Sibling : 같은 부모를 가진 노드, G의 형제 노드 {E, F}
- 깊이
Depth : 루트 노드에서 특정 노드에 도달하기 위한 간선의 수, 트리의 깊이 4
- 차수
Degree : 특정 노드에 연결된 자식 노드의 수, M의 차수 2
트리 종류
- 이진 탐색 트리
Binary Search Tree
- 여러 개의 노드가 트리 형태로 연결된 구조로, 루트 노드라에서 부터 시작해서 각 노드에 최대 2개의 노드를 연결할 수 있는 구조
- 부모 노드보다 작은 값은 왼쪽에, 부모 노드보다 큰 값은 오른쪽 노드에 생성
- 오른차순 : 왼쪽 마지막 노드에서부터 오른쪽 마시막 노트까지 [왼쪽 노드 -> 부모 노드 -> 오른쪽 노드] 순
- 내림차순 : 오른쪽 마지막 노드에서부터 왼쪽 마지막 노드까지 [오른쪽 노드 -> 부모 노드 -> 왼쪽 노드] 순
- 이진 탐색 트리가 범위 검색이 쉬운 이유는 값들이 정렬되어 있어 그룹핑이 쉽기 때문
- 트리의 경우 노드가 왼쪽이나 오른쪽 한 곳만 존재하게 될 경우 효율이 떨어져 균형이 잡히지 않았다 고 한다.
- 균형이 잡히지 않은 이진 탐색 트리는 효율이 떨어질 수 있기 때문에 AVL, 2-3, 레드-블랙 트리를 통해 전체 트리의 균형을 맞춘다.
- AVL 트리
Adelson-Velsky and Landis Tree
- 두 자식 서브 트리의 높이는 항상 최대 1만큼만 차이가 나도록 스스로 균형을 잡는 이진 탐색 트리
- 2-3 트리
2-3 Tree
- 차수가 2 또는 3 인 내부 노드를 갖는 탐색 트리
- 레드-블랙 트리
Red-Black Tree
- 각 노드는 빨강 또는 검정의 색상을 가지고 있으며, 색깔에 따른 규칙을 통해 스스로 균형을 잡는 이진 탐색 트리
그래프
- 노드
Node 와 노드를 연결하는 간선 Edge 을 하나로 모아 놓은 자료 구조
- 그래프에 사이클이 없으면 트리이다.
- 그래프 용어
- 경로
Path : 임의 정점에서 다른 정점으로 가는 길
- 경로 길이
Path Length : 경로상 있는 간선의 수
- 단순 경로
Simple Path : 한 경로의 모든 간선이 다를 때의 경로
- 사이클
Cycle : 동일 정점에서 시작과 끝이 이어지는 경로
방향 그래프
- 정점을 연결하는 선에 방향이 있는 그래프
- n개의 정점으로 구성된 방향 그래프의 최대 간선수는 n(n-1)
무방향 그래프
- 정점을 연결하는 선에 방향이 없는 그래프
- n개의 정점으로 구성된 무방향 그래프의 최대 간선 수는 n(n-1)/2
그래프 탐색방법
- 깊이 우선 탐색
DFS; Depth-First Search : 최대한 깊이 내려간 뒤, 더 이상 내려 갈 곳이 없을 경우 옆으로 이동
- 너비 우선 탐색
BFS; Breadth-First Search : 최대한 넓게 이동한 다음, 더 이상 갈 수 없을 때 아래로 이동
댓글남기기