1. Heap
1) heap의 정의
- 각 노드의 키값이 자식의 키값보다 작지 않거나(최대힙) 그 자식의 키값보다 크지 않은(최소힙) 완전이진트리
2) Heap의 장점
- Heap에서 최대/최소값을 찾을 때 O(log N) 만큼 걸림 ( 배열에서의 O(N)보다 짧음)
3) Heap의 종류
- 최대 힙(Max Heap) : 부모노드 키값 > 자식노드 키값
- 최소 힙(Min Heap) : 부모노드 키값 < 자식노드 키 값
4) Heap 구현
- 배열로 구성하며, 1번 인덱스부터 사용함
- 부모 노드 인덱스 번호 = 자식 노드 인덱스 번호 / 2
- 왼쪽 자식 노드 인덱스 번호 = 부모 노드 인덱스 번호 * 2
- 오른쪽 자식 노드 인덱스 번호 = 부모 노드 인덱스 번호 * 2 + 1
2. Stack & Queue
1) Stack의 개념
- 한 쪽 끝에서만 자료를 넣고 뺄 수 있는 LIFO (Last In First Out) 형식의 자료 구조
2) Stack과 배열의 차이
- 배열과 달리 스택은 상수 시간에 i번째 접근이 불가
- 스택은 배열과 달리 데이터 추가/삭제 연산을 상수시간에 가능
- 데이터를 탐색하기보다 앞 단의 데이터만 넣고 빼고 하는 과정이 빈번하게 일어나는 경우, 스택 자료 구조가 효율적
3) Stack의 사용 사례
- 함수의 호출
: 메모리의 stack영역에는 함수의 호출과 관계되는 지역변수들이 저장되며, 함수의 호출이 완료되면 소멸함
스택 영역에 차례대로 저장되는 함수의 호출 정보를 스택 프레임이라고 하며, 스택프레임이 있기에 함수 호출이 끝난 후 해당 함수가 호출되기 이전 상태로 돌아갈 수 있음
- 재귀 알고리즘
: 자기 자신을 다시 호출하는 함수. 자기 자신을 계속 스택에 넣으면서 종료 조건에 도달하면 스택에서 제거하는 방식과 유사
- 후위 표기법
: 연산자가 피연산자 뒤에 위치하는 방식 ex) AB + CD + *
4) Queue의 개념
- 한 쪽 끝에서만 자료를 넣고 뺄 수 있는 FIFO (First In First Out) 형식의 자료 구조
5) Queue의 사용 사례
- 너비 우선 탐색
: 루트 노트 (혹은 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법이며 큐를 사용하여 구현함
- 스케줄링 큐
: 여러 프로세스가 번갈아가며 수행되는 과정에서, 프로세스들이 순서를 대기하는 공간을 스케줄링 큐라 함
- Job Queue: 하드디스크에 있는 프로그램이 실행되기 위해 메인 메모리의 할당 순서를 기다리는 큐
- Ready Queue: CPU 점유 순서를 기다리는 큐
- Devide Queue: I/O 장치를 기다리는 큐
- 페이지 교체 알고리즘 중 FIFO
: First In First Out 알고리즘, 메모리에 올라온 지 가장 오래된 페이지를 교체하는 방식이며 각 페이지가 올라온 순서를 큐에 저장하는 방식을 사용함
3. Tree
1) Tree의 특징
- 스택이나 큐와 달리 비선형 자료구조이자, 계층적 관계(Hierarchical Relationship)을 표현하는 자료구조
- 사이클이 존재하지 않음(그래프와 차이)
- 루트에서 한 노드로 가는 경로는 유일
- N개의 노드와 N-1개의 간선이 존재
2) Binary Tree
- 루트 노드를 중심으로 두 개의 서브 트리로 나뉘어지며, 각 서브 트리 또한 이진트리
- Perfect Binary Tree(포화 이진 트리) : 모든 레벨이 꽉 찬 트리
- Complete Binary Tree(완전 이진 트리) : 위 -> 아래, 왼 ->오 순서대로 채워진 이진트리
- Full Binary Tree (정 이진 트리): 모든 노드가 0개 또는 2개의 자식 노드를 갖는 이진트리
3) Binary Search Tree
- 이진 탐색과 연결 리스트를 합한 이진 트리
- 이진 탐색의 탐색 소요 시간 O(log N) 장점과, 연결 리스트의 삽입삭제 시간 O(1)의 장점을 모두 가짐
-> 즉, 효율적인 탐색 능력을 가지고, 자료의 삽입 및 삭제가 가능한 자료구조
- 데이터 저장 규칙
1.이진 탐색 트리의 노드에 저장된 키는 유일하다
2.부모의 키가 왼쪽 자식 노드의 키보다 크다
3.부모의 키가 오른쪽 자식 노드의 키보다 작다
4.왼쪽과 오른쪽 서브트리도 이진 탐색 트리이다- 단점 : 편향 트리( 노드가 한쪽으로 치우친 트리)가 되어 탐색 시간 복잡도가 O(N)이 될 수 있다.
해당 단점을 보완하기 위해 트리의 균형을 맞춰주는 Rebalancing(재조정)이 필요하며, 그러한 기법을 이용한 트리에는 Red Black Tree와 AVL Tree가 있음
4) Red Black Tree
- BST를 기반으로 한 자료구조로, 데이터의 탐색, 삽입, 삭제 연산이 전부 O(log n)
- 만족 규칙
- 모든 노드는 Black 또는 Red의 색을 갖는다
- 루트 노드의 색은 Black이다
- 단말 노드의 색은 Black이다
- 어떤 노드의 색이 Red라면 다른 두 개의 자식의 색은 Black이다
- 각 노드에 대해서 노드로부터 descendant leaves 까지의 단순 경로는 전부 같은 수의 Black 노드를 포함하고 있다 이때, 해당 Black 노드의 수를 Black Height라고 부른다