[DB] 12.1. 트리 생성 기법

Mar 10, 2025

Contents

1. 무작위 2. 이진 탐색 트리(Binary Search Tree, BST)3. 밸런스 트리 예제 1: LL 회전 (Right Rotation)📝 예제 2: RR 회전 (Left Rotation)📝 예제 3: RL 회전 (Right-Left Rotation)📝 예제 4: LR 회전 (Left-Right Rotation)

❗

무작위 트리 생성

밸런스 트리 생성

1. 무작위

❗

그냥 막 넣음

2. 이진 탐색 트리(Binary Search Tree, BST)

❗

값을 비교해서 넣음

But, 그냥 넣으면 밸런스 무너짐

다음 숫자를 순서대로 삽입: 50, 30, 70, 20, 40, 60, 80

1️⃣ 50 삽입

2️⃣ 30 삽입 (50보다 작으므로 왼쪽)


    50
   /
  30

3️⃣ 70 삽입 (50보다 크므로 오른쪽)


    50
   /  \
  30   70

4️⃣ 20 삽입 (30보다 작으므로 30의 왼쪽)

5️⃣ 40 삽입 (30보다 크므로 30의 오른쪽)

6️⃣ 60 삽입 (70보다 작으므로 70의 왼쪽)

7️⃣ 80 삽입 (70보다 크므로 70의 오른쪽)


    50
   /  \
  30   70
 /  \   /  \
20   40 60  80

✅ 결과적으로, 삽입을 할 때 항상 왼쪽(작은 값) / 오른쪽(큰 값)으로 이동하여 적절한 위치를 찾음.

3. 밸런스 트리

❗

AVL 트리 (Adelson-Velsky and Landis Tree)

모든 노드에서 왼쪽과 오른쪽 서브트리의 높이 차이가 1 이하가 되도록 유지

균형 인수(BK) = 왼쪽 서브 트리의 높이 - 오른쪽 서브 트리의 높이
전체 삽입 후 회전X
밸런스가 무너질 때(깊이가 2 차이가 날 때)마다 회전

불균형이 발생하면 회전(Rotation) 연산을 통해 균형을 맞춤

삽입의 속도는 무작위보다 오래 걸림

데이터를 넣어두기만 하고 찾지 않거나 정말 가끔가다가 한 번 찾을 경우 → 무작위로 삽입 후 필요할 때 한번에 정렬하는게 낫다.

예제 1: LL 회전 (Right Rotation)

🔹 삽입 전

다음과 같은 트리를 고려해봅시다.

여기서 10을 삽입하면서 왼쪽 서브트리가 깊이가 2가 되어 불균형 발생

(불균형: 왼쪽-왼쪽 LL 케이스)

🔹 해결 방법: 오른쪽 회전(Right Rotation)

*30이 중심(root)**에서 20으로 내려가고

20이 새로운 루트가 되며,

10은 그대로 유지됨

🔹 회전 후 (균형 유지)


      20
     /  \
    10   30

📝 예제 2: RR 회전 (Left Rotation)

🔹 삽입 전

다음과 같은 트리를 고려해봅시다.

여기서 30을 삽입하면서 오른쪽 서브트리가 깊이가 2가 되어 불균형 발생

(불균형: 오른쪽-오른쪽 RR 케이스)

🔹 해결 방법: 왼쪽 회전(Left Rotation)

*10이 중심(root)**에서 20으로 내려가고

20이 새로운 루트가 되며,

30은 그대로 유지됨

🔹 회전 후 (균형 유지)


      20
     /  \
    10   30

📝 예제 3: RL 회전 (Right-Left Rotation)

🔹 삽입 전

다음과 같은 트리를 고려해봅시다.

여기서 60을 삽입하면서 오른쪽 서브트리가 깊이가 2가 되어 불균형 발생

(불균형: 오른쪽-왼쪽 RL 케이스)

🔹 해결 방법: 오른쪽 회전 후 왼쪽 회전 (Right Rotation → Left Rotation)

1️⃣ 80을 기준으로 오른쪽 회전 (Right Rotation at 80)

2️⃣ 54를 기준으로 왼쪽 회전 (Left Rotation at 54)



    60
   /  \
  54   80

🔹 회전 후 (균형 유지)

이제 트리는 균형을 이루게 됩니다.

📝 예제 4: LR 회전 (Left-Right Rotation)

🔹 삽입 전

다음과 같은 트리를 고려해봅시다.

여기서 60을 삽입하면서 왼쪽 서브트리가 깊이가 2가 되어 불균형 발생

(불균형: 왼쪽-오른쪽 LR 케이스)

🔹 해결 방법: 왼쪽 회전 후 오른쪽 회전 (Left Rotation → Right Rotation)

1️⃣ 54를 기준으로 왼쪽 회전 (Left Rotation at 54)

2️⃣ 80을 기준으로 오른쪽 회전 (Right Rotation at 80)



    60
   /  \
  54   80

🔹 회전 후 (균형 유지)

이제 트리는 균형을 이루게 됩니다.

See more posts

[DB] 12.1. 트리 생성 기법

1. 무작위

2. 이진 탐색 트리(Binary Search Tree, BST)

1️⃣ 50 삽입

2️⃣ 30 삽입 (50보다 작으므로 왼쪽)

3️⃣ 70 삽입 (50보다 크므로 오른쪽)

4️⃣ 20 삽입 (30보다 작으므로 30의 왼쪽)

5️⃣ 40 삽입 (30보다 크므로 30의 오른쪽)

6️⃣ 60 삽입 (70보다 작으므로 70의 왼쪽)

7️⃣ 80 삽입 (70보다 크므로 70의 오른쪽)

3. 밸런스 트리

AVL 트리 (Adelson-Velsky and Landis Tree)

예제 1: LL 회전 (Right Rotation)

🔹 삽입 전

🔹 해결 방법: 오른쪽 회전(Right Rotation)

🔹 회전 후 (균형 유지)

📝 예제 2: RR 회전 (Left Rotation)

🔹 삽입 전

🔹 해결 방법: 왼쪽 회전(Left Rotation)

🔹 회전 후 (균형 유지)

📝 예제 3: RL 회전 (Right-Left Rotation)

🔹 삽입 전

🔹 해결 방법: 오른쪽 회전 후 왼쪽 회전 (Right Rotation → Left Rotation)

🔹 회전 후 (균형 유지)

📝 예제 4: LR 회전 (Left-Right Rotation)

🔹 삽입 전

🔹 해결 방법: 왼쪽 회전 후 오른쪽 회전 (Left Rotation → Right Rotation)

🔹 회전 후 (균형 유지)

More articles

[CSS] 8. Input 디자인

[DB] 12.2. 트리 탐색 기법

[DB] 10. 통계 쿼리 함수들

[CSS] 7. Grid-Layout