- 후위표기법
- 큐
- 우선순위 큐 (Priority Queues)
- 트리
- 이진 탐색 트리
- 힙
1) 후위표기법 (Postfix notation)
연산자가 피연산자들의 뒤에 위치
중위표기법 (A + B) * (C + D) => 후위표기법 AB + CD + *
피연산자가 나오면 그대로 적고 연산자가 나오면 스택에 넣는다.
괄호의 처리
여는 괄호는 스택에 push
닫는 괄호를 만나면 여는 괄호가 나올 때까지 pop
여는 괄호의 우선순위를 가장 낮게 설정하여 여는 괄호 앞의 연산자를 pop 하지 않도록 한다.
우선순위
*, / >> +, - >> (
알고리즘
중위 표현식을 왼쪽부터 한 글자씩 읽는다.
피연산자면 그냥 출력
연산자면 peek한 연산자의 우선순위가 높거나 같으면 pop
그리고 이 연산자는 push
표현식이 끝나면 스택에 남아 있는 연산자 모두 pop
후위표기식의 계산
후위 표현식을 왼쪽부터 한 글자씩 읽는다.
피연산자면 스택에 push
연산자를 만나면 스택에서 pop (operand1), pop (operand2), operand2 연산 operand1을 스택에 push
수식이 끝나면 스택에서 pop
2) 큐
자료를 보관할 수 있는 선형구조
한 쪽 끝으로 넣는 enqueue, 반대 쪽으로 꺼내는 dequeue
선입선출 (FIFO - First-In First-Out)
3) 우선순위 큐 (Priority Queues)
큐가 FIFO 방식을 따르지 않고 원소들의 우선순위에 따라 큐에서 빠져나오는 방식
4) 트리
node와 edge를 이용하여 데이터의 배치 형태를 추상화한 자료 구조
root, internal, leaf 노드로 이루어짐
트리의 수준(level) - root 노드로부터의 거리
트리의 깊이(depth) - level + 1
노드의 차수(degree) - 자식 노드의 수
이진트리
모든 노드의 차수가 2 이하인 트리
포화 이진 트리
모든 레벨에서 노드들이 모두 채워져 있는 이진 트리
완전 이진 트리
높이가 k인 완전 이진 트리
레벨 k-2 까지는 모든 노드가 2개의 자식을 가진 포화 이진 트리
레벨 k-1 에서는 왼쪽부터 노드가 순차적으로 채워져 있는 이진 트리
이진 트리의 순회
-
깊이 우선 순회
중위 순회 (in-order traversal)
: Left - 자기 자신 - Right
전위 순회 (pre-order traversal)
: 자기 자신 - Left - Right
후위 순회 (post-order traversal)
: Left - Right - 자기 자신
-> 재귀적인 방법 이용 -
넓이 우선 순회
수준(level)이 낮은 노드를 우선으로 방문
같은 수준의 노드들 사이에는
부모 노드의 방문 순서에 따라 방문
왼쪽 자식 노드를 오른쪽 자식보다 먼저 방문
-> 큐 이용
5) 이진 탐색 트리
왼쪽 서브트리에 있는 데이터는 모두 현재 노드의 값보다 작고
오른쪽 서브트리에 있는 데이터는 모두 현재 노드의 값보다 큰 이진 트리
삽입 :
현재 노드보다 키값이 작으면 왼쪽으로, 크면 오른쪽으로 재귀적으로 이동하며 leaf 노드에서 삽입된다.
삭제 :
키값을 이용해서 노드를 찾는다.
해당 키의 노드가 없으면 pass
찾은 노드의 부모 노드를 알아야 삭제 후 이진 탐색 트리를 만족하도록 재구성할 수 있음
- leaf 노드인 경우
노드 삭제 - 자식이 하나인 경우
노드를 삭제하고 자식을 갖다 놓는다. - 자식이 둘인 경우
오른쪽 서브트리에서 가장 작은 노드를 갖다 놓는다.
가져온 노드의 부모에게 자식을 갖다 놓는다.
한 쪽으로 치우쳐지는 편향 이진 트리가 되는 경우 이진 탐색 트리가 효율적이지 못 함
-> 높이의 균형을 유지함으로써 O(logn)의 탐색 복잡도 보장하는 이진 탐색 트리 (AVL트리, 레드블랙트리)
6) 힙
이진 트리의 한 종류
루트 노드가 언제나 최댓값 또는 최솟값을 가짐
완전 이진 트리여야 함
삽입: O(logn)
트리의 마지막 자리에 새로운 원소 임시 저장
부모 노드와 키 값을 비교하여 위로 이동
삭제: O(logn)
루트 노드 제거
트리 마지막 자리 노드를 임시로 루트 노드 자리에 배치
자식 노드들과의 값 비교하여 아래로 이동
힙 정렬 알고리즘 복잡도 : O(nlogn)
