한국외대 '신찬수' 교수님과 '쉬운 코드'님의 강의 자료를 참고하였습니다.
개념을 공부하고, 시뮬레이터를 활용하여 노드의 동작 원리를 이해한다.
하단의 링크는 rbtree visualization을 확인할 수 있는 링크이다. 참고하여 학습을 진행한다.
https://www.cs.usfca.edu/~galles/visualization/RedBlack.html
Red/Black Tree Visualization
www.cs.usfca.edu
#1 레드 블랙 트리 삭제 방식
0. 삭제 전 RB 트리 속성 만족한 상태
1. 삭제 방식은 일반적인 BST와 동일
2. 삭제 후 RB 트리 속성 위반 여부 확인 - 어떻게 확인할 수 있는가
3. RB트리 속성을 위반했다면 재조정
4. RB 트리 속성을 다시 만족
RB트리에서 노드를 삭제할 때 어떤 색이 삭제되는지가 속성 위반 여부를 확인할 때 매우 중요하다.
1. 삭제하려는 노드의 *자녀가 없거나 하나인 경우
삭제되는 색 = 삭제되는 노드의 색
*유효한 값을 가지는 자녀를 의미
nil 노드는 자녀로 포함하지 않는다는 의미
25 삭제 > red 삭제
80 삭제 > black 삭제
40 삭제 > black 삭제
2. 삭제하려는 노드의 *자녀가 둘인 경우.
삭제되는 색 = 삭제되는 노드의 **successor의 색 or 삭제되는 노드의 ***predecessor의 색
*유효한 값을 가지는 자녀를 의미
**successor : 해당 노드보다 값이 큰 노드들 중에서 가장 값이 작은 노드 (후임자)
***predecessor :해당 노드보다 값이 작은 노드들 중에서 가장 값이 큰 노드 (선임자)
20 삭제 > successor 25 > red 삭제
35 삭제 > successor 37 > red 삭제
50 삭제 > successor 80 > black 삭제
두 번째에 경우에는 해당 노드가 삭제되고 successor가 대체한다. 해당 노드의 색깔을 유지하고 succesor의 색은 잃는다.
1. 속성 위반 여부 확인
1. 삭제되는 색이 red라면 어떠한 속성도 위반하지 않는다.
2. 삭제되는 색이 black이라면 #2, #4, #5 속성을 위반할 수 있다.
2. 위반 해결하기
1. 삭제되는 색이 black일 때 #2 위반 해결하기.
- 루트노드를 black으로 바꾸면 된다.
2. 삭제되는 색이 black일 때 특수한 상황을 제외하면 #5 속성을 항상 위반하게 된다.
RBtree 삭제 동작의 핵심이 된다.
- #5 속성을 다시 만족시키기 위해 삭제된 색의 위치를 대체한 노드에 extra black을 부여한다.
- 경로에서 black 수를 카운트할 때 extra black은 하나의 black으로 카운트된다.
del(10)
노드 10의 위치를 대체한 nil 노드에 extra black 부여 > #5 속성 만족
black노드인 nil노드에 extra black을 부여한 경우 doubly black이라고 부른다.
del(30)
노드 30의 위치를 대체하는 red노드인 25에 extra black 부여 > #5 속성 만족
red노드에 extra black을 부여한 경우 red-and-black이라고 부른다.
red-and-black 해결하기
red-and-black을 black으로 바꾸면 해결된다.
doubly black 해결하기
총 4가지의 case로 분류된다.
네 가지의 case로 분류할 때의 기준 : doubly black의 형제의 색과 그 형제의 자녀들의 색
#2 doubly black 해결하기
1. doubly black의 오른쪽 *형제가 black + 그 형제의 오른쪽 *자녀가 red일 때 case.4
- 오른쪽* 형제는 부모의 색
- 오른쪽* 형제의 오른쪽* 자녀는 black
- 부모는 black
- 부모를 기준으로 왼쪽*으로 회전하며 해결
*오른쪽을 왼쪽으로 바꿔도 성립
다음은 '쉬운 코딩'님의 레드 블랙트리(2부) 영상에 나오는 그림이다.
우측 하단의 경우는 case.4에서 형제 트리의 black을 자녀들에게 계승시킨 이후 과정에 해당한다.
파란색 노드는 red or black이다.
왼쪽으로 회전을 하게 되며 상단의 그림이 되는 것이다.
이후 과정에서는 A와 C에 있는 extra black을 B에 올려서 B를 black으로 만들어 주며 모든 과정이 끝나게 된다.
예제
del(80)
형제의 자녀(37) red의 색깔과 부모(50)의 색깔을 black으로 바꾼다.
부모(50)를 기준으로 오른쪽으로 회전.
2. doubly black의 오른쪽 형제가 black + 그 형제의 왼쪽 자녀가 red + 그 형제의 오른쪽 자녀가 black case.3
- doubly black의 형제가 오른쪽 자녀가 red가 되게 만든다
- 이후 case.4를 적용하여 해결
예제
del(10)
3. doubly black의 형제가 black + 형제의 두 자녀 모두 black case.2
- doubly black과 그 형제의 black을 모아서 부모에게 전달.
- 부모가 extra black을 해결하도록 위임.
4. doubly black의 형제가 red case.1
boubly black의 오른쪽* 형제가 red일 때
- 부모와 형제의 색을 바꾼다.
- 부모를 기준으로 왼쪽*으로 회전한 뒤
- double black을 기준으로 case 2, 3, 4 중에 하나로 해결
#3 black 삭제 시 #5 속성 위반 해결 요약
삭제되는 색이 black일 때
삭제되는 색이 있던 위치를 대체한 노드에
extra black을 부여한다.
대체한 노드가 red-and-black이 됐다면
black으로 바꿔주면 긑
대체한 노드가 doubly black이 됐다면
case 1, 2, 3, 4 중에 하나로 해결
#4 Red-Black 트리 삭제 예
위의 예제가 중구난방으로 구성돼서 보기 힘드라.
하나의 예제 과정으로 Red-Black트리 삭제 과정을 학습하자.
delete(15)
삭제되는 노드는 15
삭제되는 색은 15의 black,
15의 위치를 대체할 nil node에
extra black을 부여한다.
어떤 case에 속할까?
왼쪽 형제 : black
왼쪽 형제의 왼쪽 자녀 : red
case.4
delete(33)
삭제되는 노드는 33,
삭제되는 색은 33의 black,
33의 위치를 대체할 nil node에
extra black을 부여한다.
어떤 case일까?
왼쪽 형제 : black
왼쪽 형제의 왼쪽 자녀 : black
왼쪽 형제의 오른쪽 자녀 : red
case.3
delete(37)
삭제되는 노드는 37
삭제되는 색은 37의 red
red가 삭제되므로 37 삭제 후 상황 종료
delete(35)
삭제되는 노드는 30 (predecessor 삭제로 진행)
삭제되는 색은 30의 black
30을 대체할 nil node에 extra black 부여
어떤 case일까?
왼쪽 형제 : black
왼쪽 형제의 왼쪽 자녀 : black
왼쪽 형제의 오른쪽 자녀 : black
case.2
nil node의 extra black과 25의 black을 27로 올린다.
25는 red가 되고 27은 black이 된다.
delete(40)
delete(45)
삭제된 노드는 45
삭제된 노드의 색깔은 45의 black
45의 위치를 대체할 nil node에
extra black 부여
어떤 case일까?
오른쪽 형제 : black
오른쪽 형제의 두 자녀 : black
case.2
nil 노드의 extra black과
80의 black을 모아서 50으로 올리고
80은 red로 바꿔준다.
50은 extra black을 가지게 된다.
어떤 case일까?
왼쪽 형제 : black
왼쪽 형제의 왼쪽 자녀 : red
case.4
글을 마치며,
RB Tree 삭제를 공부하다 보니, 직전에 배운 삽입 과정에 대한 기억이 휘발된 것 같다.
심심할 때 들어와 복습하고, 추가적으로 정리할 글이 있다면 수정하도록 해야겠다.
학습 과정에서 완벽히 이해를 하지 못한 부분도 있다.
그러나, RB Tree의 기본 개념인 5가지의 속성을 지키기 위해 작동한다는 것이 해당 알고리즘을 이해하는데 많은 도움이 됐다.
하나 어려웠던 부분은 대부분의 문서나 영상에서 delete를 할 때 자녀 노드가 둘이면 후임자(successor)를 활용한다.
하지만 선임자(predecessor)를 활용해도 된다.
이 사실을 몰라 시뮬레이션과 강의의 차이에서 생기는 차이점에 헤매기도 했다.
앞으로 C언어에 대한 개념적인 정리를 하려고 한다.
처음 배우는 문법이라 알고리즘을 만들거나 프로젝트를 진행하는 데 어려움이 있을 것이다.
가능한 C언어의 특징을 간략히 적어서 포스팅할 예정이다.
긴 글 읽어주셔서 감사드립니다.
22.11.26
'TIL (Today I Learned) > 알고리즘' 카테고리의 다른 글
| [알고리즘] Big O (1) | 2023.03.16 |
|---|---|
| [알고리즘] RB Tree개념과 삽입 동작 원리 #1 (0) | 2022.11.26 |
댓글