자료구조에 대하여 - 2

_1. Stack, Queue에 대해서 설명해주세요.

 

 

 

[ Stack 스택 ]

• 데이터를 차곡차곡 쌓아 올린 형태의 자료구조
• 후입선출(LIFO, Last In First Out) 특성
• 삽입과 삭제되는 방향이 같음

 

 

[ Stack 스택 활용 예시 ]

• 웹 브라우저 뒤로가기
• 실행 취소
• 수식의 괄호 검사

 

 

[ Queue 큐 ]

• 대기열 형태의 자료구조
• 선입선출(FIFO, First In First Out) 특성
• 한쪽 끝에서 삽입 작업이, 다른쪽 끝에서는 삭제 작업이 이루어짐

 

 

[ Queue 큐 활용 사례 ]

• 우선순위가 같은 대기열
• 프로세스 관리

 

 

 

 

 

 

---

_2. Heap, Priority Queue에 대해서 설명해주세요.

 

[ Heap 힙 ]

• 완전 이진 트리의 한 종류
• 여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조
• 부모의 값은 자식보다 항상 크거나 작아야 함
• 최대 힙, 최소 힙 두 종류
  • key(parent) >= key(child)
  • key(parent) <= key(child)
• 최대값이나 최소값을 O(1)로 찾기 가능
  • 삽입 삭제 = O(logN)
• 중복된 값 허용
  • 이진 탐색 트리는 허용 X

 

 

 

[ Heap 힙 표현 ]

• 완전 이진 트리이기때문에 배열로 표현하기 매우 좋음
• 트리의 배열 표현의 경우 👉 계산 편하게 하기 위해 index = 1 부터 사용

 

• 힙에서의 부모 노드와 자식 노드의 관계
  
  • 왼쪽 자식의 인덱스 👉 (부모의 인덱스) * 2
  • 오른쪽 자식의 인덱스 👉 (부모의 인덱스) * 2 + 1
  • 부모의 인덱스 👉 (자식의 인덱스) / 2

 

 

 

 

[ Priority Queue 우선순위 큐 ]

• 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나오는 자료구조
• Heap 자료구조를 이용하여 구현

 

 

[ Priority Queue 우선순위 큐 구현 방법당 시간 복잡도 차이]

우선 순위 큐 구현 시 힙을 사용하는 이유

 

 

 

 

 

---

_3. Tree, Binary Tree, BST, AVL Tree에 대해서 설명해주세요.

 

 

[ Tree 트리 ]

• 비선형 구조이며 원소들간 계층 관계를 가지며, 원소들 간에 1:n 관계를 가지는 자료구조
• 노드(node) 👉 트리의 원소
• 간선(edge) 👉 노드와 노드를 연결하는 선
• 루트 노드(root node) 👉 트리의 최상위 노드
• 차수(degree) 
  • 노드의 차수 👉 원소에 연결된 자식 노드 수
  • 트리의 차수 👉 노드 차수 중 가장 큰 값
• 높이
  • 노드의 높이 👉 루트에서 노드에 이르는 간선의 수
  • 트리의 높이 👉 트리에 있는 노드 높이 중 가장 큰 값

 

 

 

[ Binary Tree 이진 트리 ]

• 최대 차수가 2인 트리
• 높이가 h인 이진트리가 가질 수 있는 노드의 최소 개수 👉 h+1
• -------------------------------------------------------의 최대 개수 👉 2^(h+1) + 1
• 종류
  • 포화 이진 트리
    • 모든 레벨의 노드가 포화 상태로 차 있는 이진 트리
  • 완전 이진 트리
    • 노드 번호 1번부터 n번까지 빈자리가 없는 트리
  • 편향 이진 트리
    • 높이 h에 대한 최소 개수의 노드를 가지면서 한쪽 방향의 자식 노드만을 가진 이진 트리

 

 

 

[ Binary Search Tree 이진 탐색 트리 ]

• 노드의 왼쪽 가지에는 노드의 값보다 작은 값들만 있고, 오른쪽 가지에는 큰 값들만 있도록 구성한 이진 트리의 일종
• 이진 탐색의 아이디어를 채용한 자료구조
  • 정렬된 특징을 이용해 반씩 쪼개가며 탐색 -> 탐색 횟수 낮아짐
  • 그럼 이진 탐색 사용하면 되는거 아닌가요?
    • 이진 탐색을 사용하는 배열은 조회에만 강점 -> 삽입 삭제 어려움!
• 중복된 키 허용 X
• 중위 순회를 사용하면 모든 키를 정렬된 순서로 가져올 수 있음

 

중위 순회 : 1, 3, 5, 7, 8, 10

 

 

 

 

 

 

[ AVL Tree 트리 ]

• 스스로 균형을 잡는 이진 탐색 트리
• 한쪽으로 치우친 편향 이진트리가 되면 트리의 높이가 높아지기 때문에 이를 방지하고자 높이 균형을 유지해줌
• 이진 탐색 트리의 속성을 가짐
• 왼쪽 오른쪽 서브 트리의 높이 차이가 최대 1
  • 1보다 커지면 회전(rotation을 통해 균형을 잡아줌)

 

[ Balance Factor (BF) ]

• BF 👉 왼쪽 서브트리의 높이 - 오른쪽 서브트리의 높이
  • BF가 1 👉 왼쪽 서브트리가 오른쪽 서브트리보다 높이가 한단계 높다는 것을 의미
  • BF가 0 👉 왼쪽 서브트리와 오른쪽 서브트리의 높이가 같다는 것을 의미
  • BF가 -1 👉 왼쪽 서브트리가 오른쪽 서브트리보다 높이가 한단계 낮다는 것을 의미

 

 

 

 

[ 회전 (rotation ]

• 삽입, 삭제 시 👉 불균형 상태 (BF가 -1,0,1이 아닐때) AVL트리는 불균형 노드를 기준으로 서브트리의 위치를 변경하는 회전 작업 수행

 

1. LL (Left Left) case

 

2. RR (Right Right) case

 

3. LR (Left Right) case

 

 

4. RL (Right Left) case

 

 

 

[ AVL 트리의 시간복잡도 ]

 

 

 

 

 

---

출처

https://devuna.tistory.com/22

[자료구조] 스택 (STACK), 큐(QUEUE) 개념/비교 /활용 예시

https://jud00.tistory.com/entry/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EC%8A%A4%ED%83%9DStack%EA%B3%BC-%ED%81%90Queue%EC%97%90-%EB%8C%80%ED%95%B4%EC%84%9C-%EC%95%8C%EC%95%84%EB%B3%B4%EC%9E%90

[자료구조] 스택(Stack)과 큐(Queue)에 대해서 알아보자!

https://namu.wiki/w/%ED%9E%99%20%ED%8A%B8%EB%A6%AC

힙 트리 - 나무위키

https://velog.io/@chayezo/%ED%9E%99-Heap

힙 Heap / 우선순위 큐(Priority Queue)

https://chanhuiseok.github.io/posts/ds-4/

자료구조 - 우선순위 큐(Priority Queue)와 힙(heap)

https://suyeon96.tistory.com/31

[자료구조] 우선순위 큐와 힙 (Priority Queue & Heap)

https://www.youtube.com/watch?v=P-FTb1faxlo 

https://ratsgo.github.io/data%20structure&algorithm/2017/10/22/bst/

이진탐색트리(Binary Search Tree) · ratsgo's blog

https://code-lab1.tistory.com/10

[자료구조] 이진탐색트리(Binary Search Tree)의 개념, 이해 | C언어 이진탐색트리 구현

https://yoongrammer.tistory.com/71

[자료구조] 이진 탐색 트리 (BST, Binary Search Tree)

https://yoongrammer.tistory.com/72#%ED%9A%8C%EC%A0%84_(rotation) 

[자료구조] AVL 트리(Tree)

https://mommoo.tistory.com/101

[자료구조] 이진탐색트리