[RB Tree] 삭제

 

1. 삭제하려는 노드의 자녀가 없거나 하나라면 = 삭제 되는 색 - 삭제되는 노드의 색
2. 삭제하려는 노드의 자녀의 둘이라면 = 삭제 되는 색 - 삭제되는 노드의 successor의 색

sucessor : 해당 노드의 오른쪽 sub tree의 가장 작은 값  - if 오른쪽 sub tree가 없다면 ... 해당 노드의 왼쪽 sub tree의 가장 큰 값

 

삭제 되는 색

1. red : 어떠한 속성도 위반 x
2. black : 위반

case 1. 삭제를 통해 root node의 색이 빨간색으로 바뀔 때, root node를 검정 색으로 바꾸면 해결이 됨.

 

만약 black 이 삭제되게 되면, RB Tree의 속성을 유지하지 못하게 된다. 따라서, extra black을 이용해서, 경로에서 black 수를 count 할 때, black 수가 일정하게 유지될 수 있도록 한다.

 

extra black을 어디에 부여? 삭제된 검정 색의 위치에 extra black을 부여.

nil 노드는 black으로 count하는데, 해당 색이 삭제되면서 extra black이 붙게 되면 doubly black이라고 명명한다.

 

red node에 extra black 이 붙게 되면, red-and-black 이라고 명명한다.

 

1. red - and - black 해결하기 : black으로 바꿔준다.
2. doubly black 해결하기 -> 4가지 case로 분류가 됨.

• doubly black의 오른쪽 형제가 black이고, 그 형제의 오른쪽 자녀가 red일 때:
  그 red를 doubly black 위로 옮기고, 옮김 red로 extra black을 전달해서 red-and-black으로 만들면 red-and-black을 black으로 바꿔서 해결
  
  
• doubly black의 오른쪽 형제가 black & 그 형제의 왼쪽 자녀가 red & 그 형제의 오른쪽 자녀는 black일 때:
  doubly black의 형제가 오른쪽 자녀가 red가 되게 만들어서 이후엔 case.4를 적용하여 해결
  
  
• doubly black의 형제가 black & 그 형제의 두 자녀 모두 black 일 때:
  doubly black과 그 형제의 black을 모아서 부모에게 전달해서 부모가 extra black을 해결하도록 위임한다.
  위임한 extra black을 통해 red-and-black이 되었다면 black으로 바꿔주면 상황은 종료.
  doubly black - b가 루트 노드 일 시, black으로 바꿔서 해결. 아니라면 case 1, 2, 3, 4 중에 하나로 해결.
  
  
• doubly black의 형제가 red일 때:
  doubly black의 형제를 black으로 만든 후 case 2, 3, 4 중에 하나로 해결

 

아주 복잡...그 잡채