5.3 비선형 자료구조

'면접을 위한 CS 전공지식 노트' 책을 보며 공부한 내용입니다.

그래프

• 정점과 간선으로 이루어진 자료 구조
  • 간선(edge), 정점(vertex)
  • 단방향 간선이 있고, 양방향 간선이 있다.
• 정점에서 나가는 간선을 해당 정점의 outdegree, 들어오는 간선을 indegree라고 한다.
• 정점은 약자로 V나 U라고 하며, 어떤 정점으로부터 시작해서 어떤 정점까지 간다는 것을 "U에서 V로 간다"라고 한다. 
• 가중치: 간선과 정점 사이에 드는 비용

트리

• 그래프 중 하나로 그래프의 특징처럼 정점과 간선으로 이루어져 있지만, 트리 구조로 배열된 계층적 데이터의 집합이다. 
• 루트 노드, 내부 노드, 리프 노드 등으로 구성된다.
• 참고로, 트리로 이루어진 집합을 숲이라고 한다 .
• 특징
  • 부모, 자식 계층 구조
  • V = E - 1
  • 임의의 두 노드 사이의 경로는 유일무이하게 존재한다. 즉, 트리 내의 어떤 노드와 어떤 노드까지의 경로는 반드시 존재한다. 
• 트리의 높이와 레벨
  • 깊이
    • 각 노드마다 다르다. 루트 노드부터 특정 노드까지 최단 거리로 갔을 때의 거리
  • 높이
    • 루트  노드부터 리프노드까지 거리 중 가장 긴 거리
  • 레벨
    • 보통 깊이와 같은 의미로 씀. 루트 노드가 레벨 0이면, 그 자식은 레벨 1이고, 루트 노드가 레벨 1이면, 그 자식은 레벨 2이다.
  • 서브 트리
    • 트리 내의 하위 집합. 트리 내에 있는 부분 집합

• 이진 트리
  • 자식 노드 수가 두개 이하인 트리
  • 정이진트리(full binary tree)
    • 자식 노드의 수가 0 또는 2인 이진 트리
  • 완전 이진 트리(complete binary tree)
    • 왼쪽에서부터 채워져 있는 이진 트리.
    • 마지막 레벨을 제외하고는 모든 레벨이 완전히 채워져 있고, 마지막 레벨은 왼쪽부터 채워져 있다.
  • 변질 이진 트리(degenerate binary tree)
    • 자식 노드가 하나밖에 없는 이진 트리
  • 포화 이진 트리(perfect binary tree)
    • 모든 노드가 꽉 차있는 이진 트리
  • 균형 이진 트리(balanced binary tree)
    • 왼쪽과 오른쪽의 높이 차이가 1 이하인 이진 트리
    • map, set을 구성하는 레드블랙트리는 균형 이진 트리 중 하나 
• 이진 탐색 트리(BST)
  • 노드의 오른쪽 하위 트리에는 '노드보다 큰 값', 왼쪽 하위 트리에는 '노드보다 작은 값'이 들어간다.
  • 왼쪽 및 오른쪽 하위 트리도 같은 특정은 가진다.
  • => 검색에 용이
  • 요소 탐색에 O(logn)이지만, 최악의 경우에는 O(n)이 걸린다.
    • 최악의 경우는 삽입 순서에 따라 선형 구조로 될 때. 
• AVL 트리
  • BST에서 최악의 경우인 선형적인 트리가 되는 것을 방지한다.
  • 스스로 균형을 잡는 이진 탐색 트리이다.
  • 특징
    • 두 자식 서브 트리의 높이는 항상 최대 1만큼 차이가 난다.
    • 탐색, 삽입, 삭제 모두 O(logn)
    • 삽입, 삭제마다 균형을 맞추기 위해 트리 일부를 왼쪽/ 오른쪽으로 회전한다. 
• 레드블랙트리
  • 균형 이진 탐색 트리로, 탐색, 삽입, 삭제 모두 O(logn)이다.
  • 각 노드는 빨강, 검정을 나타내는 추가 비트를 저장하며, 삽입 및 삭제 중에 트리가 균형을 유지하도록 하는데 사용한다.
  • C++ STL의 set, multiset, map, multimap이 레드블랙트리로 구현되었다.
  • "모든 리프 노드와 루트 노드는 블랙, 어떤 노드가 레드이면, 그 자식은 반드시 블랙이다." 등의 규칙으로 균형을 잡는 트리이다.

힙

• 완전 이진 트리 기반의 구조이다.
• 최대힙
  • 루트 노드에 있는 키는 모든 자식에 있는 키 중 가장 커야 한다.
  • 또한, 각 노드의 자식 노드와의 관계도 이와 같은 특징이 재귀적으로 이루어져야 한다.
• 최소힙
  • 루트 노드에 있는 키는 모든 자식에 있는 키 중에서 최솟값이어야 한다.
  • 또한, 각 노드의 자식 노드와의 관계도 이와 같은 특징이 재귀적으로 이루어져야 한다.

우선 순위 큐

• 대기열에서 우선 순위가 높은 요소가 우선 순위가 낮은 요소보다 먼저 제공된다.
• 힙을 기반으로 구현되었다.

맵

• 특정 순서에 따라 키와 매핑된 값의 조합으로 형성된 자료구조이다.
• 레드블랙트리 기반으로 구현되었다.
• 키: 값

해시테이블

• 무한에 가까운 데이터들을 유한한 개수의 해시 값으로 매핑한 테이블이다.
• 삽입, 삭제, 탐색 시 평균적으로 O(1)
• unordered_map으로 구현되었다.

 

---

예상 질문

 

Q. 해시 테이블을 설명하세요

해시테이블은 무한에 가까운 데이터들을 유한한 개수의 해시값으로 매핑하여 저장하는 테이블이다.

이를 통해, 작은 크기의 캐시 메모리로도 프로세스를 관리하도록 할 수 있다.

 

Q. 그래프와 트리의 차이

그래프는 정점과 간선으로 이루어진 자료 구조이다. 트리도 정점과 간선으로 이루어진 자료구조이지만, 트리 구조로 계층적인 구조를 가지고 있다. 또한, 루트 노드와 내부 노드, 리프 노드 등으로 구성되며, V - 1 = E의 특징을 가지고 있다.

 

Q. 이진 탐색 트리는 어떤 문제점이 있고, 이를 해결하기 위한 트리 중 한가지

이진 탐색 트리는 삽입 순서로 인해 선형적인 구조가 될 수도 있다. 이때, 탐색에서 최악의 경우로 O(n)이 걸리게 된다. 이진 탐색 트리를 균형 잡힌 트리로 만드는 AVL 트리와 레드블랙트리가 있다.

AVL 트리는 스스로 균형을 잡는 이진 탐색 트리이다. 두 자식의 서브 트리의 높이는 항상 1만큼 차이가 난다는 특징이 있고, 탐색, 삽입, 삭제 모두 시간 복잡도가 O(logn)이며, 삽입, 삭제를 할 때마다 균형이 맞지 않는 것을 맞추기 위해 트리 일부를 왼쪽이나 오른쪽으로 회전 시킨다.