5.3 비선형 자료 구조

5.3.1 그래프

• 정점과 간선으로 이루어진 자료 구조

정점과 간선

• 어떠한 곳에서 어떠한 곳으로 무언가를 통해 간다고 했을 때,
  • '어떠한 곳' : 정점(vertex)
  • '무언가' : 간선(edge)
    
    
• outdegree : 정점으로 나가는 간선
• indegree : 들어오는 간선
• 정점은 약자로 V 또는 U
• 정점과 간선으로 이루어진 집합 : 그래프(graph)

가중치

• 간선과 정점 사이에 드는 비용

5.3.2 트리

• 그래프 중 하나로 그래프의 특징처럼 정점과 간선으로 이루어져 있고, 트리 구조로 배열된 일종의 계층적 데이터 집합
• 루트 노드, 내부 노드, 리프 노드 등으로 구성
• 트리로 이루어진 집합 : 숲

트리의 특징

1. 부모, 자식 계층 구조를 가짐
   • 5번은 6번과 7번의 부모이고, 6번과 7번은 5번의 자식
2. V-1 = E
   • 간선 수는 노드 수 - 1
3. 임의의 두 노드 사이의 경로는 '유일무이'하게 존재.
   • 트리 내의 어떤 노드와 어떤 노드까지의 경로는 반드시 있다

트리의 구성

• 루트 노드
  • 가장 위에 있는 노드
  • 보통 트리 문제가 나오고 트리를 탐색할 때 루트 중심으로 탐색하면 쉽게 풀리는 경우가 많다
• 내부 노드
  • 루트 노드와 내부 노드 사이에 있는 노드
• 리프 노드
  • 자식 노드가 없는 노드

트리의 높이와 레벨

• 깊이 : 루트 노드부터 특정 토드까지 최단 거리로 갔을 때의 거리
• 높이 : 루트 노드부터 리프 노드까지 거리 중 가장 긴 거리
• 레벨 : 주어진 문제마다 조금씩 다르지만 보통 깊이와 같은 의미. 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 전공지식 노트'를 기반으로 작성되었습니다.