[레드 블랙 트리] 속성과 삽입

출처 : https://www.youtube.com/watch?v=2MdsebfJOyM

nill 노드란

존재하지 않음을 의미한다.

자녀가 없을 때 자녀를 nill노드로 표현한다. 값이 있는 노드와 동등하게 취급한다.

모든 nill노드는 블랙이다.

레드 블랙 트리 특징

1. 루트 노드는 블랙, 모든 노드는 블랙 혹은 레드이다.
2. 레드가 연속할 수 없다.
3. 모든 Nill노드는 블랙이다.(리프노드)
4. 레드의 자녀는 모두 블랙이다.
5. 임의의 노드에서 nill노드까지의 블랙 노드의 수는 동일하다 (본인 제외)

블랙 height = 노드 x에서 임의의 자손 nill까지 갈 때 경로의 모든 black의 수는 같다.

부모와 두 자녀의 색을 바꾸어 주어도 5번 속성은 유지된다.

 

트리들의 삽입, 삭제하며 위 속성을 맞추다 보면 균형된 트리가 만들어진다.

삽입되는 노드는 레드이다. ( 레드는 추가해도 black height가 변경되지 않기 때문에)

 

삽입 예제

case 1

10을 추가했을 때 레드가 연속이므로 2번 규칙 위반한다.

해결하기 위해 회전을 사용해야한다. 먼저 20과 50의 색을 바꾼 후 오른 쪽으로 회전을 한다.

해결이 되었다.

case 정리

레드를 삽인한 후에 위와 삼촌이 블랙인 경우 부모와 할아버지 색을 바꾼 후 할아버지 기준으로 오른쪽 회전한다.

case2

 

레드가 연속이므로 2번 조건 위반

이땐 20을 기준으로 왼쪽으로 회전을 하면 case1과 같은 상황이 되므로 case1과 같은 방법으로 해결을 하면 된다.

케이스 정리

1번 case와 동일하게 해 주기 위해 부모기준으로 왼쪽 회전을 한 후 case1과 동일하게 해결

case3

2번 속성 위반이다.

10,50을 블랙으로 20을 레드로 바꿔준 후 해결하면 된다.

루트가 레드이면 안되므로 블랙으로 바꿔주면 모든 속성을 만족한다.

이 경우는 부모와 삼촌을 모두 black으로 할아버지를 red로 바꾼 후 할아버지부터 다시 확인을 시작하면 된다.

case 정리

(부모와 삼촌)을 블랙으로 할아버지를 레드로 바꾼 후 할아버지에서 다시 확인한다.

삽입 최종 마무리

아래 그래프에서 25를 추가한 경우, 레드 연속이므로 레드-블랙트리 속성을 만족하지 않는다.

부모와 삼촌 모두 레드인 경우이므로 30,40을 블랙으로 35를 레드로 바꾼다.

바꾼 후 35에서 확인을 했더니 50,35 불만족하는 경우이고, 삼촌인 10이 블랙이므로 50을 기준으로 오른쪽으로 회전을 한 후 다시 왼쪽을 회전을 하면 된다. 

이때 회전은 80은 50과 함께 오른쪽을 내려가고, 35, 30, 25는 왼쪽으로 남은 40은 붕 뜨게 되는데 50이 오른쪽으로 내려오면서 왼쪽 자녀가 비었기 때문에 왼쪽 자녀로 가면 된다.

이 경우는 위와 같이 20과 35의 색을 바꿔준 후

20을 기준으로 왼쪽으로 회전을 하면 된다.

이때 20, 10은 왼쪽으로 내려오게 되고, 30,25는 붕뜨게 되는데 20의 오른쪽 자녀가 비어있게 되므로 오른쪽에 붙으면 된다.

모든 속성을 만족한다.

 

삭제

레드를 삭제하는 경우는 아무 문제가 되지 않는다.

삭제되는 속성이 블랙이면 위반한 속성을 해결하면 된다.