비선형 자료구조: 일렬로 나열하지 않고 자료 순서나 관계가 복잡한 구조
예 - 트리, 그래프
그래프
정점과 간선으로 이루어진 자료구조
정점과 간선
어떠한 곳에서 어떠한 곳으로 무언가를 통해서 간다.
어떠한 곳: 정점(vertex)
무언가: 간선(edge)
단방향 간선, 양방향 간선이 있음
정점으로 나가는 간선: outdegree
정점으로 들어오는 간선: indegree
정점과 간선으로 이루어진 집합: graph
가중치: 간선과 정점 사이에 드는 비용
트리
그래프 중 하나로 정점과 간선으로 이루어져 있고 트리 구조로 배열된 일종의 계층적 데이터의 집합
루트노드, 내부 노드, 리프 노드 등으로 구성
트리의 특징
1.부모 - 자식 계층 구조
2. V - 1 = E 간선 수는 노드 수 - 1
3. 임의의 두 노드 사이의 경로는 '유일무이'하게 '존재'
트리 내의 어떤 노드와 어떤 노드까지의 경로는 반드시 있음
루트 노드
: 가장 위에 있는 노드 (보통 트리 문제가 나오고 트리를 탐색할 때 루트 노드를 중심으로 탐색하면 문제가 쉽게 풀리는 경우가 많다)
내부 노드
: 루트 노드와 내부 노드 사이에 있는 노드
리프 노드
: 자식 노드가 없는 노드
트리의 높이와 레벨
깊이: 트리의 깊이는 각 노드마다 다름
루트 노드부터 특정 노트까지 최단 거리로 갔을 때의 거리
높이: 루트 노드부터 리프 노드까지 거리 중 가장 긴거리
레벨: 깊이와 같은 의미
서브 트리: 트리 내의 하위 집합
이진 트리
: 자식의 노드 수가 두 개 이하인 트리
- 정이진 트리(full binary tree): 자식 노드가 0 또는 두 개인 이진 트리
- 완전 이진 트리(complete binary tree): 왼쪽에서부터 채워져 있는 이진트리. 마지막 레벨의 경우 왼쪽부터 채워져 있다
- 변질 이진 트리(degenerate binary tree): 자식 노드가 하나밖에 없는 이진 트리
- 포화 이진 트리(perfect binary tree): 모든 노드가 꽉 차 있는 이진 트리
- 균형 이진 트리(balanced binary tree): 왼쪽과 오른쪽 노드의 높이 차이가 1 이하인 이진트리 map, set을 구성하는 레드 블랙 트리는 균형 이진 트리 중 하나임
이진 탐색 트리
: 노드의 오른쪽 하위 트리에는 '노드 값보다 큰값'이 있는 노드만 포함
왼쪽 하위 트리에는 '노드 값보다 작은 값'이 들어있는 트리
왼쪽 및 오른쪽 하위 트리 해당 특성을 가짐
-> '검색'을 하기에 용이
왼쪽에는 작은 값 / 오른쪽에는 큰 값이 정해져 있기 때문에 10을 찾으려고 한다면 25의 왼쪽 노드들만 찾으면 됨
보통 이지만 최악의 경우 이 걸린다.
-> 이진 탐색 트리는 삽입 순서에 따라 선형적일 수 있기 떄문
AVL 트리
AVL 트리(Adelson-Velsky and Landis tree)는 선형적 트리가 되는 것을 방지하고 스스로 균형을 잡는 이진 탐색 트리이다.
두 자식 서브 트리의 높이는 항상 최대 1만큼 차이가 난다.
탐색, 삽입, 삭제:
삽입, 삭제를 할 때마다 균형이 안 맞는 것을 맞추기 위해 트리 일부를 왼쪽 혹은 오른쪽으로 회전시키며 잡음
레드 블랙 트리
균형 이진 탐색 트리.
탐색, 삽입, 삭제:
각 노드는 빨간색 또는 검은색의 색상을 나타내는 추가 비트를 저장
삽입 및 삭제 중 트리가 균형을 유지하도록 사용됨
"모든 리프 노드와 루트 노드는 블랙이고 어떤 노드가 레드이면 그 노드의 자식은 반드시 블랙이다"등의 규칙을 기반으로 균형을 잡는 트리
힙
완전 이진 트리 기반의 자료구조
- 최대힙: 루트 노트에 있는키는 모든 자식에 있는 키 중에서 가장 커야 한다. 또한 각 노드의 자식 노드와의 관계도 이와 같은 특징이 재귀적으로 이루어져야 함
- 최소힙: 최소힙에서 루트 노드에 있는 키는 모든 자식에 있는 키 중에서 최솟값이어야 한다. 각 노드의 자식 노드와의 관계에서도 이 특징이 재귀적으로 이루어져야 함
최대힙의 삽입
: 새로운 노드를 힙의 마지막 노드에 이어서 삽입
새 노드를 부모 노드들과의 크기를 비교하며 교환
최대힙의 삭제
: 최댓값은 루트 노드이므로 루트 노드가 삭제되고 마지막 노드와 루트 노드를 스왑
우선순위 큐
우선순위 대기열이라고도 하며 대기열에서 우선순위가 높은 요소가 우선순위가 낮은 요소보다 먼저 제공되는 자료구조
힙을 기반으로 구현된다.
맵
특정 순서에 따라 키와 매핑된 값의 조합으로 형성된 자료 구조
"이승철": 1, "박동영": 2 (키: value)
래드 블랙 트리 자료 구조를 기반으로 형성
삽입되면 자동으로 정렬됨
셋
특정 순서에 따라 고유한 요소를 저장하는 컨테이너
중복되는 요소는 없고 오로지 희소한 값만 저장하는 자료구조
해시 테이블
무한에 가까운 데이터들을 유한한 개수의 해시 값으로 매핑한 테이블
삽입, 삭제, 탐색:
