자료구조 (3) - 비선형 자료 구조

샐러드맛집·2022년 12월 30일

CS공부

목록 보기

10/10

본 포스트는 '면접을 위한 CS 전공지식 노트'를 기반으로 공부한 내용을 정리한 포스트입니다.

그래프

정점(vertex)과 간선(edge)으로 이뤄진 자료구조

간선은 한쪽 방향으로의 이동만 가능한 단방향 간선과 양쪽 방향으로 이동이 가능한 양방향 간선, 방향이 없는 간선이 있음

정점에서 나가는 간선을 해당 정점의 outdegree
정점으로 들어오는 간선을 해당 정점의 indegree

이런 정점과 간선으로 이뤄진 집합을 그래프라고 함

트리

그래프 중 하나로 정점과 간선이 있고, 트리 구조로 배열된 계층적 데이터의 집합
루트 노드, 내부 노드, 리프 노드 등으로 구성됨

트리 특징
1. 부모, 자식 계층 구조
2. V - 1 = E 라는 특징 (노드 수 - 1 = 간선 수)
3. 임의의 두 노드 사이의 경로는 '유일무이'하게 '존재'함
  -> 트리 내의 두 노드 간에는 경로가 반드시 있음
루트 노드
트리에서 가장 위에 있는 노드
내부 노드
루트 노드와 내부 노드 사이에 있는 노드
리프 노드
자식 노드가 없는 노드

출처 : 파이썬 알고리즘 인터뷰
저작자 : 책만 출판사
저작권 : CC BY-NC 2.0 KR

깊이
루트 노드부터 특정 노드까지 최단 거리로 갔을 때의 거리
높이
루트 노드부터 리프 노드까지 거리 중 가장 긴 거리
레벨
보통 깊이와 같은 의미
서브 트리
트래 내의 하위 집합을 서브 트리라고 함

이진 트리

이진 트리는 자식의 노드 수가 2개 이하인 트리를 의미

사진 출처

정이진 트리(Full binary tree)
자식 노드가 0 또는 2 개인 이진 트리
완전 이진 트리(Complete binary tree)
왼쪽에서부터 채워져 있는 이진 트리
마지막 레벨을 제외하고는 모든 레벨이 완전히 채워져 있음
변질 이진 트리(Degenerate binary tree)
자식 노드가 하나 밖에 없는 이진 트리
포화 이진 트리(Perfect binary tree)
모든 노드가 꽉 차 있는 이진 트리
균형 이진 트리(Balanced binary tree)
왼쪽과 오른쪽 노드의 높이 차이가 1 이하인 이진 트리를 의미
map, set을 구성하는 레드 블랙 트리는 균형 이진 트리 중 하나

이진 탐색 트리

이진 탐색 트리 (Binary Search Tree) :

각 노드에 값이 있다.

값들은 전순서가 있다.

노드의 왼쪽 서브트리에는 그 노드의 값보다 작은 값들을 지닌 노드들로 이루어져 있다.

노드의 오른쪽 서브트리에는 그 노드의 값보다 큰 값들을 지닌 노드들로 이루어져 있다.

좌우 하위 트리는 각각이 다시 이진 탐색 트리여야 한다.
출처

보통 이진 탐색 트리에서 탐색은 O(logn)이 걸림.
그러나 최악의 경우 O(n)이 걸림
-> 삽입 순서에 따라 선형적으로 트리가 구성될 수 있기 때문

이진 탐색 트리 최악 시간 복잡도

자료구조	접근	탐색	삽입	삭제
이진 탐색 트리(BST)	O(n)	O(n)	O(n)	O(n)

AVL 트리

AVL 트리(Adelson-Velsky and Landis tree)
선형적으로 구성되는 이진 탐색 트리를 방지하고, 균형을 잡는 트리
두 자식 서브트리의 높이는 항상 최대 1만큼 차이 난다는 특징

삽입, 삭제를 할 때마다 균형이 맞추기 위해 트리 일부를 왼쪽 혹은 오른쪽으로 회전 시키며 균형을 잡음

AVL 트리 최악 시간 복잡도

자료구조	접근	탐색	삽입	삭제
AVL 트리	O(logn)	O(logn)	O(logn)	O(logn)

사진 출처

레드 블랙 트리

균형 이진 탐색 트리

각 노드는 빨간색, 검은색 색상을 나타내는 추가 비트를 저장하여, 삽입/삭제 중 트리가 균형을 유지하도록 사용됨
모든 리프 노드와 루트 노드는 블랙이고, 어떤 노드가 레드이면 그 노드의 자식은 반드시 블랙 이라는 규칙을 기반으로 균형을 맞춤

레드 블랙 트리 최악 시간 복잡도

자료구조	접근	탐색	삽입	삭제
레드 블랙 트리	O(logn)	O(logn)	O(logn)	O(logn)

사진 출처

힙

힙은 완전 이진트리 기반의 자료구조

힙(heap)은 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리(complete binary tree)를 기본으로 한 자료구조(tree-based structure)로서 다음과 같은 힙 속성(property)을 만족한다.

A가 B의 부모노드(parent node) 이면, A의 키(key)값과 B의 키값 사이에는 대소관계가 성립한다.
힙에는 두가지 종류가 있으며, 부모노드의 키값이 자식노드의 키값보다 항상 큰 힙을 '최대 힙', 부모노드의 키값이 자식노드의 키값보다 항상 작은 힙을 '최소 힙'이라고 부른다.

키값의 대소관계는 오로지 부모노드와 자식노드 간에만 성립하며, 특히 형제 사이에는 대소관계가 정해지지 않는다.

각 노드의 자식노드의 최대개수는 힙의 종류에 따라 다르지만, 대부분의 경우는 자식노드의 개수가 최대 2개인 이진 힙(binary heap)을 사용한다.

힙에서는 가장 높은(혹은 가장 낮은) 우선순위를 가지는 노드가 항상 뿌리노드에 오게 되는 특징이 있으며, 이를 응용하면 우선순위 큐와 같은 추상적 자료형을 구현할 수 있다.
출처

사진 출처