지금 시간은 3시 3분..자그마치 6명의 집단 지성이 힘을 합쳐 겨우 디버깅을 완료하고 모든 테스트 케이스 통과!! 삭제 기능에 대해 빠르게 로직 정리하고 집 가야겠다..
삭제(Deletion)
옮기거나 삭제하는 노드의 원래 색을 기억해뒀다가 옮기거나 지우려는 노드 색이 검정인 경우에만(=이중 흑색 노드) 트리를 고친다.
- 지우려는 노드 z 혹은 옮기려는 노드가 빨간색이면 rb트리 특성을 위반하지 않으니 고칠 필요가 없다.
- 지우려나 옮기려는 노드가 검정일 때는 경로 상의 검정 노드 개수가 변하므로 트리 특성을 위반한다. 이 경우에는 fixup 함수로 수정한다.
삭제 기능은 세 가지 케이스로 나눠서 구현한다.
1. 삭제하려는 노드(=z)의 왼쪽 자식만 있는 경우 (=오른쪽 자식이 NIL인 경우)
이때는 왼쪽 자식(y)를 z자리로 옮긴다. 일단 이렇게 하고 패스.
2. z의 오른쪽 자식만 있는 경우(=왼쪽 자식이 NIL인 경우)
여기서는 오른쪽 자식(y)를 z자리로 옮긴다. 역시 여기서도 패스. 색 고려는 밑에 가서 할 예정.
3. 삭제하려는 노드의 양쪽에 다 자식이 있는 경우 (양쪽에 NIL이 없음)
- z의 직후 노드인 y를 찾는다. (직후 노드: z 바로 다음에 오는 노드. 예를 들어 노드 번호가 15, 16, 17이고 z = 15이면 직후 노드는 16.)
- y의 색을 따로 저장해둔다.
- y의 오른쪽 자식 노드를 x로 지정한다.
여기서 2가지 케이스가 발생하는데,
1) y의 부모가 z일 때: 이때는 x의 parent로 y를 지정한다. 엥? 이미 부모가 아닌가? 하지만 x가 NIL일 경우 NIL의 부모는 설정되지 않기 때문에 이렇게 따로 지정해줘야 한다.
2) y의 부모가 z가 아닐 때: 이때는 y와 y->right를 바꾸고 / y->right = z->right (x를 z 오른쪽에 연결) / z와 y를 바꾼다.
여기까지 끝나면 색을 고쳐야 하는 상황이 발생한다. 삭제 기능은 삭제하려는 노드의 색이 빨간색인지 검정색인지에 따라 나누어서 처리한다. delete(T, z)에서 지우려는 노드 z에는 z를 대체해 z자리에 오는 노드에 검은색을 칠한다. 만약 그 노드가 빨간색이면 검정색이 되고, 검정색이면 검정색을 칠하니 이중흑색 노드가 된다. 이때는 아래에 소개할 2번에 해당하며, fixup을 실행해야 한다.
1) 삭제하려는 노드가 빨간색일 경우: 아무 문제 없이 그냥 삭제하면 끝. 이는 black 경로 함수 hb의 값에 변동이 생기지 않기 때문.
2) 삭제하려는 노드가 검정색일 경우: 이때는 아래에 소개할 fixup을 실행해야 한다.
여기서부터 8가지 경우로 나눠서 생각하는데, 4가지씩 대칭이므로 왼쪽 케이스(이중 흑색 노드가 부모의 왼쪽 자식인 경우)만 여기서 소개한다.
Case A: 이중흑색 노드 X의 형제가 빨강색인 경우
=> 형제를 검은색, 부모를 빨간색으로 칠한 뒤 부모 노드를 기준으로 좌회전한다.
이 때를 기준으로 케이스를 세 가지 나눠서 처리한다.
Case B: 이중 흑색 노드 형제가 검은색이고 형제 양쪽 자식이 모두 black인 경우
=> 형제 노드만 red로 만들고 이중 흑색 노드의 B 하나를 부모로 전달한다.
Case C: 이중 흑색 노드의 형제가 black이고 형제의 왼쪽 자식이 red, 오른쪽 자식이 black인 경우
=> 형제 노드를 red로, 형제 왼쪽 자식(=red)을 black으로 칠한 후에 형제 노드를 기준으로 우회전한다.
Case D: 이중 흑색 노드의 형제가 black이고 형제의 오른쪽 자식이 red인 경우
=> 부모 노드의 색을 형제에게 넘긴다. 부모 노드와 형제 노드의 오른쪽 자식을 검은색으로 칠한다. 이후 부모 노드를 기준으로 좌회전한다.
이미지는 주말에 시간이 난다면...(이미 4시다...)
'정글사관학교 개발일지 > RB트리' 카테고리의 다른 글
| 정글사관학교 36일차 TIL: Red-Black Tree(RB트리) 삽입 구현 (0) | 2021.12.08 |
|---|