5.3 비선형 자료 구조

스터디를 함께 진행했음

일렬로 나열하지 않은 구조. 일반적으로 트리나 그래프를 말한다.

그래프

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

정점(vertex) : 노드(node)라고도 하며, 데이터가 저장되는 그래프의 기본 단위

간선(edge) : 단방향 간선과 양방향 간선이 있다.

가중치(weight) : 정점과 정점 사이에 드는 비용

트리

그래프 중 하나. 계층적 데이터의 집합이다.

트리의 특징

• 부모, 자식 계층 구조를 갖는다.
• 간선 수 = 노드 수 - 1
• 임의의 두 노드 사이의 경로는 반드시 존재한다.

트리의 구성

• 루트 노드 : 가장 위에 있는 노드
• 내부 노드 : 루트 노드와 리프 노드 사이에 있는 노드
• 리프 노드 : 자식 노드가 없는 노드

트리의 높이와 레벨

• (노드의) 깊이 : 루트 노드로부터 특정 노드까지 최단 거리로 갔을 때의 거리
• (트리의) 높이 : 루트 노드로부터 리프 노드까지의 거리 중 가장 긴 거리
• (노드의) 레벨 : 문제마다 다른 의미를 갖기도 하지만 보통은 깊이와 동일한 의미를 가짐

서브트리 : 트리 내의 하위 집합

이진 트리

모든 노드의 자식 노드 수가 2개 이하인 트리

• 정이진 트리 : 자식 노드가 없거나 2개인 이진 트리
• 완전 이진 트리 : 왼쪽에서부터 채워져 있는 트리. 마지막 레벨을 제외하고는 모두 채워져 있고. 마지막 레벨의 경우 왼쪽부터 채워져 있다.
• 변질 이진 트리 : 자식 노드가 하나밖에 없는 이진 트리 (선형이 됨)
• 포화 이진 트리 : 모든 레벨이 꽉 차 있는 이진 트리
• 균형 이진 트리 : 왼쪽과 오른쪽 노드의 높이 차이가 1 이하인 이진 트리

이진 탐색 트리

어떤 노드를 기준으로

• 오른쪽 하위 트리에는 노드 값보다 큰 값의 노드만 존재
• 왼쪽 하위 트리에는 노드 값보다 작은 값의 노드만 존재

하는 이진 트리

삽입 순서에 따라서 선형(변질 이진 트리)이 될 수도 있다. (이런 경우에 탐색 시간 복잡도가 최악이 됨.)

AVL 트리

이진 탐색 트리의 문제점인 “최악의 경우 선형적인 트리가 되는 것”을 방지하기 위해서 스스로 균형을 잡는 이진 탐색 트리

삽입 또는 삭제를 할 때마다 트리를 회전하는 방식으로 균형을 잡는다.

레드 블랙 트리

각 노드가 빨간색, 또는 검은색의 색을 갖고 있다는 특징을 갖는 균형 이진 트리.

모든 리프 노드와 루트 노드는 블랙이고 어떤 노드가 레드이면 그 노드의 자식은 반드시 블랙이다… 뭐 이런 규칙

힙

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

• 최대 힙 : 루트 노드에 있는 키는 모든 자식에 있는 키 중에서 가장 커야 함. 이 규칙은 모든 하위 서브트리에도 적용된다.
• 최소 힙 : 루트 노드에 있는 키는 모든 자식에 있는 키 중에서 가장 작아야 한다. 이 규칙은 모든 하위 서브트리에도 적용된다.

힙의 삽입

일단 힙의 마지막 노드에 붙인다. 그리고 위치에 맞게 끌어올림

힙의 삭제

힙에서의 삭제란… 가장 우선순위가 높은 데이터를 꺼내는 것.

일단 루트 노드를 반환하고, 힙의 가장 마지막 노드를 가져와서 루트 노드 자리에 둔다. 그리고 아래 자식과 비교하면서 내려가기.

• 최대 힙 : 더 큰 자식과 내 위치를 바꿈
• 최소 힙 : 더 작은 자식과 내 위치를 바꿈

우선순위 큐

힙을 기반으로 구현된다. (제발..)

맵

키와 매핑된 값의 조합으로 형성된 자료구조.

자바스크립트의 맵은 삽입된 순서를 기억하는 맵입니다

셋

고유한 요소를 저장하는 컨테이너

해시 테이블

무한한 데이터들을 유한한 개수의 해시 값으로 매핑한 테이블