[Algorithm] Red Black Tree

레드 블랙 트리 (Red Black Tree)란?

레드블랙 트리는 지난번에 포스팅했던 트리에서 이어진다. 균형 이진 탐색 트리의 예시에서 레드블랙 트리를 언급했었고, 상당히 내용이 있는 이론이기 때문에 새로운 포스팅으로 옮겼다. 따라서 이진 탐색 트리에 대해서 안다고 가정하고 이어서 작성해보려고 한다.

 

---

특징

1. 모든 노드는 빨간색 또는 검은색이다.
2. 루트 노드는 검은색이다.
3. 잎 노드는 검은색이다. (NIL 노드)
4. 빨간 노드의 자식은 모두 검은색이다. (레드 노드는 연달아 나타날 수 없다.)
5. 루트 노드에서 모든 잎 노드 사이에 존재하는 검은색 노드의 수는 모두 동일하다.

---

구현

탐색의 경우 기존의 BST와 동일하게 해주면 된다. 하지만 노드의 삽입과 삭제에서 문제가 발생한다. 트리의 균형이 유지가 안되기 때문이다. 이에따라 나온 방식이 있다.

 

삽입을 하는 과정에서 4번 규칙을 어기게 된다면, 즉 double red가 나타난다면?

1. Restructuring: 현재 삽입된 노드의 uncle node(부모의 형제)가 검정인 경우
2. Recoloring: 현재 삽입된 노드의 uncle node가 빨강인 경우

이 두가지 중 하나를 선택해서 수행하게 된다.

 

Restructuring

Restructuring은 다른 서브트리에 영향을 끼치지 않기 때문에 한번의 수행이면 끝난다.

수행시간은 O(logn)이다.

1. 나와 내 부모, 내 부모의 부모를 오름차순으로 정렬
2. 정렬한 결과에서 무조건 가운데 있는 값을 부모로 만들고 나머지 둘을 자식으로 만든다.
3. 올라간 가운데 있는 값을 검정으로 만들고 그 두자식들을 빨강으로 만든다.

Recoloring

Recoloring은 Restructuring과는 다르게 여러번 일어날 수 있다.

1. 현재 삽입된 노드의 부모와 그 형제를 검정으로 하고 부모의 부모를 빨강으로 한다.
2. 부모의 부모가 루트 노드가 아니었을 시 Double Red가 다시 발생할 수 있다.

 

Reference

https://zeddios.tistory.com/237