오늘의 목표는 코어타임 이전에 RB 트리의 삽입 이론을 노션에 정리하고 코드를 구현하는 것입니다. 가능하다면 EC2까지 구축하려고 합니다.
9:50 ~ 12:00
RB-Tree 삽입 과정에 대해 정리해보고, 코드를 구현해 보겠다.
삽입 과정에 대해 정리 중이다.
12:00 ~ 13:00
식사 진행 및 휴식
13:10 ~14:45
잤다. 이게 일주일치 잠이 누적되서 그런지 너무 졸렸다. 이대로 공부하는 것이 효율성이 더 떨어진다고 생각했다.
14:45 ~ 16:20
삽입을 마저 끝내고 있다. 완벽한 이론을 노션 정리는 완료 했다. 이제 삽입 코드 구현을 해보겠다.
16:20 ~ 18:00
RB Tree의 새 트리 만드는 코드와 삽입 코드를 구현중이다.
18:00 ~ 19:00
식사를 하고 시놀로지 도커작업을 시작하였다. 아직 못끝냈다.
19:00 ~
시놀로지 세팅을 하다가 RB 트리 삽입을 마저 구축하겠다.
22:00 ~ 01:00(팀원 코어 타임)
RB 트리 삽입 복습하고 바로 삭제에 대해서 공부했다.
삭제
삭제시, 노드의 색이 red면 그냥 리턴.
만약, balck을 삭제하면 위반을 한다. 5번 규칙인 black depth의 수가 달라진다.
[자식노드가 0인 블랙노드를 삭제해보자]
삭제 한 곳에 NIL더블 블랙 노드를 삽입한다.(임시로)
그러면 이걸 해결하기 위해 삭제된 오른쪽에도 더블 블랙이 나오면 된다. (본인의 형제를 더블 블랙으로)
그 후 부모가 빨강이면 된다.
그럼 여기서 두가지 케이스가 있다.
형제가 red라면?(아웃터 케이스)
형제를 블랙으로 바꾸고 본다. 그러고 상황에 따라 rotation을 수행한다. 그런 다음 형제를 블랙으로 바꾼다.
형제가 black이라면?
바깥쪽 자식이 레드여야한다.
어떤 케이스든 아웃터 케이스를 만들면된다.
자식이 더블 블랙이면서, 안쪽이 레드이면
형제가 블랙이고 안쪽이 레드이면?
형제중에 삭제하면 더블 블랙되고, 이상태에서 회전을 하고 outer case로 만들고 해결
형제 자식이 레드면?
최종적으로 두가지 케이스인데
outer case로 만들고 해결 아니면 루트를 더블 블랙으로 만들고 해결
중간에 있는 블랙 노드를 바꾸면?
걔의 부모와 자식을 서로 잇고 자신의 블랙을 자식에게 줘서 더블 블랙을 주고 해결해 나간다.
중간의 블랙인 케이스일 때, 자식이 두 개일때 후임자 리프 노드와 스위칭하고 삭제
부모가 빨강이 블랙으로 바뀔러면, 부모의 양 자식이 더블 블랙이어야한다.
팀원간 코어 타임 후 삭제 과정 한번더 들었다.
삭제와 관련된 내용은 노션에 정리가 완료되는 대로 올리겠다.(꽤 많은 시간이 필요할 것으로 예상한다)
01:00 ~ 03:30
토크 시간 및 산책
03:30 ~ 04:30
운동 및 샤워
결론적으로 삽입 구현과 삭제 이론 완벽 정리는 못했습니다. 내일은 일요일이니 마저 진행해보겠습니다.
오늘 비와서 사진을 찍어봤습니다.
