교육 정보
- 교육 명: 경기미래기술학교 AI 교육
- 교육 기간: 2023.05.08 ~ 2023.10.31
- 오늘의 커리큘럼:
파이썬 자료구조
(7/17 ~ 7/28)- 강사: 이현주, 이애리 강사님
- 강의 계획:
1. 자료구조
AVL 트리
- 스스로 균형(height)을 잡는 이진 탐색 트리
- 균형을 잡아서 편향도를 낮춰 height를 낮게 유지
- 속성:
- 이진 탐색 트리 속성 만족
- 좌 우 서브트리 height 차이가 최대 1 (높이 차이가 1보다 커지면 rotation을 통해 균형을 맞춤)
→ 트리 내의 모든 노드가 이 성질을 만족해야 함
- 높이 logN으로 유지, 삽입, 검색, 삭제의 시간 복잡도는 O(logN)
AVL 트리 시뮬레이터
AVL 트리의 수선(균형을 맞추는 방법)
- LL 타입: 루트의 왼쪽의 왼쪽이 가장 깊은 경우 → right rotation (1회전)
- RR 타입: 루트의 오른쪽의 오른쪽이 가장 깊은 경우 → left rotation (1회전)
- LR 타입: 루트의 왼쪽의 오른쪽이 가장 깊은 경우 → left rotation → right rotation (2회전)
- RL 타입: 루트의 오른쪽의 왼쪽이 가장 깊은 경우 → right rotation → left rotation (2회전)
링크의 Rebalancing 항목 참고
레드 블랙 트리
- 자가 균형 이진 탐색 트리
- 속성:
- 모든 노드는 레드 or 블랙
- 루트 노드와 모든 리프노드는 항상 블랙 (구현을 위해 가장 말단에 NIL이라는 가상의 블랙 노드를 가진다고 가정)
- 레드노드의 자식은 항상 블랙 (레드 연속 불가)
- 모든 리프노드에서 루트노드로 가는 경로에서 만나는 블랙 노드의 갯수는 동일
- 새로 추가되는 노드는 항상 레드
레드 블랙 트리 시뮬레이터
B 트리
→ Restructuring과 Recoloring을 통해 균형을 맞춤
:D