알고리즘)2주차 퀴즈 준비(2)

'
트리, 여러번 그려봐야겠는데
시험칠때
검산

🍇pdf2h장에 잇는 문제들
 
(avl 재구성 할필요없는데 재구성 하는 경우도 있3
 
리프노드가 아닌 블랙이 삭제되면 어케 하지,
 

---

if(!key.equals(x.key)){

x는 노드임 (자료형) 
 
 
x == p.left< 분기점 else에도 동일 
 
rebalanceDelete(p, x);
 
 
 

relink(z,y.right,z.left==y);

y는 x의 중위후속자이니깐, 
y.leaft는 없
 
 
 
 
다름

이미지의 코드: (x == y.left) == (y == z.left)

이 코드는 두 조건의 결과값(true/false)이 같은지를 비교합니다.

작성하신 코드: (y.left == x && z.left == y)

이 코드는 논리곱(AND)으로, 두 조건이 모두 true일 때만 통과됩니다.
 
 
 
 
의 트리에서 5가 삭제되고 난 후의 레드-블랙 트리<<이거 어케함,
근데 이거 회전시킬때,
9자식(자식 둘다 있을때, 회전시킬대)_중 8,11중 11이 크기때문에, 즉, 일직선 상에 있는게 후보로 되어야하나,ㅇㅇ
후보 3명 고를떄,
 오른쪽 회전이엇다면 ll에 위치한 녀석이 후보가 되나ㅇㅇ
 
 
그리고 색바꾸고 회전시킨다음에는 뭘해야하지
형제가 블랙인 경우 적용시키기
 
 
 
그리고 색깔은 어떻게 바꾸는가,
 이건 공식보다는 원래 그 
일직선 회전시킬때 중간게 서브트리의 루트가 되고 검은색 되고, 두개는 red되는것처럼, ㄴㄴ
9는 블랙, 7,11은 red되나 ㄴㄴ
11은 black그대로임 ㄷㄷ
 
형제(9)가 Red일 때 하는 회전과 색 변환은
**"원래 부모(7)와 원래 형제(9)의 색만 맞바꾸는 것"
 
 
 
엥 11은 블랙 그대로네 
< 그냥 ll,rr회전이랑 다름 
 
 
 
 

[대원칙] 삭제 상황 파악

• 삭제 노드가 Red면? → 그냥 지우고 끝 (균형 안 깨짐).
• 삭제 노드가 Black이면? → 그 자리에 이중 흑색(DB) 발생. 이제 형제의 상태를 봅니다.

---

유형 1. 형제(s)가 Red인 경우 (변환 단계)

질문하셨던 문제의 첫 단계가 이 경우였습니다.

• 상황: 내 형제가 빨간색이다.
• 해법: 부모와 형제의 색을 바꾸고, 부모를 축으로 회전합니다.
• 결과: DB는 그대로지만, 내 형제가 Black인 상태로 구조가 바뀝니다. (이제 아래 유형 2, 3, 4 중 하나로 넘어갑니다.)

---

유형 2. 형제(s)가 Black이고, 형제의 자식들이 모두 Black인 경우 (수혈 단계)

• 상황: 형제도 검은색인데, 조카들도 다 검은색이라 빌려올 빨간색이 없다.
• 해법:
  1. 형제를 Red로 바꿉니다. (형제에게서 검은색 한 개를 뺏음)
  2. 뺏은 검은색을 부모에게 줍니다.
• 결과:
  • 부모가 원래 Red였다면? → Black이 되면서 상황 종료! (가장 깔끔)
  • 부모가 원래 Black이었다면? → 부모가 새로운 DB가 되어 위로 올라가며 반복합니다.

---

유형 3. 형제(s)가 Black이고, 가까운 조카가 Red인 경우 (준비 단계)

• 상황: 형제는 Black인데, 나랑 가까운 쪽 조카만 빨간색이다. (꺾인 모양, RL 또는 LR)
• 해법: 형제와 그 조카의 색을 바꾸고 회전해서 **"일직선 모양(유형 4)"**으로 만듭니다.
• 결과: 유형 4로 넘어갑니다.

---

유형 4. 형제(s)가 Black이고, 먼 조카가 Red인 경우 (종결 단계)

• 상황: 형제가 Black이고, 나랑 멀리 있는 조카가 빨간색이다. (일직선 모양, LL 또는 RR)
• 해법:
  1. 부모와 형제의 색을 맞바꿉니다.
  2. 부모를 축으로 회전합니다.
  3. 먼 조카(빨간색이었던 놈)를 Black으로 바꿉니다.

 

• 올라가는 **형제(S)**는 원래 부모(P)의 색을 그대로 가져갑니다.(1)
• 내려가는 **부모(P)**는 Black이 됩니다.
• 빨간색이었던 **먼 조카(D)**는 Black이 됩니다. (이게 핵심! 여기서 검은색 노드가 하나 더 생겨서 DB를 메꿔줍니다.)

 

---

💡 아주 쉽게 외우는 팁 (시험용)

1. 형제가 Red면? → 일단 회전하고 색 바꿔서 형제를 Black으로 만들어라. ("형제 블랙 만들기")
2. 형제 자식들이 다 Black이면? → 형제 빨간색으로 만들고 부모한테 블랙 떠넘겨라. ("부모에게 토스")
3. 형제 자식 중에 Red가 하나라도 있으면? → 회전하고 색깔 예쁘게 맞춰서 끝내라. ("조카 빨간색 뺏어오기")

 
 
 
(회전시킬수있기때문에 일직선에 있는 (먼조카를 먼저 보는건가 ) ㅇㅇ
 
 
 
 
 
근데 중위후속자가 없는, 리프노드가 아닌 블랙이 삭제되면 어케 하지,
 
 
 
 
 
 
30 (Black)
/
20 (Black) 40 (Black)

50 (Black)
근데 원래는 이렇게 바꾸는 과정에서 db에게 형제가 생겨서 뭐 어떻게 햇는데, 지금처러
ㅁ형제가 안생기면 어케 해야하지
내가 궁금한건 이게 잘된건지,,
아 블랙의 갯수 세아려보면 되나, 아니면 다른 방법도 있나 
 
 
 
 

35(B)
        /      \
     20(R)     50(R)
    /    \     /    \
  10(B) 30(B) 40(B) 80(B)

 

1. 20의 자리에 후계자인 30의 값을 복사합니다. (색상은 원래 20의 색인 Red 유지)

상황	삭제 대상 노드 색	중위 후속자 노드 색	실제 물리적 삭제 색	결과
Case 1	Red (20)	Black (30)	Black	Double Black 발생! (재조정 필요)
Case 2	Black (20)	Red (30)	Red	그냥 삭제 끝! (매우 쉬움)

 

30(B)
       /     \
    10(B)    50(B)
            /    \
          40(R)  60(R)

 
50
 
 
 
 
 
항상 이진트리여야하나 ?
avl에서 최소노드갯수 
2**(h-1)아님

• 왼쪽 자식은 높이가 3인 트리 중 가장 마른 녀석을 붙입니다.
• 오른쪽 자식은 굳이 높이 3일 필요 없습니다. 규칙상 2만 되어도 전체 높이는 4가 됩니다. (차이가 1이니까요!)

 
 
N(h−1)+N(h−2)+1
왜 이런 피보나치 수열 같은 형태인거지
 
 
 
 
 
이거 입력되는 순서가 정해진건가,ㅡ
나는 7자리인데, 일단 4가 먼저 입력되어야하고, 2보다는 13이 나중에 6보다는 57이 나중에 뭔가 이거 확률에서 중복 조합ㅈ 냄새나는데,
ㄷㄷ