06. 자료구조 review [2 1주차]

6. 자료구조 review [2-1주차]

2024년 1월 9일 화요일

오후 11:06

Array

저장되는 데이터들이 동일한 타입으로 구성. 연속된 주소에 저장됨

 

 

Stack

Insert/Delete만 제공 -> Push/Pop이라고 부름

Last in, First out

성능 : Push: O(1), Pop: O(1)

 

 

Queue

Insert/Delete만 제공

First in, First out

성능 : Insert: O(1), Delete: O(1)

 

원형 큐의 문제점 : 가득 찼을 때와 비어 있을 때의 구분이 어렵다.

해결책 : 적어도 한 칸은 비워 놓는다.

 

 

Linked List

노드(Node, item) : 원소가 저장될 공간과 다음 노드를 가리키는 포인터로 구성됨

Head : 첫 번째 노드를 가리키는 포인터

 

 

Binary Search Tree (이진 탐색 트리)

부모보다 작은 데이터는 왼쪽에, 큰 데이터는 오른쪽에.

• node는 key를 포함한다.
• Root 노드는 하나 존재한다. (비어 있는 트리는 제외)
• 각각의 자식은 자신의 subtree의 root이다.
• 각각의 subtree는 그 자체로 이진 탐색 트리이다.
• 이를 왼쪽, 오른쪽 서브트리라고 하자.
• 왼쪽 서브트리의 키값은 루트 노드의 키값보다 작다. (반대도 성립)

 

 

Heap

• 완전 이진 트리. (마지막 깊이 이전의 노드는 가득 채워져 있고, 마지막 깊이의 노드는 왼쪽부터 순서대로 채워져 있다)
• 자식 노드의 키값이 부모 노드보다 커야 한다.
• 루트 노드의 키값이 가장 작다.
• 트리의 높이가 약 logN 이므로,  삽입과 삭제 연산에 걸리는 시간은 O(logN)이다.

 

 

 AVL Tree

• 이진 트리의 성능을 높이기 위함.
• 각각의 노드는 두 개의 label을 갖는다 : L, R
• L : 왼쪽 서브트리의 높이, R : 오른쪽 서브트리의 높이
• 각각의 노드에서, L과 R의 차이가 1이하여야 한다.

 

N개의 노드가 있을 때 AVL트리의 높이가 O(logN)이다.

증명 : 노드의 L이 n이고, L<=R 이라 가정하자. 그 노드의 왼쪽 자식 노드의 높이는 n이다. 높이가 n인 노드의 두 자식 중 적어도 하나는 높이가 n-1이고, AVL트리의 특성에 의해 나머지 하나의 자식은 높이가 n-1 또는 n-2이다. 즉, 높이가 n인 노드의 L과 R의 값의 최솟값은 n-2이다.

이로써 L과 R중 더 작은 값이 n인 노드의 자식 노드에서 label의 최솟값은 n-2임을 알 수 있다.

이를 이용해 높이가 2h인 트리가 끝나는 가장 짧은 경로를 찾아보자. 깊이 0 노드의 label 최솟값은 2h-2, 깊이 1 노드의 label 최솟값은 2h-4, 깊이 2 노드의 label 최솟값은 2h-6, ..., 깊이 h-1 노드의 label 최솟값은 0, 깊이 h 노드의 label 최솟값은 -1이 된다. 따라서 트리가 끝나는 가장 짧은 경로의 깊이는 h이며, 이는 적어도 깊이 h까지 노드가 가득 차 있으며, 높이가 2h인 트리의 노드는 아무리 적어도 2^h보다 많다는 것이다.

2^h<N, h<logN, 2h<2logN.

따라서 AVL트리의 높이는 O(logN)이라 할 수 있고,

삽입, 검색, 삭제에 걸리는 시간도 O(logN) 이다.

 

 

2-3 Tree

• 각각의 노드는 1개 또는 2개의 키를 갖는다.
• 키가 1개 있을 때는 2개의 자식을, 키가 2개 있을 때는 3개의 자식을 갖는다.
• 모든 리프 노드까지의 거리가 같다.
• 노드가 N개인 경우 높이는 O(logN).

 

 

Trie(트라이)

• 트리의 한 종류
• 루트에서 리프까지 읽어 내려가는 식으로 데이터를 읽을 수 있다.

• 검색에 걸리는 시간이 비트 수에 비례
• 사전 등에서 문자열을 저장할 때 자주 사용된다.

 

 

Simple Graph

V : Vertex(정점, 노드)들의 집합

E : Edge(간선)들의 집합

simple그래프의 경우, 방향이 없으므로, 간선하나를 두 정점의 무순서쌍으로 정의.

그래프는 G = (V ,E)라는 순서쌍으로 표현

 

Q : n개의 정점이 있을 때, 간선은 최대 몇개 있는가?

A : _nC₂ = n(n-1)/2