5.3.1 그래프
정점과 간선
- 어떠한 곳에서 어떠한 곳으로 무언가를 통해 간다고 했을 때,
- '어떠한 곳' : 정점(vertex)
- '무언가' : 간선(edge)
- outdegree : 정점으로 나가는 간선
- indegree : 들어오는 간선
- 정점은 약자로 V 또는 U
- 정점과 간선으로 이루어진 집합 : 그래프(graph)
가중치
5.3.2 트리
- 그래프 중 하나로 그래프의 특징처럼 정점과 간선으로 이루어져 있고, 트리 구조로 배열된 일종의 계층적 데이터 집합
루트 노드
, 내부 노드
, 리프 노드
등으로 구성
- 트리로 이루어진 집합 : 숲
트리의 특징
- 부모, 자식 계층 구조를 가짐
- 5번은 6번과 7번의 부모이고, 6번과 7번은 5번의 자식
- V-1 = E
- 임의의 두 노드 사이의 경로는 '유일무이'하게 존재.
- 트리 내의 어떤 노드와 어떤 노드까지의 경로는 반드시 있다
트리의 구성
- 루트 노드
- 가장 위에 있는 노드
- 보통 트리 문제가 나오고 트리를 탐색할 때 루트 중심으로 탐색하면 쉽게 풀리는 경우가 많다
- 내부 노드
- 리프 노드
트리의 높이와 레벨
- 깊이 : 루트 노드부터 특정 토드까지 최단 거리로 갔을 때의 거리
- 높이 : 루트 노드부터 리프 노드까지 거리 중 가장 긴 거리
- 레벨 : 주어진 문제마다 조금씩 다르지만 보통 깊이와 같은 의미. 1번 노드를 0레벨, 2, 3노드를 1레벨 혹은 1번 노드를 1레벨, 2, 3노드를 2레벨이라 할 수 있다
- 서브트리 : 트리 내의 하위 집합
이진 트리
- 자식의 수가 두 개 이하인 트리
- 정이진 트리(full binary tree) : 자식 노드가 0 또는 두 개인 이진 트리
- 완전 이진 트리(complete binary tree) : 왼쪽에서부터 채워져 있는 이진 트리. 마지막 레벨을 제외하곤 모든 레벨이 완전히 채워져 있으며, 마지막 레벨의 경우는 왼쪽부터 채워져 있음
- 변질 이진 트리(degenerate binary tree) : 자식 노드가 하나밖에 없는 이진 트리
- 포화 이진 트리(perfect binary tree) : 모든 노드가 꽉 차 있는 이진 트리
- 균형 이진 트리(balanced binary tree) : 왼쪽과 오른쪽 노드의 높이 차이가 1 이하인 이진 트리. map, set을 구헝하는 레드 블랙 트리는 균형 이진 트리 중 하나이다
이진 탐색 트리(BST)
- 노드의 오른쪽 하위 트리에는 노드 값보다 큰 값이 있는 노드만 포함되고, 왼쪽 하위 노드에는 작은 값이 들어 있는 트리
- 검색을 하기에 용이
- 검색 보통 O(logN), 최악의 경우 O(n)
- 이진 탐색 트리는 삽입 순서에 따라 선형적일 수 있기 때문.
AVL 트리
- Adelson-Velsky and Landis tree
- 최악의 경우 선형적인 트리가 되는 것을 방지하고 스스로 균형을 잡는 이진 탐색 트리
- 두 자식 서브트리의 높이는 항상 최대 1만큼 차이난다
- 최악의 경우를 배제하고 항상 균형 잡힌 트리 -> AVL 트리
- 탐색, 삽입, 삭제 모드 O(logN)
- 삽입, 삭제를 할 때마다 균형이 안 맞는 것을 맞추기 위해 트리 일부를 왼쪽 혹은 오른쪽으로 회전시키며 균형을 잡음
레드 블랙 트리
- 균형 이진 탐색 트리
- 탐색, 삽입, 삭제 모두 O(logN)
- 각 노드는 빨간색 또는 검은색의 색상을 나타내는 추가 비트를 저장
- 삽입 및 삭제 중에 트리가 균형을 유지하도록 하는 데 사용
- 모든 리프 노드와 루트 노드는 블랙이고 어떤 노드가 레드이면 그 노드의 자식은 반드시 블랙이다
5.3.3 힙
- 완전 이진 트리 기반의 자료구조.
- 최대힙 : 루트 노드에 있는 키가 모든 자식에 있는 키 중에서 가장 큼. 각 노드의 자식 노드와의 관계도 이런 특징이 재귀적으로 이루어짐.
- 최소힙 : 루트 노드에 있는 키는 모든 자식에 있는 키 중에서 최솟값. 각 노드의 자식 노드와의 관계도 이와 같은 특징이 재귀적으로 이루어짐.
최대힙의 삽입
- 새로운 요소가 들어오면 일단 힙의 마지막 노드에 이어서 삽입
- 이 새로운 노드를 부모 노드들과의 크기를 비교하며 교환의 힙의 성질을 만족시킴
최대힙의 삭제
- 최댓값은 루트 노드이므로 루트 노드가 삭제되고, 그 이후 마지막 노드와 루트 노드를 스왑하여 또 다시 스왑 등의 과정을 거쳐 재구성
5.3.4 우선순위 큐
- 대기열에서 우선순위가 높은 요소가 우선순위가 낲은 요소보다 먼저 제공되는 자료 구조
- 힙을 기반으로 구현
5.3.5 맵
- 특정 순서에 따라 키와 매핑된 값의 조합으로 형성된 자료 구조
- 레드 블랙 트리 자료 구조를 기반으로 형성되고, 삽입하면 자동으로 정렬
- map<string, int> 형태로 구현 !
5.3.6 셋
- 특정 순서에 따라 고유한 요소를 저장하는 컨테이너
- 중복되는 요소 X
5.3.7 해시 테이블
- 무한에 가까운 데이터들을 유한한 개수의 해시 값으로 매핑한 테이블
- 삽입, 삭제, 탐색 시 평균적으로 O(1)
Reference
주홍철 작가님의 '면접을 위한 CS 전공지식 노트'를 기반으로 작성되었습니다.