[ 8일차 복습 ] 트리(Tree) 개념 정리 & 개인 프로젝트 개발계획서 작성

1. 오늘 학습내용

① 트리(Tree) 기본 개념

• 계층적(Hierarchical) 자료구조
• 노드(Node)와 간선(Edge)으로 구성
• 루트(Root)에서 시작해 하위 노드로 확장
• 노드 n개 → 간선 n-1개

✔ 주요 용어

• Root / Parent / Child
• Leaf Node (단말 노드)
• Degree (차수)
• Level / Height
• Subtree

---

 ② 이진 트리 (Binary Tree)

• 각 노드가 최대 2개의 자식
  • left
  • right
• 재귀적 구조

typedef struct TreeNode {
    int data;
    struct TreeNode* left;
    struct TreeNode* right;
} TreeNode;

 

✔ 이진 트리의 특징

• 최소 노드 수: h+1
• 최대 노드 수: 2^(h+1) - 1
• 종류
  • 포화 이진 트리
  • 완전 이진 트리
  • 편향 이진 트리

---

③ 이진 트리 순회 (Traversal)

트리는 재귀적 접근이 핵심

• 전위 순회 (Preorder) → D-L-R
• 중위 순회 (Inorder) → L-D-R
• 후위 순회 (Postorder) → L-R-D

✔ 폴더 용량 계산 예제 → 후위 순회 활용

---

④ 이진 탐색 트리 (BST)

• 왼쪽 < 부모 < 오른쪽
• 탐색, 삽입, 삭제 연산 수행
• 삭제 시 경우 3가지
  1. 단말 노드
  2. 자식 1개
  3. 자식 2개 → 후계자 선택

---

⑤ AVL 트리

• 균형 이진 탐색 트리
• 균형 인수 BF = hL - hR
• BF 값은 -1, 0, 1만 허용
• 회전 연산
  • LL
  • RR
  • LR
  • RL

---

⑥ 히프(Heap)

• 완전 이진 트리 기반
• 최대 히프 / 최소 히프
• 삽입 → 위로 비교
• 삭제 → 아래로 비교
• 배열 기반 구현 가능

---

⑦ 개인 프로젝트 개발계획서 작성

✔ 일정

• 개발계획서 마감: 2026.02.12
• 최종 발표: 2/27 오전
• 제출: dbuser@naver.com
• 형식: PPTX 또는 PDF
• 분량: 약 10페이지

✔ 개발계획서 구성

(1) 아이디어

• 문제 제기
• 제안 배경
• 해결 방안

(2) 요구사항

• 기능 목록 작성
• 각 기능에 고유 ID 부여
• 세부 기능 설명
• 기능 설명 구체화

(3) 설계

• 순서도 (큰 흐름 위주)
  • 시간의 흐름
  • 인과관계 중심
• 구조도
  • 전체 구성
  • 포함 관계 표현
• 일정 계획
  • 우선순위 설정
  • 핵심 기능부터 구현

(4) 리스크 관리

• 예상 실패 요인
• 대비 방안
• 추후 확장 가능성
• 프로젝트 활용 방향

---

2. 헷갈렸던 거

• 트리의 높이 계산 방식
• AVL 회전 유형 구분
• BST 삭제 시 후계자 선택 과정
• 순서도와 구조도의 차이

---

3. 나중에 다시 볼 키워드

• 트리 용어 정리
• 이진 트리 순회 재귀 흐름
• BST 삭제 알고리즘
• AVL 회전
• 히프 삽입/삭제
• 순서도 vs 구조도
• 요구사항 정의서 작성 방법