연쇄적으로 일어나는
avl 중간 노드 지워지면 [ ]
avl트리만들때 지우개 쓰기
8 → 9 → 10 → 2 → 1 → 5 → 3 → 6 → 4 → 7 → 11 → 12연
bst 에서 delete코드 ,
알고리즘 이해
rotate(x)이해[ ]🍇
1차 회전 (Left Rotation): 자식 노드인 10과 20을 먼저 회전시킵니다. ㅡ근데 마음대로 이렇게 해도되는이유가 뭐지
그니깐 대충 밑에 잇는거 순서바꾸는거같은데
2-3 삭제
Step 2: 70 삭제 (Merging & Height Reduction)
- 교체: 내부 노드 70을 삭제하기 위해 중위 후속자인 80과 위치를 바꿈. 이제 리프 노드 위치에 있는 70을 삭제함.
- 리프 언더플로우: 80이 있던 자리가 비게 됨. 왼쪽 형제 [60]은 키가 하나뿐이라 빌려줄 수 없음.
- 1차 합치기: 비어있는 오른쪽 자식 + 형제 [60] + 부모에 있던 80(원래 70자리)을 합쳐서 [60, 80] 노드를 만듦.
- 부모 언더플로우: 70이 있던 부모 노드가 비어버림. 이제 이 노드의 형제인 [25, 35]를 확인.
- 2차 합치기 (연쇄): 형제 [25, 35]는 키가 2개이므로 사실 여기서 **빌려오기(Redistribution)**가 가능함!
- 루트 50을 비어있는 오른쪽 부모 자리로 내려보냄.
- 왼쪽 형제의 가장 큰 키 35를 루트로 올림.
- 35의 오른쪽 자식이었던 [40] 노드를 내려온 50의 왼쪽 자식으로 붙여줌.
- 이때, 35와 50 사이에 끼어있던 [40] 노드가 짐을 싸서 이동합니다.
- 빌려올 수 있을 때(Redistribution): 트리의 높이가 유지됩니다. (위의 10 삭제, 70 삭제 후 부모 단계)
- 빌려올 수 없을 때(Merge): 부모 노드의 키를 소모하며,
- 부모까지 비어버리면 트리 높이가 줄어듭니다.[ ] 이경우
- 10이 있던 자리가 비었습니다. 형제인 [30]을 보니 2-노드(키 1개)입니다. 빌려올 수 없습니다.
- 합치기: 형제 30과 부모 20을 합쳐서 하나의 노드 [20, 30]을 만듭니다.
(부모를 내리ㅁ)
(이떄 원래 부모자리에 빈공간이 생김)
>(그다음 어케 해야하지 )
- 형제 노드인 [75]를 봅니다. [75]도 키가 1개뿐이라 빌려올 수 없습니다.
- 결과: 다시 **합병(Merge)**을 합니다. 부모인 [50]을 내려서 형제 [75]와 합칩니다.
왼쪽이나 오른쪽 형제 노드가 3-노드라면이때 형제노드는 부모가 같아야하던가
ㅇㅇ
부모가 키를 2개 가진 3-노드일 때, 자식 중 하나가 비어버리면(언더플로우) 어떻게 되는가"**입니다.
결론부터 말씀드리면, 부모가 부자(3-노드)라면 자식들끼리 합병해도 트리의 높이가 줄어들지 않고, 부모만 2-노드로 바뀝니다.
2-3 삭제 유형
삭제 과정 (유형별 정리)
삭제는 삽입보다 까다로우며, 크게 3가지 상황으로 나뉩니다. 핵심은 **"리프 노드에서 삭제되도록 유도하고, 트리의 균형(높이)을 유지하는 것"**입니다.
유형 1: 삭제할 키가 리프(Leaf) 노드에 있고, 그 노드가 3-노드일 때
- 방법: 그냥 삭제하면 끝입니다. (남은 키가 1개 있으므로 트리의 구조가 유지됨)
- 예: 위 최종 형태에서 37을 삭제하면 그냥 [40]이 됨.
유형 2: 삭제할 키가 리프 노드에 있는데, 그 노드가 2-노드일 때 (언더플로우)
노드에 키가 없어지면 트리의 형식이 깨집니다. 이때는 주변에서 빌려와야 합니다.
- 형제에게 빌리기 (Redistribution): 왼쪽이나 오른쪽 형제 노드가 3-노드라면, 부모를 거쳐서 키를 하나 가져옵니다.
- 형제와 합치기 (Merging): 형제도 2-노드라 빌려줄 수 없다면, 부모의 키를 내려서 형제와 합칩니다. 이때 부모 노드에 언더플로우가 발생하면 다시 위로 올라가며 같은 과정을 반복합니다.
유형 3: 삭제할 키가 내부(Internal) 노드에 있을 때
- 방법: 이진 탐색 트리(BST)와 비슷합니다. 삭제할 키의 중위 후속자(In-order Successor, 오른쪽 자식 중 가장 작은 값) 또는 **중위 선행자(In-order Predecessor, 왼쪽 자식 중 가장 큰 값)**와 자리를 바꿉니다.
- 자리를 바꾸면 삭제할 키는 리프 노드로 내려가게 됩니다.
- 이제 유형 1이나 유형 2의 방법으로 리프 노드에서 삭제를 진행합니다.
자식이 하나만 있는 경우 (현재 예시 상황)
질문하신 트리에서 90은 자식(100)이 하나 있습니다. 이때도 "대체 자식(Successor)"을 복잡하게 찾을 필요가 없습니다.
- 방법: 90을 삭제하고, 그 외동자식(100)을 90의 자리로 그대로 올립니다.
(avl에서 삭제 )
아래의 난수 리스트를 순서대로 삽입하여 AVL 트리를 생성했습니다.
삽입 리스트: [44, 17, 78, 32, 50, 88, 48, 62, 54]
(이진트리로 만들고 한번에 바꾸는게 아니라 불균형 일어날때마다 바꾸기 )
원칙 1. "인오더(In-order) 순서는 절대 변하지 않는다"
트리가 아무리 회전하고 난리를 쳐도, 노드들을 왼쪽-나-오른쪽 순으로 읽은 값의 크기 순서는 절대로 바뀌면 안 됩니다.
원래 트리 순서: 10 - 30 - 35 - 37 - 40 - 60 - 80
실수하신 경우: 만약 40을 35의 오른쪽에 붙이면? ... 30 - 35 - 40 - 37 - 60 ... 순서가 됩니다. 37보다 큰 40이 37보다 왼쪽에 있게 되죠? 이건 이진 탐색 트리 규칙 위반입니다.
근데 삭제하고 균형맞출때 자꾸 40 을 35의 오른쪽 자식으로 다는 실수를함
애초에 60 의왼쪽자식인데
[60] (BF: 1)
/ \
[30] [80] (BF: -1)
/ \ \
[10] [40] [90]
/
[35]
90삭제해도 80은 밸런스 안깨짐
ㅡ자기 자식들 높이 비교하는거니깐
- 서론: 탐색 구조의 흐름
복습 내용: 연결 리스트(Linked List), 정렬된 배열(Sorted Array), 이진 검색 트리(BST), 최적 이진 검색 트리(Optimal BST).
오늘의 주제: 이진 검색 트리의 일종이지만 '균형'을 강제로 맞추는 AVL 트리와 새로운 형태의 균형 트리인 2-3 트리.
- AVL 트리 (AVL Tree)
(1) 정의 및 특징 (Slide 56)
유래: 만든 사람(Adelson-Velsky, Landis)의 이름 앞글자를 따서 AVL 트리라고 부릅니다.
균형 조건 (HB(1) 트리): 모든 노드에 대해 왼쪽 서브트리의 높이(hL)와 오른쪽 서브트리의 높이(hR) 차이가 1 이하여야 합니다. (차이 1 이하)
목적: BST가 한쪽으로 치우쳐 성능이 O(n)으로 떨어지는 것을 방지하고, 항상 O(log n)을 보장하기 위함입니다.
(2) 트리의 재구성: 회전(Rotation) (Slide 57)
데이터 삽입 후 균형이 깨지면(높이 차가 2 이상) 트리를 회전시켜 균형을 맞춥니다.
LL 회전 / RR 회전: 한 방향으로 치우친 경우 부모와 자식의 위치를 바꿔 균형을 맞춤.
LR 회전 / RL 회전: 꺾인 형태로 치우친 경우, 중간 노드를 올리는 방식(Double Rotation).
(3) 삽입 예시 및 추적 (Slide 60~69)
교수님은 숫자를 직접 쓰며 삽입 과정을 설명하셨습니다. (예: 10, 5, 3 삽입 시 10의 왼쪽 높이는 2, 오른쪽은 0이 되어 균형이 깨짐 -> 재구성 필요)
복합 예시 (Slide 58): 'c'나 'e'가 추가될 때 기존 자식 노드들의 위치가 어떻게 변하는지가 중요합니다. 새로운 부모가 된 노드보다 작으면 새로운 자식의 오른쪽에, 크면 부모의 오른쪽/왼쪽 밑에 다는 식의 위치 조정이 필요합니다.
(4) 성능 및 특징 (Slide 70, 77)
높이: 노드 개수가 n일 때 높이 h < 2 log2 n을 유지합니다.
성능: 실험 결과(Slide 77), 단순 BST보다 삽입(put) 시 재구성 비용 때문에 약간 느릴 수 있지만, 최악의 경우에도 항상 O(log n)을 보장한다는 강점이 있습니다.
(5) Java 구현 (Slide 71, 73)
노드 구조에 높이 값을 저장하는 aux 필드를 추가합니다.
[Node 구조]codeJava
public class Node<K,V> {
K key; V value;
int N; // 노드 수
int aux; // 노드의 높이 (리프 노드 = 1)
Node<K,V> left, right, parent;
public int getAux() { return aux; }
public void setAux(int value) { aux = value; }
}[재구성 핵심 로직 - rotate & restructure]codeJava
protected void rotate(Node<K,V> x) {
Node<K,V> y = x.parent;
Node<K,V> z = y.parent;
// 부모 z와 x를 연결
if (z == null) { root = x; x.parent = null; }
else relink(z, x, y == z.left);
// LL/RR에 따른 자식 노드 교체 및 회전
if (x == y.left) { relink(y, x.right, true); relink(x, y, false); } // LL
else { relink(y, x.left, false); relink(x, y, true); } // RR
}
protected Node<K,V> restructure(Node<K,V> x) {
Node<K,V> y = x.parent;
Node<K,V> z = y.parent;
// LL or RR인 경우 한 번 회전
if ((x == y.left) == (y == z.left)) { rotate(y); return y; }
// LR or RL인 경우 두 번 회전 (Double Rotation)
else { rotate(x); rotate(x); return x; }
}3. 2-3 트리 (2-3 Tree)
(1) 정의 및 성질 (Slide 78~79)
교수님은 "아주 재미있는 트리"라고 소개하셨습니다.
- 노드의 종류:
- 2-node: 키 1개, 자식 2개.
- 3-node: 키 2개, 자식 3개.
- 완벽한 균형: 모든 리프 노드(Leaf Node)의 레벨이 항상 동일합니다.
- 탐색 (Slide 80): 키가 2개인 경우(3-node), 첫 번째 키보다 작으면 왼쪽, 사이값이면 중간, 두 번째 키보다 크면 오른쪽으로 탐색합니다.
(2) 삽입(Insertion) - Bottom-up 방식 (Slide 81~83)
2-3 트리의 삽입은 아래에서 위로 올라가는 특징이 있습니다.
- 항상 리프 노드에 먼저 삽입을 시도합니다.
- 노드에 공간이 있으면(2-node가 3-node로 변함) 끝납니다.
- 공간이 없으면(3-node에 삽입 시도) **분할(Split)**이 일어납니다.
- 3개의 키 중 작은 것은 왼쪽, 큰 것은 오른쪽 노드로 나누고, 중간 값은 부모 노드로 올립니다.
- 이 과정이 루트까지 반복되어 루트가 분할되면 트리의 높이가 한 단계 높아집니다.
[2-3 트리 삽입 코드]codeC
(삽입 코드는 안나오려나 )
void insert23 (two_three_ptr *t, element y) {
two_three_ptr q = NULL, p;
if (!(*t)) new_root(t, y, NULL);
else {
p = find_node(*t, y); // 삽입할 리프 노드 찾기
while (1) {
if (p->data_r.key == INT_MAX) { // 2-node인 경우
put_in(&p, y, q); break; // 그냥 넣고 종료
} else { // 3-node인 경우 분할 발생
split(p, &y, &q);
if (p == *t) { // 루트가 분할되면 새로운 루트 생성
new_root(t, y, q); break;
}
p = p->parent; // 부모로 올라가며 반복
}
}
}
}(3) 삭제(Deletion) (Slide 84~87)
- 리프 노드로 변환: 삭제할 키가 내부 노드에 있다면 Inorder Successor/Predecessor와 교체하여 리프 노드 삭제 문제로 바꿉니다.
- 삭제 케이스:
- 3-node에서 삭제: 키만 지우면 되므로 간단합니다.
- 2-node에서 삭제: 해당 노드가 비게 되므로(Underflow), 형제 노드에서 키를 빌려오거나(Rotation), 부모 노드의 키를 내려 형제와 합칩니다(Combine).
- 이 과정에서 부모 노드가 비게 되면 다시 위로 올라가며 같은 작업을 반복합니다.
4. 결론 및 다음 예고
- AVL 트리는 삽입 시마다 매번 엄격하게 재구성을 해야 하는 비용이 발생합니다.
- 이런 재구성 비용을 조금 낮추면서도 균형을 유지하는 것이 **레드-블랙 트리(Red-Black Tree)**이며, 자바의 TreeMap 등이 이를 사용합니다.
모든 노드는 각자 **'왼쪽 서브트리의 높이'**와 **'오른쪽 서브트리의 높이'**를 가지고 있습니다.
- 공식: |왼쪽 높이 - 오른쪽 높이| ≤ 1
- 이 차이가 2가 되는 순간, 그 노드를 기준으로 트리를 다시 잡아야(재구성해야) 합니다.
1-3있고 오른쪽에 7-10-20인데,
여기 엄청 높이 깊어도되나,ㄴㄴ
누구랑 누구를 비교해야하는거지
일단 코드말고 실제 문제 풀이할때 안놓치려면 어케 해야하지,
부모를 계속 올라가면서 확인하라고 햇던것같은데(재구성 해야하는지 아닌지 )
삽입 순서: 8 → 9 → 10 → 2 → 1 → 5 → 3 → 6 → 4 → 7 → 11 → 12
주의: 루트인 9까지 가기 전에 8에서 먼저 깨졌습니다. 8부터 고쳐야 합니다.
1-2-8이 하나의 셑트임
9 (h=4)
/ \
8 (h=3) 10 (h=1)
/
2 (h=2)
/
1 (h=1)
LR / RL (Double Rotation): 꺾인 형태이므로, 먼저 일직선으로 펴준 뒤(1차 회전), 다시 중간값을 위로 올립니다(2차 회전). 결국 세 값 중 중간값이 최종 부모가 됩니다.
<<이거 문제 푸는거랑 달랏던것같은데 예제로 어케 한다고 간단한 예제 문제풀이방식말고 코드방식에서는 double이잖아
- 2-3 트리: 빈 자리를 찾아 내려가는 건 같지만, 새로운 노드를 밑에 매달지 않고 기존의 리프 노드에 "합체" 시킵니다. (트리가 옆으로 뚱뚱해지다가 위로 자람)
방에 3명이 모이면(기존 2명 + 새 데이터 1명), 이 노드는 **"폭발"**합니다.
- 정렬: 세 숫자 중 작은 놈, 중간 놈, 큰 놈을 순서대로 세웁니다.
- 분할: 작은 놈과 큰 놈은 각각 별도의 방(노드)을 만들어 나눠 갖습니다.
- 승진(Promote): 가장 중요한 "중간 놈"은 부모 노드로 올라갑니다.
25 삽입
<엥 나는 20옆에 드가는줄, 일단은 무조건 자식으로 드가고, 자식 자리없으면 올라오는건가
[20]
/ \
[10, 15] [25, 30]
"새 손님은 무조건 맨 밑바닥(Leaf)으로만 들어온다"
삭제
그리고 2-3에서 입력순서 주어질때, 젤 처음에는 처음 두개 어떻게 처리해야하지
- 1번째 숫자 삽입: 빈 트리에 노드 하나를 만들고 숫자를 넣습니다. (2-node 상태)
- 2번째 숫자 삽입: 새로 노드를 만들지 않고, 기존 노드의 남은 빈자리에 숫자를 집어넣습니다. (3-node 상태)
- 3번째 숫자 삽입: 이때 비로소 방이 꽉 차서 **폭발(Split)**이 일어나고, 중간값이 위로 올라가면서 층수가 2층으로 높아집니다.
1. AVL 트리 삭제: "모빌 무게 맞추기"
AVL 트리는 왼쪽과 오른쪽의 **높이(무게)**가 비슷해야 하는 모빌이라고 생각하세요.
- 일단 지우기: 숫자를 하나 뺍니다. (지울 때는 이진트리 방식 그대로!)
- 기울었나 확인: 숫자를 뺐더니 모빌이 한쪽으로 확 기울었는지(높이 차이가 2) 봅니다.
- 뱅글 돌리기(회전): 너무 기울었으면 우리가 배운 LL, RR, LR, RL로 뱅글 돌려서 수평을 맞춥니다.
- 끝까지 확인: 이게 중요해요! 밑에서 수평을 맞췄는데, 그 바람에 그 윗부분이 또 기울 수도 있어요. 그래서 루트(꼭대기)까지 올라가면서 계속 "기울었니?" 물어보고 수평을 맞춰야 합니다.
2. 2-3 트리 삭제: "방 비우지 않기"
2-3 트리는 모든 방(노드)에 **최소 한 명(숫자 1개)**은 살고 있어야 하는 아파트예요.
- 방 비우기: 숫자를 지웁니다.
- 방이 비었나?(Underflow): 숫자를 지웠는데 그 방에 아무도 안 남았으면 문제가 생깁니다. (방이 텅 비면 안 됨!)
- 옆집 보기: 텅 빈 방을 채우기 위해 **옆집(형제 노드)**을 봅니다.
- 옆집이 부자면(숫자가 2개): 한 명만 빌려달라고 합니다. 부모를 거쳐서 한 명이 내려옵니다. (빌려오기)
- 옆집도 가난하면(숫자가 1개): 빌려줄 게 없죠? 그럼 부모님까지 내려오라고 해서 옆집이랑 합쳐버립니다. (합치기)
- 부모님이 걱정: 부모님이 옆집이랑 합치려고 내려오셨는데, 그 바람에 부모님 방이 비어버릴 수도 있죠? 그럼 부모님도 똑같이 옆집에 빌리거나 합쳐야 합니다. 이 과정이 루트(꼭대기)까지 올라갈 수 있어요.
- 키가 줄어듦: 만약 맨 꼭대기(루트) 방까지 비어서 옆집이랑 합쳐지면, 아파트 층수가 한 층 낮아집니다
50 (Root)
/
30 70
/
20 40
근데 이거 삭제할때 재구성할떈 뭘로 해야하지
삽입일떄는 찾는거 쉬웟는데,
삭제일떄는 50 30 20으로 해야하는지
50 30 40으로 하는지
// 1. 왼쪽이 더 높으면? 당연히 왼쪽 자식 선택
if (height(x.left) > height(x.right)) return x.left;
// 2. 오른쪽이 더 높으면? 당연히 오른쪽 자식 선택
if (height(x.left) < height(x.right)) return x.right;
// 3. [중요] 높이가 똑같다면? (사용자님이 질문하신 부분!)
if (x == root) return x.left; // 루트면 그냥 왼쪽
왜 "일직선"을 고집할까요?
이유는 단순합니다. 일직선(LL, RR)이면 한 번만 돌리면 되기 때문입니다.
- 일직선(LL, RR)을 선택하면: rotate 함수를 한 번만 실행하면 끝납니다. (Single Rotation)
- 지그재그(LR, RL)를 선택하면: rotate 함수를 두 번 실행해야 합니다. (Double Rotation)
[문제 3] 중간 노드 삭제 + 연쇄 합치기 (고난도)
다음 트리에서 '20'을 삭제하세요. (Slide 84의 Successor 교체 원리 적용)
- 구조:
- 루트 노드: [20, 40]
- 왼쪽 자식: [10]
- 가운데 자식: [30]
- 오른쪽 자식: [50]
[문제 3 풀이] 20 삭제 (Successor 교체 후 합치기)
- 리프로 옮기: 20은 중간 노드입니다. 20의 바로 다음 큰 숫자인 **30(Inorder Successor)**과 자리를 바꿉니다.
- 상태: 루트 [30, 40], 리프들 [10], [20], [50] (지울 놈 20은 리프로 내려옴)
- 방 비우기: 리프에 있는 20을 지우면 가운데 자식 방이 텅 비어버립니다.
- 옆집 확인: 왼쪽 형제(10)도, 오른쪽 형제(50)도 다 가난한 2-node입니다.
- 합치기:
- 부모인 루트에서 30을 내려서 왼쪽 형제 10과 합칩니다.
- 루트는 이제 [40] 하나만 남습니다.
- 자식은 합쳐진 **[10, 30]**과 원래 있던 [50] 두 개가 됩니다.결과:codeText
-
[40] / \ [10, 30] [50]
1. 규칙: "내 바로 다음으로 큰 놈" 혹은 "내 바로 직전에 작은 놈"
중간에 있는 숫자(20)를 지울 때는, 그 빈자리를 채워도 순서가 꼬이지 않을 놈을 데려와야 합니다. 그 후보는 딱 두 명뿐입니다.
- Inorder Predecessor (직전 숫자): 내 왼쪽 자식들 중 가장 큰 놈 (10)
- Inorder Successor (다음 숫자): 내 오른쪽 자식들 중 가장 작은 놈 (30)
질문하신 것처럼 10이랑 바꿔도 결과는 결국 비슷하게 나옵니다. 하지만 보통 알고리즘 교재나 강의에서는 **"오른쪽 자식 중 가장 작은 놈(Successor)"**을 데려오는 것을 표준으로 많이 가르칩니다. (Slide 84에서도 Successor를 언급하죠!)
2. 왜 꼭 "리프 노드"에 있는 놈이랑 바꿔야 하나요?
이게 핵심입니다! 2-3 트리는 삭제가 무조건 맨 밑바닥(Leaf)에서 일어나야 "옆집에서 빌리기"나 "부모랑 합치기"를 할 수 있기 때문입니다.
- 만약 루트에 있는 20을 그 자리에서 그냥 쓱 지워버리면? 루트 노드에 구멍이 뚫리는데, 이걸 메울 방법이 막막해집니다.
- 하지만 리프에 있는 30(혹은 10)과 자리를 바꾼 뒤 지우면? 구멍이 맨 밑바닥에 생기죠. 그러면 우리가 배운 "옆집 보고 빌려오기"나 "합치기"를 차례차례 적용하면서 위로 올라갈 수 있습니다.
[[ 30 ]] <- 1층 (루트)
/ \
[ 15 ] [ 50 ] <- 2층
/ \ / \
[10] [20] [40] [60] <- 3층 (리프)미션: [60]을 삭제하라!
[[ 40 ]] <- 1층 (루트)
/ \
[ 20 ] [ 60 ] <- 2층
/ \ / \
[10] [30] [50] [70, 80] <- 3층 (리프)
50,10 삭제
- 1층(루트): [40]
- 2층: 왼쪽 [20], 오른쪽 [60, 80]
- 3층(리프):
- [20] 아래: [10], [30]
- [60, 80] 아래: [50], [70], [90]
이건 최대한 리프는 그대로 둬야하나, 위쪽을 바꿔야하나
| 유형 1 | 내가 3-node일 때 | 그냥 지우고 끝 | 없음 |
| 유형 2 | 나는 2-node, 옆집은 3-node | 부모 내리고 옆집 숫자 올리기 (Rotate) | 없음 |
| 유형 3 | 나는 2-node, 옆집도 2-node | 부모 내리고 형제랑 한 방으로 합치기 (Combine) | 부모 층이 비게 됨 (연쇄 반응 가능) |
부모가 숫자 2개인 '3-node'라면
'26년1학기 > 알고리즘' 카테고리의 다른 글
| 알고리즘 )2주차 퀴즈준비 (0) | 2026.04.04 |
|---|---|
| 알고리즘) 2-3-4 &red black tree (0) | 2026.04.01 |
| 알고리즘) 복습(26.3.26) (0) | 2026.03.26 |
| 알고리즘) 강의 (26.3.25) (0) | 2026.03.25 |
| 알고리즘) 2장 코드 (25) | 2026.03.23 |