[강의정리] 알고리즘 W3 - Data Structures
Data Structure
List
Linked List
배열과 달리 크기를 바꿀 수 있는 자료구조
각 노드는 다음노드를 가르키는 포인터를 가짐
첫번째노드: 헤드(Head), 마지막 노드: 테일(Tail)
Double Linked List
- 각 노드는 다음노드와 이전노드를 가르키는 포인터를 가짐
Circle Linked List
- Head가 Tail을 물고있는 형태의 Linked List
Stack
- 먼저 들어간 요소가 나중에 나옴 (First-In, Last-Out: LIFO)
Queue
- 먼저 들어간 요소가 먼저 나옴 (First-In, First-Out: FIFO)
Circle Queue
Linked Queue
Tree
- 나무를 닮은 구조
- Root, Branch, Leaf로 이루어져 있음
깊이(Depth): 루트노드에서 해당 노드까지의 경로의 길이
레벨(Level): 같은 깊이를 가지는 노드의 집합
높이(Height): “가장 깊은 곳”에 있는 잎노드까지의 깊이
차수(Degree): 자식 노드의 개수
트리의 차수: 트리 내에 있는 노드들 가운데 자식 노드가 가장 많은 노드의 차수
이진트리(Binary Tree)
- 모든 노드가 최대 “2 개”의 자식을 가질 수 있는 트리
포화 이진 트리(Full Binary Tree)
- 모든 노드가 대대손손이 자식을 둘씩 가지고 있는 이진 트리
완전 이진 트리
- 잎 노드들이 트리의 왼쪽부터 차곡차곡 채워진 트리
완전 높이 균형 트리(Completely Height Balanced Tree)
- 루트 노드를 기준으로 왼ㅉ고 하위 트리와 오른ㅉ고 하위 트리의 높이가 같은 이진트리
Priority Queue
- 우선순위 속성을 갖는 데이터를 다룸
Heap
- 힙 순서 속성(Heap Order Property)를 만족하는 완전 이진 트리
- 힙 순서 속성 : 트리 내의 모든 노드가 부모 노드보다 커야 한다는 규칙