[2022/09/02 공부 정리] 헷갈리는 자료구조론 - 큐(원형 큐, 데크), 트리(이진트리, 히프트리)

공부 정리 글은 하루를 마무리 하면서 혹은 아침 일찍 일어나서 하루를 시작하기 전에 복습의 의미에서 써보려 합니다.

• 오늘의 공부량: 자료구조론 100문제

• 헷갈리는 자료구조론: 큐(원형 큐, 데크), 트리(이진트리, 히프트리)

1. 원형 큐의 삽입/삭제 순서
   ▶️ 증가 → 오버플로우 검사 → 삽입
   ▶️ 언더플로우 검사 → 증가 → 삭제
   오버플로우 발생 시 맨 처음 노드에 데이터를 입력

2. 데크
   ▶️ 입력 제한 데크(Scroll)
   ▶️ 출력 제한 데크(Shelf)

3. 트리
   ▶️ e = n - 1 (e: 간선 수, n: 노드 수)
   ▶️ 차수: 파생된 직계 노드 수.
   ▶️ 일반트리는 한 개 이상의 노드.

4. 이진트리(Binary Tree)
   ▶️ 노드가 0개일 수 있음.(공트리)
   ▶️ 순서 트리(왼/오 순서가 중요)
   ▶️ 배열[1..n]에 저장 시,
   i번째 노드의 부노드 위치: ⌊i/2⌋
   왼쪽 자노드 위치: 2i
   오른쪽 자노드 위치: 2i +1
   ▶️ 노드 간 관계
   n₀: 단말 노드 수, n ₂: 차수 2인 노드 수
   n₀ = n₂ + 1
   
   n: 총 노드 수, k: 차수
   총 링크 수 = nk
   널 링크 제외한 링크 수 = n - 1
   널 링크 수 = nk - (n - 1)
   ▶️ 연결리스트 표현: 트리의 차수만큼 포인터 필요
   ▶️ E = I + 2n (E: 외부경로길이, I: 내부경로길이)

5. 이진트리 종류
   ▶️ 포화이진트리(정이진트리, full binary tree)
   n = 2^k-1(n: 노드 수, k: 높이)
   단말노드 수: 항상 2 ^k-1
   단말노드가 아닌 노드 수: 2 ^k-1-1
   레벨 i(1<= i <= k))에서 가질 수 있는 노드 수: 2 ^i-1
   높이: log₂(n+1)
   ▶️ 완전이진트리(정이진트리, complete binary tree)
   노드 수: 2 ^k-1 <= n <= 2 ^k-1
   높이: ⌈ log₂(n+1) ⌉
   포화이진트리는 완전이진트리에 포함됨.
   ▶️ Knuth이진트리: 차수가 2이하
   ▶️ 엄밀한 이진트리: 차수가 0이거나 2(단말노드 수 = 단말 아닌 노드 수 + 1)

6. 일반트리 → 이진트리 변환
   
   (1) 형제 노드 연결
   (2) 가장 왼쪽 자손을 제외하고 나머지 자식 노드들에 대해 부모와 연결된 간선을 모두 제거
   (3) 형제 노드들을 연결하는 간선을 시계방향으로 45도 회전(왼/오 서브트리 구분 위해)

7. 스레드 이진트리
   ▶️ 이진트리에서 낭비되는 n+1개의 null링크를 포인터로 사용
   ▶️ 5개 필드
   ▶️ 알고리즘은 반복적
   ▶️ 스택 도움 없이 트리 순회 가능
   ▶️ 노드가 n개 일 때, 시간복잡도 O(n)

8. 히프 트리
   ▶️ 최소 힙의 부노드 값 <= 자식노드 값
   최대 힙의 부노드 값 >= 자식노드 값
   ▶️ 완전이진트리
   ▶️ 삽입, 삭제 시간: O(log₂n)
   ▶️ 힙에 새로운 원소 삽입에 걸리는 시간: 높이에 비례
   ▶️ 최대 힙
   가장 작은 원소 찾는데 O(n) 시간
   가장 큰 원소 찾는데 O(1) 시간

내일은 더 많이 공부하겠슴다~
정리했으니 오래 기억에 남길~!
화이팅!!👊