avl 어떻게 하더라 [ ㅇㅋ ]
코드 [ ]
bst코드에서 삭제도 했었던가 [ ]
더블블랙이해[ ]
1. 2-3-4 트리 (2-3-4 Tree)
(1) 정의 및 특징
- 지난 시간에 배운 2-3 트리에 **'4-노드(4-node)'**가 추가된 형태입니다.
- 4-노드: 3개의 키 값과 4개의 자식 노드(Left, Left-Mid, Right-Mid, Right)를 가집니다.
- 트리의 높이(h): log4(n+1) <= h <= log2(n+1) 사이의 높이를 유지하여 균형을 잡습니다.
(2) 주요 연산
- 검색: 2-3 트리와 동일하게 키 값의 대소 관계에 따라 4개 경로로 분기하여 탐색합니다.
- 삽입: 리프 노드에 공간이 있으면 삽입하고, 4-노드를 초과하게 되면 분할(Split)이 일어납니다. (중간 값을 부모로 올리는 방식)
- 삭제: 리프 노드에서 삭제를 수행하며, 2-노드일 경우 형제 노드에서 빌려오거나(Rotation), 합치기(Combine)를 수행합니다.
- 의의: 2-3-4 트리는 직접 구현하기보다 **레드-블랙 트리의 개념적 배경(Ideological Background)**으로서 중요합니다.
2. 레드-블랙 트리 (Red-Black Tree, RBT)
(1) 등장 배경: 왜 레드-블랙 트리인가?
- 2-3-4 트리의 단점: 모든 노드가 최대 3개의 키와 4개의 링크를 저장할 공간을 미리 확보해야 하므로 메모리 낭비가 발생합니다.
- 해결책: 모든 노드가 하나의 키만 갖는 이진 트리(Binary Tree) 형태로 2-3-4 트리를 표현한 것이 레드-블랙 트리입니다.
(2) 2-3-4 트리와의 매핑(Mapping) 방식
노드에 색깔(Black/Red) 속성을 부여하여 구분합니다.
- 2-노드: 하나의 블랙(Black) 노드.
- 3-노드: 하나의 블랙 노드 + 하나의 레드(Red) 자식 노드.
- 4-노드: 하나의 블랙 노드 + 두 개의 레드 자식 노드.
- 참고: 색깔을 노드가 아닌 링크(Link)에 부여하는 방식도 있으나, 메모리 효율성 측면에서 노드에 부여하는 방식이 더 선호됩니다.
(3) 레드-블랙 트리의 4가지 핵심 성질
- 루트 노드는 항상 블랙입니다.
- 레드 노드의 자식은 항상 블랙입니다. (레드-레드 연속 발생 불가)
- 블랙 노드는 연속될 수 있습니다. (2-노드가 연속되는 경우)
- 리프에서 루트까지 가는 경로의 블랙 노드 수는 동일합니다. (2-3-4 트리의 모든 리프 레벨이 같다는 성질에서 기인)
(4) 높이 및 성능
- 레드-블랙 트리의 최대 깊이는 **2 * log2(n+1)**보다 작거나 같습니다.
- 따라서 아무리 불균형해도 최악의 경우 성능이 **O(log n)**을 보장합니다.
3. 레드-블랙 트리의 연산 상세
(1) 삽입 (Insertion)
- 이진 탐색 트리 방식으로 노드를 추가하고, 새로 추가된 노드의 색깔은 항상 **레드(Red)**로 설정합니다.
- 만약 부모 노드가 블랙이면 그대로 종료됩니다.
- 부모 노드가 레드일 경우 (Double Red 발생):
- Case 1: 삼촌(부모의 형제) 노드가 레드일 때 (Recoloring/Split)
- 부모와 삼촌을 블랙으로 바꾸고, 할아버지를 레드로 바꿉니다. 할아버지가 레드가 되었으므로 위쪽으로 올라가며 다시 체크합니다.
- Case 2: 삼촌 노드가 블랙이거나 없을 때 (Restructuring/Rotation)
- AVL 트리처럼 회전(LL, LR, RL, RR)을 통해 균형을 맞추고 색깔을 재조정합니다.
- Case 1: 삼촌(부모의 형제) 노드가 레드일 때 (Recoloring/Split)
(2) 삭제 (Deletion)
- 매우 복잡하지만 기본 원칙은 2-3-4 트리의 삭제와 같습니다.
- 레드 노드 삭제: 그냥 삭제해도 트리의 성질이 유지됩니다.
- 블랙 노드 삭제: 블랙 높이가 변하므로 문제가 생깁니다.
- 삭제된 자리에 레드 노드를 올려 블랙으로 바꾸거나,
- 형제 노드의 색깔과 자식 유무에 따라 회전 또는 색깔 변경을 통해 블랙 높이를 맞춥니다.
4. 결론 및 비교
- AVL 트리 vs 레드-블랙 트리:
- 둘 다 **O(log n)**의 탐색 시간을 보장합니다.
- AVL 트리: 균형을 아주 엄격하게 잡기 때문에 탐색 속도가 미세하게 빠르나, 삽입/삭제 시 회전이 빈번합니다.
- 레드-블랙 트리: 균형을 조금 덜 엄격하게 잡는 대신, 삽입/삭제 시 트리의 재구성(회전) 빈도가 적어 전반적인 성능이 더 안정적이고 효율적입니다.
- 구현 팁: 노드 구조체 내의 aux 변수를 color 속성(0: Black, 1: Red)으로 활용할 수 있습니다.
잠깐! 이럴 땐 부모가 키가 넉넉한지 봅니다. 부모 [20, 40]은 키가 2개나 있습니다.<그래서 그다음 뭘한는데, 20을 내리는지 40을 내리는지
- 왼쪽 형제와 작업할 때: 내 노드와 왼쪽 형제 사이의 벽인 **'왼쪽 구분자(20)'**를 내립니다.
- 오른쪽 형제와 작업할 때: 내 노드와 오른쪽 형제 사이의 벽인 **'오른쪽 구분자(40)'**를 내립니다.
왼쪽 형제 노드를 봅니다. 오! **[10, 20]**이네요. 키가 2개나 있으니 하나 정도는 빌려줄 수 있는 **'부자 형제'**입니다.
3단계: 빌려오기(Rotation) 시작! (누구를 움직일까?)
이때 가장 중요한 건 **"부모를 거쳐서 빌려온다"**는 것입니다. 그냥 형제의 키를 슥 가져오는 게 아니에요.
- 부모의 키(40)를 내립니다: 지워진 50의 빈자리로 부모인 40을 내려보냅니다. (이제 40이 자식 노드가 됩니다.)
- 형제의 키(20)를 올립니다: 왼쪽 형제 [10, 20] 중에서 부모와 가장 가까운(가장 큰 값인) 20을 부모 자리로 올려보냅니다.
- 나머지는 정리: 형제 노드에는 이제 10만 남게 됩니다.
💡 만약, 형제도 가난했다면? (합치기 - Merge)
만약 왼쪽 형제가 [10, 20]이 아니라 그냥 [10] 하나뿐이었다면 어떻게 될까요? (즉, 둘 다 2-노드일 때)
- 부모를 끌어내립니다: 부모의 40을 아래로 내립니다.
- 다 합칩니다: 왼쪽 형제 10 + 부모 40 + (텅 빈 50의 자리)를 하나로 뭉쳐서 **[10, 40]**이라는 새로운 노드를 만듭니다.
[20]
/ \
[10] [30, 40]20(리프아닌 노드 삭제할때 )
[20, 40] (부모)
/ | \
[10] [30] [50, 60]
70넣기
[30, 50] (부모는 키가 2개로 넉넉함)
/ | \
[10] [40] [60] (형제 [40]도 가난함)10삭제
2-3 트리의 철칙: "자식의 수 = 키의 수 + 1"
(30,40 합쳐야하는 이유
- 부모: [30, 50] (키가 2개인 3-노드)
- 자식들: [10], [40], [60] (자식이 3개인 완벽한 상태)
여기서 10을 지웠다고 가정해봅시다.
부모가 키 2개를 유지하려면 자식을 3개 데리고 있어야 하는데, 자식 하나(10)가 죽어버렸습니다. 이제 부모는 선택해야 합니다.
- 빌려오기: 다른 자식이 키를 2개 갖고 있다면 하나를 뺏어와서 빈자리를 채우겠지만, [40]과 [60] 모두 가난해서 빌려줄 게 없습니다.
- 강등(Merge): 결국 부모는 "내가 키 2개를 유지할 자격이 없구나"라고 인정하고, 키 하나(30)를 아래로 내려보냅니다.
[20, 40]
/ | \
[10] [30] [50]20삭제
바로 지우면 안되고 리프로 내려가게 해야
대역 찾기: 20의 오른쪽 자식 중 제일 작은 30과 값을 바꿉니다.
[50]
/ \
[20] [80]
/ \ / \
[10] [30] [70] [90]
문제: 루트 노드인 50을 삭제하라.
- 후계자 찾기: 50의 오른쪽 자식 중 가장 작은 값 70과 바꿉니다.
(아 바로 왼쪽인 80과 자리 바꾸는게 아니네 )
0. 삽입의 대전제
- **새 노드(X)**는 무조건 **레드(Red)**로 넣습니다.
- 루트 노드는 무조건 **블랙(Black)**입니다.
- Double Red 발생: 부모(P)가 레드일 때만 해결 작업에 들어갑니다.
| 구분 | 조건 | 해결책 | 위로 올라가는가? |
| 케이스 1 | 삼촌이 레드 | 부모/삼촌 블랙, 할아버지 레드 | YES (계속 체크) |
| 케이스 2 | 삼촌 블랙 + 꺾인 모양 | 회전해서 직선으로 만듦 | (케이스 3으로 전환) |
| 케이스 3 | 삼촌 블랙 + 직선 모양 | 회전 + 부모 블랙, 자식 레드 | NO (즉시 종료) |
🌟 교수님 강조 포인트
"레드-블랙 트리가 왜 효율적인가?"라고 물으신다면, 케이스 1(Recoloring) 때문이라고 답하시면 됩니다.
- AVL 트리는 매번 회전(Restructuring)을 해야 하지만,
- 레드-블랙 트리는 색깔만 바꾸고(Recoloring) 넘어가는 경우가 많기 때문에 훨씬 빠릅니다!
레드-블랙 트리 삽입의 3가지 케이스
1. 케이스 1: 삼촌이 레드일 때 (Recoloring)
상황: 20, 10, 30이 있는 상태에서 5를 삽입할 때
- 초기 상태: 20(B)가 루트이고, 자식으로 10(R), 30(R)이 있음.
- 숫자 5 삽입: 10(R)의 왼쪽 자식으로 5(R)가 들어감.
- 문제 발생: 10(R)과 5(R)가 Double Red!
- 삼촌 확인: 부모(10)의 형제인 삼촌(30)이 레드임.
[20(Black)] <-- 할아버지
/ \
[10(Red)] [30(Red)] <-- 부모와 삼촌 모두 레드 (Case 1)
/
[5(Red)] <-- 나(새 노드)
▼ [해결: 부모와 삼촌을 블랙으로, 할아버지를 레드로!]
[20(Red)] <-- 할아버지가 레드가 됨
/ \
[10(Black)] [30(Black)] <-- 부모와 삼촌이 블랙이 됨
/
[5(Red)]
▼ [마무리: 루트는 항상 블랙이어야 하므로 20을 블랙으로 변경]
[20(Black)]
/ \
[10(Black)] [30(Black)]
/
[5(Red)]2. 케이스 2: 삼촌이 블랙 + 꺾인 모양 (LR 회전 필요)
상황: 50(B), 20(R)이 있는 상태에서 30을 삽입할 때
- 초기 상태: 50(B) 루트, 왼쪽 자식 20(R).
- 숫자 30 삽입: 20(R)의 오른쪽 자식으로 30(R)이 들어감.
- 문제 발생: 20(R)과 30(R)이 Double Red!
- 삼촌 확인: 할아버지(50)의 오른쪽 자식(삼촌)이 없음(블랙).
- 모양 확인: 50-20-30이 왼쪽으로 갔다 오른쪽으로 꺾인 LR 모양.
[50(Black)] <-- 할아버지
/ \
[20(Red)] [NULL(B)] <-- 삼촌이 블랙(NULL)이고 꺾인 모양 (Case 2)
\
[30(Red)] <-- 나(새 노드)
▼ [해결: 부모 20을 기준으로 좌회전하여 직선으로 펴기]
[50(Black)] <-- 할아버지
/
[30(Red)] <-- 부모 자리에 30이 올라옴
/
[20(Red)] <-- 나 자리에 20이 내려감
▼ [직선이 되었으므로, 이제 케이스 3으로 넘어가서 해결!]
(이때 회전시킴)
3. 케이스 3: 삼촌이 블랙 + 직선 모양 (LL 회전 + 색칠)
상황: 위 케이스 2에서 이어진 50(B), 30(R), 20(R) 상태 (LL 모양)
- 상태 확인: 50-30-20이 왼쪽으로 곧게 뻗은 LL 직선 모양.
- 삼촌 확인: 여전히 삼촌(50의 오른쪽)은 블랙(NULL).
[50(Black)] <-- 할아버지
/ \
[30(Red)] [NULL(B)] <-- 삼촌이 블랙이고 직선 모양 (Case 3)
/
[20(Red)]
▼ [해결: 할아버지 50을 기준으로 우회전 + 부모 30을 블랙으로!]
[30(Black)] <-- 중간값인 30이 새로운 부모가 되며 블랙으로 변신!
/ \
[20(Red)] [50(Red)] <-- 자식 노드들은 레드로 색칠
삭제의 대원칙 (BST와 동일)
- 지울 노드가 내부 노드라면? 오른쪽 자식의 최소값(후계자)과 값을 바꾼 뒤, 리프 노드 상태에서 삭제합니다.
- 이제 우리는 **"자식이 없거나 하나뿐인 노드(오른쪽자식만 있겟지)"**만 지우면 됩니다.
(나보다 큰값중 가장 작은값 가져왔다면 )
레드-블랙 트리(RBT) 삭제는 **"블랙 높이(루트에서 리프까지의 검정색 노드 수)를 어떻게 일정하게 유지하느냐"**가 핵심입니다.
교수님이 강조하신 2-3-4 트리의 원리를 섞어서, 가장 많이 나오는 3가지 핵심 예제로 설명해 드릴게요.
예제 1: 레드(Red) 노드 삭제 (가장 쉬운 경우)
상황: 아래 트리에서 10을 삭제하라.
[20(B)]
/ \
[10(R)] [30(B)]- 분석: 지우려는 노드 10이 레드입니다.
- 해결: 레드는 블랙 높이에 아무런 영향을 주지 않습니다. 그냥 지워버리면 끝입니다.
- 결과:(각 경로의 블랙 높이가 여전히 1로 일정함)
[20(B)] \ [30(B)]
예제 2: 블랙(Black) 삭제 + 레드(Red) 자식이 있을 때
상황: 아래 트리에서 20을 삭제하라.
[20(B)] <-- 지울 노드
/
[10(R)] <-- 레드 자식- 분석: 블랙인 20을 지우면 그쪽 경로의 블랙 높이가 하나 줄어듭니다.
- 해결: 자식인 10을 20의 자리로 올리고, 색깔을 블랙으로 바꿉니다.
- 결과:(블랙 노드가 사라진 자리를 레드가 블랙으로 변신해서 채워줌. 균형 유지!)
[10(B)]
예제 3: 블랙(Black) 삭제 + 자식도 블랙(NULL)일 때 (가장 복잡!)
이 경우를 '더블 블랙(Double Black)' 상태라고 합니다. 블랙이 하나 모자란 상태죠. 이때는 **형제(Sibling)**를 봐야 합니다.
유형 A: 형제도 가난할 때 (합치기 - Merge)
상황: 루트 20(B), 왼쪽 10(B), 오른쪽 30(B)인 트리에서 10을 삭제하라.
[20(B)]
/ \
[10(B)] [30(B)] <-- 형제도 블랙, 형제 자식도 없음(블랙)- 분석: 10을 지우면 왼쪽 경로에 블랙이 0개가 됩니다.
- 해결: 2-3-4 트리에서 부모를 끌어내려 합치는 것과 같습니다.
- 형제인 30의 색깔을 레드로 바꿉니다. (오른쪽 블랙 높이도 하나 낮춤)
- 부모인 20에게 "블랙 하나 더 가져!"라고 책임을 넘깁니다.
- 부모가 원래 레드였다면 블랙이 되고 끝나지만, 여기선 부모가 루트이므로 그냥 블랙으로 유지하고 끝납니다.
- 결과:
[20(B)] \ [30(R)]
유형 B: 형제가 부자일 때 (빌려오기 - Rotation) 🌟 중요!
상황: 루트 20(B), 왼쪽 10(B), 오른쪽 40(B), 40의 자식 50(R)인 트리에서 10을 삭제하라.
[20(B)]
/ \
[10(B)] [40(B)]
\
[50(R)] <-- 형제 40에게 레드 자식이 있음! (부자)- 분석: 10을 지우면 왼쪽이 비지만, 형제 40에게 빌려올 레드가 있습니다.
- 해결: 2-3-4 트리에서 **회전(Rotation)**하는 것과 같습니다.
- 할아버지(20)를 기준으로 좌회전합니다.
- 새로운 부모가 된 40은 원래 부모의 색(Black)을 가져가고, 자식들(20, 50)은 모두 블랙으로 칠합니다.
- 결과:(완벽하게 블랙 높이 2를 회복하며 종료!)
[40(B)] / \ [20(B)] [50(B)]
💡 삭제 퀴즈 대비 요약 (이것만 외우세요!)
- 지우는 놈이 레드다? -> 그냥 삭제.
- 지우는 놈이 블랙인데 자식이 레드다? -> 자식 올리고 블랙으로 칠함.
- 지우는 놈이 블랙이고 자식도 블랙이다? (더블 블랙)
- 형제도 가난하면: 형제를 레드로 바꾸고 부모에게 책임 전가 (합치기).
- 형제가 부자(레드 자식 있음)면: 회전 시키고 부모 색깔 맞춘 뒤 자식들 블랙칠 (빌려오기).
레드-블랙 트리(RBT) 삭제 시 "자식이 둘 다 레드(Red)인 블랙 노드"를 직접 지우는 경우는 절대로 없습니다.
지우려는 노드가 '블랙'이고 자식도 없는 경우
(자식이 블랙인 경우는 없는건가 )
Case 2의 조건 (언제 발생하나?)
- 나의 형제(S)가 Black입니다.
- 형제의 자식(조카들)도 모두 Black입니다. (NIL 노드 포함)
- (부모님의 색깔은 상관없습니다. Red일 수도, Black일 수도 있습니다.)
2. 해결 방법 (공식)
- 형제(30)의 색을 Red로 바꿉니다. (형제의 블랙을 하나 뺏음)
- DB(나)가 가진 블랙 하나를 부모(20)에게 넘깁니다.
- 나는 이제 정상적인 Black 노드가 됩니다.
- 부모(20)는 블랙을 하나 더 받았으므로 상태가 변합니다.
3. 결과 (두 가지 상황 발생)
부모가 블랙을 하나 더 받았을 때, 원래 부모의 색깔에 따라 결과가 달라집니다.
상황 A: 부모가 원래 Red였던 경우 (상황 종료)
- Red + Black = Black
- 부모가 Red에서 Black으로 변하면서 트리의 균형이 완벽하게 맞춰집니다. 해결 완료!
상황 B: 부모가 원래 Black이었던 경우 (계속 진행)
- Black + Black = Double Black (DB)
- 부모가 다시 더블 블랙이 됩니다.
- 이때는 부모 노드를 기준으로 다시 Case 1, 2, 3, 4를 판단해서 해결해야 합니다. (문제가 트리 위쪽으로 전이됨)
10
/ \
5 20
/ \
15 25
avl에서
AVL 트리에서 노드를 삭제한 후,
제된 지점부터 루트 노드까지 올라가며 BF를 확인한다"
- 삽입할 때: 불균형이 발생한 곳에서 딱 한 번만 회전하면 전체 트리의 균형이 다 맞습니다. (그 위로는 더 이상 안 봐도 됨)
- 삭제할 때: 회전을 한 번 해서 해당 구간의 균형을 맞춰도, 그 상위 노드에서 다시 불균형이 생길 수 있습니다.
AVL 트리도 레드-블랙 트리나 일반 이진 탐색 트리(BST)와 똑같습니다.
AVL 트리 역시 내부 노드(자식이 있는 노드)를 바로 삭제하는 것이 아니라, 리프 노드(또는 자식이 하나뿐인 노드)와 자리를 바꾼 뒤에 삭제해야 합니다.
- 자식이 1개: 삭제할 노드 자리에 그 자식 노드를 끌어올리고, 부모 노드부터 균형을 확인합니다.
20 삭제
40
/ \
20 60
/ / \
10 50 80
/ \
70 90
\
100
50삭
50
/ \
30 70
/ \ \
20 40 80
/
35
원래 60이 있던 자리를 지웁니다. 이때 60의 오른쪽 자식이었던 65를 60의 부모였던 70의 왼쪽 자식으로 붙입니다. (70 입장에서는 왼쪽 자식 60이 사라졌으니 60의 자식인 65를 입양하는 것)
왜 자식이 둘인 노드는 직접 안 지우나요?
레드-블랙 트리도 기본적으로 이진 탐색 트리입니다. 이진 탐색 트리에서 자식이 둘인 노드를 지울 때는 어떻게 하나요?
- 지우려는 노드와 **후계자(오른쪽 자식 중 가장 작은 값)**의 값을 바꿉니다.
- 실제 삭제는 리프로 내려간 노드를 대상으로 합니다.
중요: 어떤 노드의 후계자(오른쪽 서브트리의 최소값)는 절대로 자식을 둘 가질 수 없습니다. (자식이 있다면 오른쪽 자식 하나뿐이거나, 아예 없거나 둘 중 하나입니다.)
레드-블랙 트리에는 아주 중요한 규칙이 하나 있습니다.
**"루트 노드에서 리프(끝) 노드까지 가는 길에 있는 블랙 노드의 개수는 어느 길로 가든 모두 같아야 한다"**는 규칙입니다.
1. 왜 블랙을 물려주나요?
예를 들어, 모든 경로에 블랙 노드가 3개씩 있는 완벽한 상태였다고 해봅시다.
- 그런데 내가 블랙 노드 하나를 삭제해버렸습니다.
- 그럼 그 블랙 노드가 있던 길은 블랙이 2개로 줄어들겠죠?
- 다른 길은 여전히 3개인데, 이 길만 2개가 되면 규칙이 깨집니다.
이 문제를 해결하기 위해, 삭제된 블랙 노드가 가지고 있던 **'블랙이라는 속성(검은색 색종이 1장)'**을 그 자리에 새로 들어온 노드에게 억지로 쥐여주는 것입니다.
"야, 내가 사라지니까 이 길에 블랙이 부족해졌어. 내 검은색 색종이 네가 대신 들고 있어!"라고 하는 거죠.
2. 'Double Black(이중 흑색)'이란?
이제 그 자리에 새로 들어온 노드(대체 노드)의 상황을 봅시다.
- 원래 레드였던 노드가 들어온 경우:
- 원래 색(레드) + 물려받은 색(블랙) = 그냥 블랙 노드가 됩니다.
- 색종이 한 장만 가지게 되니 아주 깔끔하게 해결됩니다!
- 원래 블랙이었던 노드가 들어온 경우 (이게 문제!):
- 원래 색(블랙) + 물려받은 색(블랙) = **블랙이 2개(Double Black)**가 됩니다.
- 이 노드는 혼자서 **"난 블랙 노드 2인분이야!"**라고 외치고 있는 상태입니다.
3. 이게 왜 문제인가요?
컴퓨터 입장에서 노드의 색은 '레드' 아니면 '블랙'이어야 합니다. 그런데 '블랙 2인분(Double Black)'이라는 색은 실제로 존재하지 않는 가상의 상태입니다.
트리의 전체적인 블랙 개수(규칙)를 맞추기 위해 임시로 "너 2인분 해!"라고 정해놓긴 했지만, 결국 이 2인분짜리 블랙을 주변으로 넘기거나 없애서 다시 평범한 1인분 블랙 노드들로 만들어야 합니다.
'26년1학기 > 알고리즘' 카테고리의 다른 글
| 알고리즘)2주차 퀴즈 준비(2) (0) | 2026.04.05 |
|---|---|
| 알고리즘 )2주차 퀴즈준비 (0) | 2026.04.04 |
| 알고리즘) AVL Tree & 2-3 Tree (0) | 2026.03.30 |
| 알고리즘) 복습(26.3.26) (0) | 2026.03.26 |
| 알고리즘) 강의 (26.3.25) (0) | 2026.03.25 |