[Database] 21. 트리 생성 기법

1. 무작위

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

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

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

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

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

• 20이 새로운 루트가 되며,

• 10은 그대로 유지됨

🔹 회전 후 (균형 유지)

      20
     /  \
    10   30

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

🔹 삽입 전

      10
       \
        20
          \
           30

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

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

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

• 20이 새로운 루트가 되며,

• 30은 그대로 유지됨

🔹 회전 후 (균형 유지)

      20
     /  \
    10   30