모기.. 때문에 또 잠을 설침..
1시간 정도 더 자고 옴.
08:45 입실
오늘은 RB Tree 삭제 구현하고, 확실하게 원리 이해하기!
작성한 코드 리팩토링하기
RB tree 삭제 과정 정리
우선 RB Tree 색상 조정은 고려하지 않음. BST 삭제 과정을 명확히 설명하고 감.
용어 정리
삭제할 노드 z
Z를 대체할 후계자 y
y의 자식 x
- 삭제할 노드에 양쪽 자식이 없으면 그냥 삭제(조건문 처리 필요 없음, 마지막에 free(z)로 삭제됨)
- 삭제할 노드에 왼쪽 자식이 nil이면 삭제할 노드를 오른쪽 자식으로 대체
(이 시점에서 자식이 모두 없는 경우 1도 해당되지만 변화된 것은 없음) - 삭제할 노드에 오른쪽 자식이 없으면 삭제할 노드를 왼쪽 자식으로 대체
(여기서부터 이해에 오래 걸림) - 만약 후계자에게 오른쪽 자식이 있다면(왼쪽 자식은 있을 수가 없음. 후계자가 제일 작은 값이니까)
후계자가 z의 자리로 올라갈 때, 자신의 빈 자리를 자신의 오른쪽 자녀에게 물려주고 가야함.
그래서 우선 y의 자리로 y의 오른쪽 자식을 데리고와서, 기존 y의 관계를 y의 오른쪽 자식에게 물려줌.
이 작업이 끝나면 y가 z로 떠나도 문제가 없음. - y가 z로 이동하면, z는 기존의 자신의 관계를 y에게 물려줌.
- y가 모든 관계를 물려받으면(색상을 포함한), 메모리 해제를 통해 z를 삭제 시켜줌.
이것도 이해하는데 오전 내내 걸렸는데, 이제 완전히 이해함!!! 🎉
(근데 C로 바로 코드는 못 짬 ㅠ GPT없이 짜야되는데..)
끈임 없는 디버깅
삭제까지 구현했는데 테스트에 실패한다.
문제 가능성
1. 삽입
2. 삭제
3. 최소, 최대
테스트 코드를 추적해 본 결과, 삭제 코드에서 삭제가 되지 않는 문제 확인.
그러니까 당연히 최소, 최대도 테스트에 통과하지 못한다.
(삭제 후에 최솟값이 삭제 전 최솟값으로 그대로니까.)
이제 코드 고치러 간다..
청천벽력같은 소식..
기존의 인서트 함수가 잘못 되었다..
다 갈아엎고 처음부터 다시 짬..
이번에는 GPT 안보고 블로그에 정리한 로직만 보고 제로부터 C로 짜본다.
이러면서 점점 C 익숙해지는 거 느껴짐..
파이썬이 얼마나 편한 언어인지.. 유레카다..
그래도 C가 나왔을 때는 어셈블리에 비하면 유레카였겠지..?
케이스 4 다시 구렁텅이로..
마지막 적색으로 바꾸면서 더블블랙이 해소되는 상황을 다시 이해 못함.
스터디 90분 동안했는데 거의 다 왔는데, 하아..
케이스 4는 이정도에서 타협
케이스 1, 2, 3은 별도의 증명 없이 바로 더블블랙을 삭제했는데,
케이스 4는 기존의 케이스 1, 2, 3과 같은 방식으로는 설명이 어렵고,
별도의 증명 과정을 거쳐서 해결함.
C
헤더 파일의 역할을 알았다!!
헤더 파일은 일종의 추상 클래스가 하는 역할을 하는 거였음!
c에서 함수의 반환값이나 매개변수를 바꾸고 컴파일 하는데,
자꾸 헤더 파일에 뭐랑 안 맞다는 에러가 나옴.
가만 보니까 헤더 파일에 어떤 함수가 이미 형식이 지정되어 있다면
c에서는 헤더 파일의 형식에 맞춰서 함수를 선언, 사용해야 하는 거였음.
이건 일종의 추상 클래스의 역할과 비슷하다고 볼 수 있음!
그래서 컴파일 시 전처리기로 이런 헤더 파일하고 잘 맞춰서 문법적으로 코드가 이상 없는지 체크하고,
헤더 파일에서 구현되야 하는 실제 기능은 링킹 단계에서 라이브러리와 연결하는 거였음!
