RB-Tree
좌우 서브트리의 높이차이
루트 기준 왼쪽 서브트리와 오른쪽 서브트리의 높이차이는 최대 루트 서브트리의 높이의 절반까지 될 수 있다.
즉 최대 2배.
삭제
삭제하려는 노드의 자녀가 없거나 하나라면
➡️ 삭제되는 색 = 삭제되는 노드의 색.
삭제하려는 노드의 자녀가 둘이라면
➡️ 삭제되는 노드의 successor의 색. -> 후임자?
삭제되는 색이 RED라면, 어떠한 속성도 위반하지 않는다.
- 모든노드는 빨강 혹은 검정
- 루트 노드는 검정
- 모든 nil 노드는 검정
- 노드가 빨강이라면 자녀들은 검정
- 임의의 노드에서 그 노드의 자손 nil노드들까지 가는 경로들의 검정 수는 같다
삭제되는 색이 black이라면.
삭제 후 속성위반 해결 방법
삭제되는 색이 검정일 때 특수한 상황을 제외하면 5. 속성을 항상 위반하게 된다.
5. 속성을 다시 만족시키기 위해 삭제된 색의 위치를 대체한 노드에 extra black을 부여함.
extra black의 역할
경로에서 black 수를 카운트 할 때 extra black은 하나의 black으로 카운트 된다.
검정색 10을 삭제. 10은 자녀가 없으므로 black이 삭제됨.
- 속성을 만족시키기 위해 10의 위치를 대체한 노드인 nil노드에 extra black을 부여함.
doubly black덕분에 검정색 2개가 카운트 되는 모습.
이번엔 30을 삭제. 자녀가 하나이므로 30의 검정색이 삭제되고, 이진트리의 속성을 만족시키기 위해 20과 25가 연결 되어야 함.
- 속성을 만족시키기 위해 25의 위치에 extra black 부여. 빨강 노드에 extra black을 추가한 것을
red-and-black이라고 함.
이번에는 50을 삭제할건데, 자녀가 둘이므로 빨간색을 삭제하는 것이아닌 후임자의 색깔인 검정색을 삭제함.
- 속성을 만족시키기 위해 nil노드의 extra black을 부여,
doubly black을 만들어 줬음.
extra black을 부여받은 노드는
doubly black이 되거나
red-and-black이 된다.
red-and-black 해결하기
➡️ red-and-black 을 black으로 바꾸면 해결.
30을 삭제하며 30과 검정색을 삭제할거임.
30을 대체하는 빨강 25에게 extra black을 부여하겠음. 25는 red-and-black이 되었으니, 25를 검정으로 바꿔주면 끝.
doubly black 해결하기
➡️ Extra black을 부여했더니 doubly black 노드가 생겼다면, 어떻게 extra black을 없앨거니?
4가지 case로 분류됨.
📍 4가지 case로 분류할 때의 기준은 doubly black의 형제의 색과 그 형제의 자녀들의 색을 기준으로 삼음.
case.4
🏷️ doubly black의 오른쪽 형제가 black & 그 형제의 오른쪽 자녀가 red일 때.
해결방법은 이러하고 간단하게 표현 할 수 있다.
오른쪽 형제는 부모의 색으로, 오른쪽 형제의 오른쪽 자녀는 black으로, 부모는 black으로 바꾼 후에 부모를 기준으로 왼쪽으로 회전하면 해결. => 루트 노드 기준으로 좌우를 바꿔도 성립함.
case.3
doubly black의 오른쪽 형제가black & 그 형제의 왼쪽 자녀가 red & 그 형제의 오른쪽 자녀는 black일 때
🏷️ doubly black의 형제의 오른쪽 자녀가 red가 되게 만들어서 이후엔 case.4를 적용해 해결하면 된다.
접근 방법 자체는 c의 빨강을 a의 doubly black위로 옮겨 red-and-black 으로 만들어줘서 해결하려는 아이디어로 case.4와 동일함.
-> C와 D의 색을 바꾼후 D를 기준으로 오른쪽으로 회전.
-> 이제 case.4 를 해결하듯 하면 된다.
C는 B의 색으로, B와 D는. black으로 바꾼 후 B를 기준으로 왼쪽으로 회전하면 해결.
완성된 모오습.
case.2
doubly black의 형제가 black & 그 형제의 두 자녀 모두 black일 때
🏷️ doubly black과 그 형제의 black을 모아서 부모에게 전달해서 부모가 extra black을 해결하도록 위임한다.
A의 doubly black과 형제의 검정을 모아 부모에게 전달하면 아래 사진처럼 바뀜.
지랄났네
case.1
doubly black의 형제가 red일 때
🏷️ doubly black의 형제를 black으로 만든 후 case 2,3,4 중에 하나로 해결
B와 D의 색을 바꿔주고 부모를 기준으로 왼쪽으로 회전(색바꾸고 꼭 드리프드 돌아줘야 함), doubly black을 기준으로 case,2,3,4중 하나로 해결.
🫎 정리
