![[DB] 12. 인덱스 Ⅰ. 트리 생성 기법](https://image.inblog.dev?url=https%3A%2F%2Fsource.inblog.dev%2Ffeatured_image%2F2025-03-05T08%3A45%3A59.898Z-b68d09ea-3c28-4e00-9194-1f05d5ba8226&w=3840&q=75)
무작위 트리 생성
밸런스 트리 생성
1. 무작위
그냥 막 넣음
2. 이진 탐색 트리(Binary Search Tree, BST)
값을 비교해서 넣음
다음 숫자를 순서대로 삽입: 50, 30, 70, 20, 40, 60, 80
1️⃣ 50 삽입
50
2️⃣ 30 삽입 (50보다 작으므로 왼쪽)
50
/
30
3️⃣ 70 삽입 (50보다 크므로 오른쪽)
50
/ \
30 70
4️⃣ 20 삽입 (30보다 작으므로 30의 왼쪽)
50
/ \
30 70
/
20
5️⃣ 40 삽입 (30보다 크므로 30의 오른쪽)
50
/ \
30 70
/ \
20 40
6️⃣ 60 삽입 (70보다 작으므로 70의 왼쪽)
50
/ \
30 70
/ \ /
20 40 60
7️⃣ 80 삽입 (70보다 크므로 70의 오른쪽)
50
/ \
30 70
/ \ / \
20 40 60 80
✅ 결과적으로, 삽입을 할 때 항상 왼쪽(작은 값) / 오른쪽(큰 값)으로 이동하여 적절한 위치를 찾음.
3. 밸런스 트리
예제 1: LL 회전 (Right Rotation)
🔹 삽입 전
다음과 같은 트리를 고려해봅시다.
30
/
20
/
10여기서 10을 삽입하면서 왼쪽 서브트리가 깊이가 2가 되어 불균형 발생
(불균형: 왼쪽-왼쪽 LL 케이스)
🔹 해결 방법: 오른쪽 회전(Right Rotation)
- *30이 중심(root)**에서 20으로 내려가고
- 20이 새로운 루트가 되며,
- 10은 그대로 유지됨
🔹 회전 후 (균형 유지)
20
/ \
10 30
📝 예제 2: RR 회전 (Left Rotation)
🔹 삽입 전
다음과 같은 트리를 고려해봅시다.
10
\
20
\
30
여기서 30을 삽입하면서 오른쪽 서브트리가 깊이가 2가 되어 불균형 발생
(불균형: 오른쪽-오른쪽 RR 케이스)
🔹 해결 방법: 왼쪽 회전(Left Rotation)
- *10이 중심(root)**에서 20으로 내려가고
- 20이 새로운 루트가 되며,
- 30은 그대로 유지됨
🔹 회전 후 (균형 유지)
20
/ \
10 30
Share article