2-3
삽입 순서: 40, 10, 20, 50, 30, 60, 70, 25, 15, 35, 45, 55
삭제 순서: 10, 25, 40, 35, 15
레드블랙에서
중간노드 삭제하면
(중위후속자 찾나) [ ]
근데 삭제할떄는 루트까지 올라가면서 db인지 확인해야하나, 아니면 db인지 확인하는법잇나
레드블랙
이제 문제 내줘 풀이도, 높이 3정도, 일단, 리프에서 삭제되는 경우마ㅏㄴ
(나중엔 ㅈ중간 노드 삭제되는 경우도)
중위후속자가 아닌 자식이 있을때 처리
레드블랙
put할때 루트부터 내려와야
(지금 비교하는 노드만 뺴고 다 가리고 )
자꾸 틀림
블랙 링크,노드로 구성할떄의 차이[ ]
각종 수학식이나 5지선다형[ ]
(모두고르시오 대충 2개인가
확률 부분
코드 나온다면
relink
rotate
bst삭제부분
레드블랙트리 문제풀기
2-3
레드블랙
삭제
루트부터라는거야
리프부터라는거야[ p ]
연결리스트
이진배열
bst는 안나오려나 [ ]
왜 정답이 '최적 이진 탐색 트리(OBST)'인가?
이 문제의 핵심은 **"나머지 트리들은 균형을 '목표'로 하지만, OBST는 아니다"**라는 점에 있습니다.
- OBST의 목적: 트리의 높이를 맞추는 것이 아니라, **'자주 찾는 데이터를 위로 올리는 것'**이 목적입니다.
레드 블랙트리는 블랙의 갯수만 똑같은거지 최악의 경우 높이는 많이 차이날수있는거 아닌가
그래도 두배까지 차이나는거지 1, 999차이는 안나서 ?ㅇㅇ
- 최악의 경우: 가장 짧은 경로(전부 블랙)와 가장 긴 경로(레드-블랙 교대)의 차이가 최대 2배까지만 날 수 있도록 제한합니다.
- 레드블랙
힙은 **'완전 이진 트리(Complete Binary Tree)'**의 일종입니다.
- 구조적 특징: 위에서 아래로, 왼쪽에서 오른쪽으로 차곡차곡 노드를 채워 나가는 방식입니다.
- 깊이 차이: 마지막 레벨을 제외하고는 모든 노드가 꽉 차 있어야 하므로, 왼쪽 서브트리와 오른쪽 서브트리의 깊이 차이는 최대 1을 넘지 않습니다. 따라서 매우 균형 잡힌 트리입니다.
우선순위 큐를 구현할 때 쓰는 트리인데
(아 부모는 i/2가 만족해야하니깐,
Optimal Binary Search Tree (최적 이진 탐색 트리): 각 키의 액세스 빈도(확률)에 따라 탐색 비용을 최소화하도록 구성됩니다. 만약 특정 키의 빈도가 매우 높고 나머지 키들은 매우 낮다면, 트리는 한쪽으로 길게 치우친 형태(편향 트리)가 될 수 있습니다. 이 경우 왼쪽과 오른쪽 서브트리의 깊이 차이는 노드 수 n
에 비례하여 매우 커질 수 있습니다.
키 값 입력 순서: 1 → 2 → 3 → 4 → 5 → 6 → 7<<<이거 어떻게 해야하지,
이거 4입력되면 234 처리하고 나면 1,2가 red red가 되는데
무조건 회전하는게 아니라 삼촌이 red이면
둘다 블랙으로 만들고
부모를 red로 바꿈
삼촌(블랙) 부모(레드)
일때 부모밑에 레드 들어올때
아 그냥 삼촌 생각하지말고
b -r -r경우인거랑 같네 복잡한 회전 생각할필요없이
레드블랙트리에서
삼촌 부모 둘다 red일때
블랙으로 바꿔줄때
할아버지, 증조할아버지 red-red인지 확인
이진 검색 트리(BST)**를 인덱스로 사용할 때 발생하는 2가지 주요 문제점
편향트리(에서 멈추면 안되고)> 이러면 nlogn이 아니라 n이됨
일단왜 4노드이면 2h라더라
블랙이 두개의 레드 자식을 가지니깐, 근데, 아 3노드여도 레드자식 안가지는곳도 있긴하지만, 가지는 곳도 있고 최대높이는 2h이고 최소는 h가 되는곳도 있나, 모두 3노드인걸 레드블랙으로 바꾸면
2-3-4
위치 탐색: "어디로 들어갈까?" 루트에서 리프
새로운 데이터를 삽입하려면 가장 먼저 **"이 데이터가 들어갈 자리가 어디인가?"**를 찾아야 합니다.
- 트리의 구조상 가장 큰 값과 작은 값의 기준이 되는 **루트(Root)**부터 시작해서, 키 값을 비교하며 아래로 내려가야만 적절한 리프(Leaf) 노드에 도달할 수 있습니다.
① 2-노드는 두 개의 키 값을 갖는다. (틀림)
이유: 2-노드는 1개의 키와 2개의 자식 링크를 갖는 노드를 말합니다. (참고: 3-노드는 2개의 키와 3개의 자식, 4-노드는 3개의 키와 4개의 자식을 가집니다.)
키의갯수랑 노드의 갯수 다른가 ㅇㅇ
2-3-4 트리에서
노드(Node)와 키(Key)의 개수를 계산하는 법
은 "각 노드가 가질 수 있는 자식의 수"를 기하급수적으로 더해보면 쉽게 이해할 수 있습니다.
계산을 위해 트리의 높이(Level)를 h라고 가정하겠습니다. (루트만 있을 때 h=1)
- 노드 수와 키 수의 기초 정의
2-노드: 키 1개, 자식 2개
3-노드: 키 2개, 자식 3개
4-노드: 키 3개, 자식 4개 - 최대 개수 계산 (모든 노드가 '4-노드'일 때)
가장 빽빽하게 찼을 때를 생각하면 됩니다. 자식이 매 레벨마다 4배씩 늘어납니다.
레벨 1 (루트): 노드 1개 (키 3개)
레벨 2: 노드 4개 (4의 1제곱) (각 노드당 키 3개씩, 총 12개)
레벨 3: 노드 16개 (4의 2제곱) (각 노드당 키 3개씩, 총 48개)
레벨 h: 노드 4의 (h-1)제곱 개
[결과]
총 노드 수: 1 + 4 + 16 + ... + 4의 (h-1)제곱
이것은 등비수열의 합 공식에 의해 (4의 h제곱 - 1) / 3 개가 됩니다.
총 키(Key) 수: 각 노드마다 키가 3개씩 있으므로 (노드 수 곱하기 3)
((4의 h제곱 - 1) / 3) 곱하기 3 = 4의 h제곱 - 1 개
그래서 4번 문제의 4번 보기가 틀린 것입니다. "4의 h제곱 - 1"은 노드의 개수가 아니라 키의 개수이기 때문입니다.
- 최소 개수 계산 (모든 노드가 '2-노드'일 때)
가장 헐겁게 찼을 때입니다. 일반적인 포화 이진 트리와 모양이 같습니다.
레벨 1: 노드 1개 (키 1개)
레벨 2: 노드 2개 (2의 1제곱) (키 2개)
레벨 h: 노드 2의 (h-1)제곱 개
[결과]
총 노드 수: 1 + 2 + 4 + ... + 2의 (h-1)제곱 = 2의 h제곱 - 1 개
총 키(Key) 수: 각 노드마다 키가 1개씩이므로 노드 수와 같습니다. 2의 h제곱 - 1 개
- Red-Black 트리 높이와의 관계 (2번 보기 관련)
2-3-4 트리를 Red-Black 트리로 바꿀 때 높이가 어떻게 변하는지 보면 됩니다.
2-노드 -> 블랙 노드 1개 (높이 변화 1)
4-노드 -> 블랙 노드 1개 + 양옆에 레드 노드 1개씩 (높이 변화 2)
따라서:
2-3-4 트리의 모든 경로가 2-노드로만 되어 있다면? RB 트리의 높이는 그대로 h입니다.
2-3-4 트리의 모든 경로가 4-노드로만 되어 있다면? RB 트리의 높이는 2h가 됩니다. (블랙-레드 층이 반복되므로)
결론: RB 트리의 높이는 항상 2h인 것이 아니라, h 이상 2h 이하 범위 안에 있게 됩니다. 그래서 "항상 2h다(ㄴㄴ)"라고 말한 2번이 틀린 것입니다.
정리하자면!
구분 / 최소 (모든 노드가 2-노드) / 최대 (모든 노드가 4-노드)
총 노드 수: 2의 h제곱 - 1 / (4의 h제곱 - 1) / 3
총 키(Key) 수: 2의 h제곱 - 1 / 4의 h제곱 - 1
RB 트리 높이: h / 2h
ll인지 lr인지 (자식 높이 같을때 )
ll로
20삭제할떄 어떤곳에서 빌려와야하지 양쪽 다가능한데
[삭제 25] 직후
- 유형: 병합 (Merge)
- 설명: 25가 사라져 빈 노드가 되었습니다. 형제인 15나 35 모두 키가 1개라 빌려줄 수 없습니다. 부모인 20이 내려오고, 왼쪽 형제 15와 병합하여 [15, 20]이 됩니다.
(부모 내려올때, 형제랑 병합하나보다
형제는 거지인데 부모가 부자일때
근데 이거 순서가 있나, 만야게 부모도 부자이고ㅓ 형제도 부자이면ㅇㅇ
- 형제가 부자다? -> 빌려온다 (구조 유지)
- 형제는 가난한데 부모가 부자다? -> 부모 키 내려서 합친다 (구조 유지)
- 둘 다 가난하다? -> 합치고 윗단계에서 다시 해결한다 (트리 높이 감소 가능성)
(3번이 아마 일방적으로 부모가 내려오는것같은데 )
나도 가난, 형제도 가난, 부모도 가난
이제 문제는 [20]이 있던 자리가 비었다는 것입니다. 이 노드 입장에서 다시 주변을 봅니다.
- 형제([60]) 확인: 키가 1개뿐입니다(가난함). 빌려올 수 없습니다.
- 부모(루트 [45]) 확인: 키가 1개뿐입니다(가난함).
- 해결: 루트의 키 45를 내려서 형제 60과 합칩니다.
[ 45 ]
/ \
[ 빈칸 ] [ 60 ] <-- 부모였던 [20] 자리가 비어버림!
| / \
[ 20, 30 ] [ 50, 55 ] [ 70 ]
[ 7 ]
/
[ 2 , 4 ] [ 9 ]
/ | \ /
[1] [3] [5,6] [8] [10]
여기서 8,10,9삭제 각각 과정 상세히 그려줘 설명도
이제 문제는 [20]이 있던 자리가 비었다는 것입니다. 이 노드 입장에서 다시 주변을 봅니다.
내 형제에서 빌려올때
자식도 같이오나본데
(리프노드가 아닐떄
- 숫자가 1개면 다리가 2개 | |
- 숫자가 2개면 다리가 3개 | | |
만약 숫자가 이동해서 다리 개수가 안 맞는다면(예: 숫자는 1개인데 다리가 3개라거나), 그게 바로 자식을 이사시켜야 한다는 신호입니다
[ 10 , 13 ]
/ |
[ 9 ] [ 11 ] [14,15]
이때 9삭제하면 어케 되는지 이해안됨, 그냥 9만 삭제해버리면 안되던가
근데 10빌려오면 부모 2노드인데 자식이 3개가 되는디
2가 삭제되어 왼쪽 자식 자리가 비었습니다. 이 빈 구멍을 메우려면 **그 구멍 바로 옆에 있는 벽(5)**을 건드려야지, 멀리 있는 벽(15)을 건드리면 아무 소용이 없습니다.
[20B]
/ \
(10R) [NIL:B] <-- 삼촌이 Black
\
(15R) <-- 신규 노드(N), 꺽인 모양(LR)- 회전 1 (Case 2 -> Case 3): 10을 기준으로 왼쪽으로 회전하여 직선 형태로 만듭니다.
[20B]
/
(15R)
/
(10R) <-- 이제 직선 모양(LL)
- 분석: 형제(50)도 Black이고, 조카들(40, 60)도 모두 Black입니다. 빌려올 Red가 전혀 없는 상황입니다.
- 형제(50)를 Red로 만들고,
- 최종: 만약 30이 원래 Red였다면 [30B]가 되면서 종료되고,
- 30이 루트였다면 그대로 Black이 되며 종료됩니다.
- 분석: 형제(50)는 Black이고, 나(DB)와 가장 먼 쪽 조카인 60이 Red입니다. 이 Red를 뺏어와서 부족한 Black을 채울 수 있습니다.
- 해결 방법: 부모 기준 왼쪽 회전 + 색상 변경.
- 과정:
- 부모(30)를 기준으로 왼쪽 회전한다.
- 새로운 루트가 된 형제(50)에게 원래 부모의 색(Black)을 준다.
- 원래 부모(30)와 먼 조카(60)를 Black으로 칠한다.
[ ]
Case 1: 형제(S)가 Red일 때
상황: 아래 트리에서 노드 10을 삭제했습니다.
[30B] (P)
/ \
[[DB]] (50R) (S: 형제가 Red)
/ \
[40B] [60B]
"AVL 트리도 아닌데 왜 굳이 회전을 해야 하나?"
색깔만 바꾸면 "검은색 노드의 개수(Black Height)"가 양쪽이 맞지 않기 때문
| Case 1 | S가 Red | P와 S 색 바꾸고 P 기준 회전 | 형제를 Black으로 만들기 |
| Case 2 | S, SL, SR 모두 Black | S를 Red로 만들고 P에게 DB 넘김 | 부모에게 검은색 책임 떠넘기기 |
| Case 3 | S는 Black, 가까운 조카만 Red | S와 SL 색 바꾸고 S 기준 회전 | Case 4 모양으로 만들기 |
| Case 4 | S는 Black, 먼 조카가 Red | P, S, SR 색 조절 후 P 기준 회전 | 검은색 보충 및 완전 해결 |
(30R) <-- 부모 P (Red)
/ \
[[DB]] [50B] (형제 S)
\
(60R) (먼 조카 SR)[해결 과정]
- 색상 변경:
- 형제(50)는 부모의 색인 Red를 가져옵니다.
- 부모(30)와 먼 조카(60)를 Black으로 칠합니다.
- 회전: 부모(30)를 기준으로 왼쪽 회전합니다.
삭제하려는 노드는 검정인데
"빨간색 형제를 검은색 형제로 교체해서, 문제를 풀 수 있는 상태(Case 2, 3, 4)로 만드는 것
먼 조카(60)가 빨간색(Red)이면 가까운 조카(40)가 무슨 색이든 상관없이 무조건 'Case 4'**입니다.
레드-블랙 트리 규칙에서는 **"해결사(먼 조카)가 이미 좋은 위치(먼 쪽)에 있다면, 다른 조카의 색깔은 무시하고 바로 끝내버린다"
아 부모가 red이고 형제도 red일리는 없으니깐
유형에 따라 순서가 바뀌는 게 아니라, 일단 지우고 나서 발생한 "이중 흑색(Double Black)"의 상태에 따라 해결하는 '유형'이 결정되는 것입니다
- 10, 20, 15 세 노드를 크기 순으로 정렬하면 10 < 15 < 20입니다.
- 가운데 값인 15를 부모로 올리고 10과 20을 자식으로 보냅니다. (이 경우 RL 회전)
- 색상 조정: 새로운 부모 15는 원래 부모였던 10의 색(B)을 물려받고, 자식들(10, 20)은 Black으로 칠합니다.
1. Case 1: 형제가 Re인 경우
- 상황: 내 형제(S)가 빨간색입니다.
- 문제: 형제가 빨간색이면 내가 검은색을 빌려오거나 합칠 수가 없습니다. (대화가 안 통하는 상대)
- 해결: 형제를 Black으로 강제로 바꿔놓고 다른 케이스(2, 3, 4)로 넘깁니다.
- 방법:
- 부모(P)와 형제(S)의 색을 바꿉니다.
- 부모(P)를 기준으로 나(D) 쪽으로 회전시킵니다.
- 결과: 나의 형제가 원래 조카였던 '검은색 노드'로 바뀝니다. 이제 다시 상황을 체크합니다.
2. Case 2: 형제는 Black + 조카들도 모두 Black
- 상황: 형제도 검은색이고, 형제의 자식(조카들)도 둘 다 검은색(NIL 포함)입니다.
- 문제: 형제네 집도 가난해서 내가 빌려올 검은색이 없습니다.
- 해결: "우리 둘 다 가난하니, 부모님한테 검은색 하나를 달라고 하자!" (병합)
- 방법:
- 형제(S)를 Red로 바꿉니다.
- 나의 검은색 부족(Double Black) 상태를 **부모(P)**에게 떠넘깁니다.
- 결과: 부모가 이제 Double Black이 되어 위로 올라가며 다시 문제를 해결해야 합니다. (부모가 Red였다면 그냥 Black으로 변하고 종료됩니다.)
3. Case 3: 형제는 Black + 가까운 조카가 Red (먼 조카는 Black)
- 상황: 형제는 검은색인데, 나랑 가까운 쪽 조카가 빨간색입니다.
- 문제: 이 상태로는 한 번에 빌려오기가 안 됩니다. (회전 각도가 안 나옴)
- 해결: 먼 쪽 조카를 Red로 만들기 위해 준비 운동을 합니다.
- 방법:
- 형제(S)와 가까운 조카의 색을 바꿉니다.
- 형제(S)를 기준으로 바깥쪽으로 회전시킵니다.
- 결과: 이제 **Case 4(먼 조카가 Red인 상황)**가 되었습니다.
4. Case 4: 형제는 Black + 먼 조카가 Red
- 상황: 형제는 검은색인데, 나랑 멀리 있는 조카가 빨간색입니다.
- 해결: "형제네 집에 여유가 있구나! 하나 빌려오자." (최종 해결)
- 방법:
- 형제(S)의 색을 부모(P)의 색으로 바꿉니다.
- 부모(P)와 먼 조카를 Black으로 칠합니다.
- 부모(P)를 기준으로 나(D) 쪽으로 회전시킵니다.
- 결과: 부족했던 검은색이 채워지며 상황 종료! (트리 균형 완벽 회복)
💡 한눈에 보는 요약 (내가 왼쪽 자식일 때)
| 케이스 | 상황 | 행동 | 목표 |
| Case 1 | 형제(S)가 Red | 부모/형제 색 바꾸고 회전 | 형제를 Black으로 만들기 |
| Case 2 | 형제/조카 모두 Black | 형제만 Red로 바꿈 | 부모에게 책임 전가 (Merge) |
| Case 3 | 가까운 조카가 Red | 형제/조카 색 바꾸고 회전 | Case 4로 만들기 |
| Case 4 | 먼 조카가 Red | 색 정리하고 부모 회전 | 종료 (해결) |
PDF에서 말한 "3가지 유형"과의 차이:
- PDF는 Case 3와 4를 하나로 합쳐서 "조카가 빨간색이면 빌려온다(회전)"라고 가르치는 것입니다.
- 일반 책은 회전을 한 번 하느냐(Case 4), 두 번 하느냐(Case 3 -> 4)를 구분하기 위해 4가지로 나눈 것입니다. 본질은 똑같습니다!
Case 4 적용 (먼 조카가 Red일 때)
- 부모(20) 기준 왼쪽 회전.
- 부모(20)의 색(Red)을 형제(25)에게 주고, 부모(20)와 먼 조카(30)를 Black으로 만듭니다.
내(DB) 형제가 Red입니다. Red 블랙 트리의 규칙상 형제가 Red이면 부모와 형제의 자식들은 무조건 Black이어야 합니다.
- 목표: 형제를 Black으로 바꿔서 다른 케이스(Case 2, 3, 4)로 넘기기
- 방법: 부모와 형제의 색을 바꾸고, 부모를 기준으로 회전합니다.
(형제의 자식중 어디가 red인지 )
형제가 Black인데, 형제의 자식 중 DB에서 먼 쪽(바깥쪽) 자식이 Red인 경우입니다. (가장 깔끔하게 끝나는 케이스!)
- 목표: 오른쪽의 넘치는 Red를 왼쪽(DB 쪽)으로 보내서 부족한 Black을 채우기
- 방법:
- 형제(50)는 부모(30)의 색을 이어받음.
- 부모(30)와 빨간 자식(60)은 Black으로 칠함.
- 부모(30)를 기준으로 회전.
상황: 형제가 Black인데, 형제의 자식 중 DB와 가까운 쪽(안쪽) 자식만 Red인 경우입니다.
- 목표: 이 상태로는 한 번에 해결이 안 되니, 유형 2(Case 4) 모양으로 만들기
- 방법:
- 형제(50)와 빨간 자식(40)의 색을 바꿈.
- 형제(50)를 기준으로 회전하여 Red가 바깥쪽으로 가게 만듦.
db
형재 블랙일떄
조카 둘다 있을떄
r r
r b
b r
r
r
다양한 케이스
[회전 전] [형제 회전 후 (Case 4가 됨)]
30(?) 30(?)
/ \ / \
DB(10) 50(B) DB(10) 40(B) <-- 새 형제
/ \ \
40(R) 60(B) 50(R) <-- 이제 바깥쪽이 Red!
(색깔 먼저 바꾸고 회전)\
4(B)
/
2(B) 6(B)
/
1(R)
이문제 이해안가, 만약에 자식이 없었더라면,
6을 레드로 만들었어야햇지않앗나
- 주의: 할아버지가 빨간색이 됐는데, 할아버지의 부모가 또 빨간색이면? 이 과정을 위로 올라가면서 반복합니다. (만약 할아버지가 루트라면 다시 검은색으로 바뀝니다.)
- 나(Red), 부모(Red), 삼촌(Black 또는 없음/NIL)해결:
- 회전: 나, 부모, 할아버지 세 노드를 크기 순서대로 정렬해서 중간값을 부모로 만듭니다. (LL, RR, LR, RL 회전)
- 색칠: 새로 부모가 된 노드(중간값)를 검은색으로, 그 밑에 자식이 된 두 노드를 빨간색으로 칠합니다.
- 위로 올라가며 다시 확인할 필요가 없어요.
삼촌 이 빨강이어서
할아버리 빨강으로 만들어도
- 할아버지(20)를 **빨간색(R)**으로 바꿉니다.
- 루트 규칙: 루트 노드는 항상 검은색이어야 하므로, 20은 다시 **검은색(B)**이 됩니다.
중간층(2층) 방을 키우면 안 되나요?
- 만약 2층에 있는 방 하나를 '2인실(3-노드)'로 바꾸면 어떻게 될까요?
- 2-3 트리의 규칙상, 방이 2인실이 되면 자식 방이 3개로 늘어나야 합니다.
- 자식 방이 늘어나면? 바닥 층에 방이 하나 더 생깁니다.
- 그러면 (중간층에 1명 추가) + (바닥층에 방이 생겨서 최소 1명 추가) = 총 2명 이상이 추가되어 버립니다.
- 우리는 딱 1명만 더 필요한데, 중간층을 건드리면 최소 2명이 늘어나서 9명 이상이 되어버립니다. 그래서 중간층은 건드릴 수 없습니다!
왜 회전을 "두 번" 하나요? (LR 케이스 예시)
컴퓨터는 한 번의 rotate로 노드를 딱 한 칸만 위로 올릴 수 있습니다. 그런데 꺽쇠(LR) 모양에서 중간값인 x는 현재 맨 밑(손자)에 있죠? 얘를 대장(루트)으로 만들려면 두 계단을 올라와야 합니다.
rotate(x)의 단 한 가지 목표는 "x를 한 단계 위로 올리는 것"입니다.
1. 왜 회전인가? (시소라고 생각하세요)
트리가 한쪽으로 기울어져 있는 걸 상상해 보세요. z - y - x 순서로 오른쪽으로 길게 늘어져 있습니다.
z (할아버지)
\
y (아버지)
\
x (나) <-- 얘를 위로 올리고 싶어!이걸 rotate(x) 한다는 건, x를 잡고 위로 확 끌어올리는 겁니다. 그러면 y는 밑으로 딸려 내려가겠죠?
근데 이게 avl코드인데 실제로는 젤 중간값이 루트가 되는데 서브트리의,
항사 ㅇx<즉 제일 마지막ㅇ 얘가 중간값인가 왜지, ㄴㄴ
restructure 함수가 rotate(x)를 두 번 실행합니다
restructure 함수가 **rotate(y)**를 실행합니다
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
근데 ll일떄는 왜 첫번째 relink에서 두번쨰 매개변수가 x.right이고
rr일떈 x.left인거지
내가 위로 올라가면, 원래 내 부모였던 y는 내 오른쪽 자식이 되어야 합니다
- 내가 위로 올라가려는데, 내 **오른쪽(x.right)**에 이미 내 자식이 살고 있네?
- 충돌: "어라? 아빠(y)가 내 오른쪽 자리에 앉아야 하는데, 내 보물상자(x.right)가 거기 있네!"
- 해결: "내 보물상자(x.right)를 아빠(y)의 빈 왼쪽 손에 맡기자!"
그래 이제 무슨 자식을 건드려야하는지는 알게슨ㄴ데, 그
래서 y의 오른쪽에 붙이는지 왼쪽에 붙이는지
내가 위로 올라가면서 부모의 손을 놓았기 때문에, 그 손(y.left 또는 y.right)이 비어 있기 때문입니다. 그 비어 있는 손으로 내 짐을 낚아채는 것이죠.
- 첫 번째 relink(y, x.right, true): x의 오른쪽 서브트리(안쪽 서브트리)를 떼어서 y의 왼쪽 자식으로 붙여주는 작업입니다. 회전 후에도 이진 탐색 트리의 성질을 유지하기 위해 꼭 필요한 이동입니다.
- 두 번째 relink(x, y, false): 원래 부모였던 y를 이제 x의 오른쪽 자식으로 만드는 작업입니다. 이 작업이 핵심적인 "회전" 동작입니다.
relink(x, y, false)**를 먼저 실행: "y를 x의 오른쪽 자식으로 만들어라."
- 여기서 문제가 발생합니다. 원래 x.right에 있던 T2 정보가 지워지고, 그 자리에 y가 들어갑니다. (x.right = y)
- 이제 T2라는 자식 노드는 트리 어디에서도 찾을 수 없는 '미아' 상태가 됩니다.
근데 왜 true,false인거지 순서가
그리고 이게 왜 ll,rr,rl,lr이던 상관없는거지
일단 z,x
y,x의 자식
x,y
rotate 함수가 단순히 '회전' 하나만 하는 게 아니라, '자식(x)을 부모 자리로 끌어올리는 범용적인 기능'**을 하기 때문입니다
이 코드에서 rotate(x)는 **"x가 부모의 왼쪽이든 오른쪽이든 상관없이, x를 현재 부모의 위치로 한 단계 격상시킨다"**는 뜻입니다.
- x가 왼쪽 자식이면 (LL 방향): 우회전(Right Rotation)을 해서 x를 올립니다.
- x가 오른쪽 자식이면 (RR 방향): 좌회전(Left Rotation)을 해서 x를 올립니다.
즉, rotate 함수 하나가 방향에 맞춰서 알아서 작동하도록 설계되어 있습니다.
if(x==y.left){
relink(y,x.right,);
}
else{
relink(x,y,);
}이거 세번째 매개변수 어떻게 해줘야하는지 모르겟어
(아 relink 두번해야하는구나
(rotate두번하는거랑 상관없이 )
이진 탐색 트리(BST)의 크기 순서"**를 지키는 것입니다
ll기준, y보단 x가 작은거니깐, x으 ㅣ자식들, y보단 작으니깐
왼쪽이 맞는거고
'26년1학기 > 알고리즘' 카테고리의 다른 글
| 알고리즘) 해싱 (26.4.6) (1) | 2026.04.06 |
|---|---|
| 알고리즘)2주차 퀴즈 준비(2) (0) | 2026.04.05 |
| 알고리즘) 2-3-4 &red black tree (0) | 2026.04.01 |
| 알고리즘) AVL Tree & 2-3 Tree (0) | 2026.03.30 |
| 알고리즘) 복습(26.3.26) (0) | 2026.03.26 |