- RBtree 삽입에 대한 내용은 많은데, RBTree 삭제에 대한 내용이 별로 없어서 이 글을 씁니다.
- RBTree 삭제를 이해하기 위해선 double black 이라는 개념을 이해해야 합니다.
- double black이 생기는 이유는 아래와 같습니다.
삭제할 노드를 z라 하고, z위치에 놓을 노드를 v라 합니다. v가 z로 갈때, v또한 자리를 비우므로 v위치에 갈 노드를 u라 합니다.
이 때 v는 z의 속성을 그대로 따릅니다. z의 노드를 root로 한 subTree의 블랙개수를 그대로 이용하기 위함이죠
문제는 v가 z노드로 갈 경우,
v가 블랙이고 u가 레드일 때,
v가 올라가버리면 v의 subTree는 블랙개수가 하나 부족하니깐 v위치에 갈 u노드를 블랙으로 만듭니다. 그럼 블랙개수는 이전과 동일하죠?
v가 레드이고 u가 블랙일 때,
v가 그대로 올라가도 v는 레드이기 떄문에 v의 subTree의 블랙개수에 전혀 영향을 주지 않습니다. 그러므로 u는 v노드 위치에 그냥 가면 됩니다.
이제 진짜 문제가 기다립니다.
v가 블랙이고 u도 블랙일 때,
v가 올라가버리면 v노드의 subTree의 블랙개수가 하나 줄어 듭니다. 대체할 u도 블랙입니다. 이 경우 double black이라는 트릭을 씁니다. u를 double black으로 만들어 버립니다. 그리고 이것이 뜻하는 것은 트리의 회전을 뜻합니다.
어떤 회전을 할것인지는 v자리에 간 u노드의 sibling을 보고 판단합니다.
이것에 대한 자료는 영문으로 된 자료가 많습니다. 이 부분은 생략하겠습니다.
위의 내용을 코드로 만들고 오픈소스에 공개된 rbTree deletion 함수 부분이랑 비교해서 이해하시면 될 것 같습니다.
