R-B Tree의 삭제

삭제 OverView

1. 삭제 전 RB트리 속성 만족한 상태
2. 삭제 방식은 일반적인 BST와 동일
3. 삭제 후 RB 트리속성 위반 여부 확인
4. RB트리 속성을 위반했다면 재조정
5. RB트리 속성을 다시 만족

노드를 삭제할 때 어떤 색이 삭제되는지가 속성 위반 여부를 확인할 때 매우 중요하다.

삭제 되는 색에 따라서 위반 여부를 확인할 수 있다는 말이다.

위와같이 자식이 두개 미만인 노드라면 삭제되는 노드의 색을 삭제하면 된다.

여기서 20을 삭제한다고 하면 20 바로 다음으로 큰 값인 25가 Successor로 되게 되고 20의 자리로 이동하게 된다. 이때 successor의 색이 Red임으로 Red가 삭제가 된다.

여기서 햇갈릴 수 있는건 삭제되는 색이다.

우리는 successor를 삭제된 노드에 넣게 되는데 이 노드의 색을 유지시키겠다는 말이 된다.

자녀가 2개 미만이라면 삭제되는 노드의 색을 없애겠다 자녀가 2개라면 삭제되는 노드의 색을 유지시키겠다 라는 의미가 된다.

삭제시키는 색이 레드라면 어떠한 속성도 위반하지 않게 된다.

1번 속성은 당연히 통과가 되는것이고 2번 속성은 red가 삭제가 되었음으로 해당사항이 없게 된다.

3번 모든 nil 노드는 black인데 red를 삭제를 했음으로 해당 없고

4번 red를 삭제를 했음으로 자녀들의 색은 당연히 블랙이다.

5번또한 레드를 삭재했음으로 black의 수도 변동이 없다.

하지만 삭제되는 색이 black이면 말은 달라진다.

2,4,5번 속성이 black 과 관련된 내용이기 때문이다.

40이 삭제된다고 하면 red 노드와 red노드가 연속이 됨으로 4번 속성이 위반이 되며 black노드가 삭제 되었음으로 5번 규칙도 위반이 되게 된다.

만약 루트노드가 50의 자식 하나만 있을때에도 자식 red가 루트가 되면서 2속성이 위반이 되게 된다.

고로 삭제되는 색이 red라면 아무런 상관이 없게 되지만 black일 경우에는 조건이 많이 들어가게 된다.

2번 속성이 위반 되었을때는 간단하다. 삭제하고 그냥 루트 노드를 블랙으로 변경하면 된다.

이제 보통 마주하게되는 문제는 5번속성이다. 위와 같은 특수한 상황을 제외하면 항상 5번 속성인 black의 수에 위반이 된다.

이때 빠르게 해결하기 위해 extrablack을 부여해서 이를 해결하게 된다. 즉 nil + extrablack을 만들어서 doubly black 을 만들어서 갯수를 채워준다.

*doubly black : extrablack이 부여된 black 노드

위와 같이 red가 올라오게 될 경우에는 red에 extra black을 부여해서 black의 갯수를 맞춰준다.

이때 노드는 red-and-black이 된다.

red-and-black: extra black이 부여된 red노드

여기서 red-and-black의 조치는 쉽다. 그냥 red-and-black노드의 색을 black으로 변경해주면 해결이 된다.

 

문제는 doubly black이다. 이는 총 4가지의 case로 분류가 되어 해결을 할 수 있다.

이때의 기준은

1. doubly black의 형제의색
2. 그 형제의 자녀들의 색

으로 분류할 수 있다.

레드를 doubly black위로 옮기고 옮긴 red로 extrablack을 전달해서 red-and-black으로 만들면 black으로 만들 수 있으니 이처럼 해결하는 방식을 사용할 수 있다.

 

5번 속성에서 자녀와 부모의 색을 바꿔도 RB트리의 속성을 만족하는 특성을 이용해서 문제를 풀 수 있다.

 

위의 그림과 같이 모르는 노드에게 extra-black을 부여하면 5번속성을 만족 시킬 수 있다.

 

위와같은 과정을 통해서 노드를 정렬 할 수 있고 5번 속성을 만족시킬 수 있다.

결과론 적으로는 위의 내용이 완성된다. (case 4)

다른 케이스를 확인하겠다.

위와 같은 내용은 red노드의 위치가 조금 다른데 case4와 같이 해결을 하기 위해서는 c의 위치를 e로 변경하고 위의 과정을 똑같이 반복하면 해결이 된다.

위의 결과물을 만들어 낼 수 있게 된다.

이와 같은 상황을 case 3라고 한다.

 

또 다른 케이스를 확인해보겠다.

위의 예제는 A의 extra black과 D의 black을 B에게 전달을 함으로써 D를 red로 만들고 A를 black으로 만들어서 해결을 시작한다.

위와 같이 B가 extra-black을 받아도 5번속성은 만족하게 된다.

B가 red-and-black이면 상황이 종료되지만 B가 루트노드라면 black으로 변경해서 종료 아니라면 case1234중 하나로 해결해야한다.

위와 같이 double black의 형제가 black이고 그 형제의 두 자녀 모두 black일때 doubly black과 그형제의 black을 모아서 부모에게 전달해서 부모가 extra black을 해결하도록 위임한다. (case2)

위와 같은 과정을 가지게 된다.

위와 같이 doubly black의 오른쪽 형제가 red일때 case1을 사용할 수 있게 된다.

자 결론적으로 정리를 하자면

R-B Tree시간복잡도

 

스스로 균형을 잡기 때문에 시간복잡도는 항상 같게 된다.

 

AVL 트리와 비교