09-04레드 블랙 트리(Red Black Tree)

 

아래의 상기 내용은

"이것이 자료구조+알고리즘이다. With C언어"의 도서 내용과 인터넷의 내용을 실습 및 정리한 글입니다.

 

 

1.레드 블랙 트리(Red Black Tree)

 1)개요

 -이진 트리는 동적 크기가 증가하는 데이터도 잘 처리하며 탐색 속도 좋다.

-하지만 위와 같이 한쪽으로 편중된 상태의 트리가 만들어 질 경우 탐색 효율이 극단적으로 떨어진다.

-위의 문제를 해결한 방식이 레드 블랙 트리가 있다.

-레드 블랙 트리(Red Black Tree)란 레드 블랙 두가지 요소로 된 

 자가 균형 이진 트리(트리에서 노드의 삽입과 삭제 같은 연산이 일어날 때 자동으로 균형 트리)이다.

 

2.레드 블랙 트리의 구현 규칙

 1)구현 규칙

  2)NIL 노드

 -센티널(Sentinal) 노드라고 하며 아무 데이터도 갖지 않는 검은색 노드이다.

 -레드 블랙 트리에 대한 구현을 용이하기 위해 만든 더미 노드이다.

 -원래의 모든 잎 노드가 NIL을 가리킨다면 모든 잎 노드는  검은색이라는 규칙을 지키기 수월하다.

3.레드 블랙 트리 중요 연산 : 회전

 1)개요

 -회전이란 트리에서 부모와 자식 노드의 위치를 서로 바꾸는 연산.

 -회전은 오른쪽 자식과 부모의 위치를 바꾸는 좌 회전과 왼쪽 자식과 부모의 위치를 바꾸는  

  우회전으로 나뉜다.

 

 -위의 그림에서 이진 트리의 규칙이 깨지지 않게 6의 노드가 이동하였다.

 

 3.레드 블랙 트리 중요 연산 : 삽입

  1)개요

 -레드 트리의 새 노드를 삽입하면 노드 색깔을 빨간색으로 하고 양쪽자식을 Nil노드로 연결한다.

 -새 노드에 연결되는 부모 노드가 검은색이면 규칙에 위반되지 않는다.

 -부모 노드가 빨간색이라면 빨간색 노드의 자식은 검은색이라는 규칙이 위반된다.

 -이 문제를 해결해야 하는 상황의 경우 새 노드의 삼촌 노드(부모 노드의 형제 노드)에 따라

  3가지로 나뉜다.

 2)새 노드의 삼촌 노드가 빨간색일 경우

 -기본적으로 부모 노드와 삼촌 노드를 검은색으로 만들고 할아버지 노드를 빨간색으로 칠한다.

 -다만 할아버지의 노드의 색깔을 변경 한 것에 따라 규칙 다시 위반될 수 있다.

 -트리를 계속해서 올라가는 방식으로 전체적인 관계를 검사하고 올라가는 노드가 뿌리 노드이거나

 검은색노드일 때까지 반복한다.

 

3)삼촌 노드가 검은색이며 새 노드가 부모 노드의 왼쪽 자식일 경우

-부모 노드를 검은색으로 할아버지 노드를 빨간색으로 바꾼 뒤 할아버지 노드를 우회전한다.

4)삼촌 노드가 검은색이며 새 노드가 부모 노드의 오른쪽 자식일 경우

 -부모 노드를 좌회전 시킨 다음 2)에서 했던 것과 같이 적용한다.

4.레드 블랙 트리 중요 연산 : 제거

1)개요

 -노드를 삭제할 때 빨간색 노드를 제거할 경우 규칙에 위반되지 않는다.

 -검은색 노드가 삭제되면 검은색 노드 수가 달라지므로 5번의 규칙에 위반되고

 삭제된 노드의 부모 자식이 빨간색이라면 4번 규칙 또한 위배되게 된다.

 -그래서 위의 대한 해결방법으로  대신하게 되는 노드의 색깔을 검은색으로 바꾸고 그에 대한 처리를 하는 방법이 있다

-대체 노드를 검은색으로 바뀌게 되면 4번 규칙을 해결하고 5번 규칙에 대한 위반을 처리한다.

-처리에 있어 경우 수가 대체노드의 형제 노드의 상태에 따라 나뉘게 된다.

2)형제 노드가 빨간색인 경우

 -형제 노드를 검은색, 부모 노드를 빨간색으로 변경한다.

 -그 다음 부모 노드를 좌회전 시킨다.

 -이렇게 되면 형제 노드는 검은색이 되고 나중에 후술 경우에 따라 처리하면 된다.

3)형제 노드가 검은색이고 형제 노드의 양쪽 자식 노드가 모두 검은색인 경우

 -형제 노드는 빨간색 부모 노드를 검은색으로 칠한다.

4)형제 노드가 검은색이고 형제의 왼쪽 자식은 빨간색, 오른쪽 자식은 검은색인 경우

 -형제 노드가 검은색이고 형제의 왼쪽 자식은 빨간색, 오른쪽 자식은 검은색인 경우는

 왼쪽 자식은 빨간색, 오른쪽 자식은 검은색인 경우로 바꿔서 다시 처리한다.

 -그러기 위해 형제 노드를 빨간색으로 칠하고 왼쪽 자식을 검은색으로 칠한 다음 형제 노드 기준으로

 우회전 한다.

 

5)형제 노드가 검은색이고 형제의 왼쪽 자식은 검은색, 오른쪽 자식은 빨간색인 경우

 -형제노드를 빨간색을 변환 후 부모 노드와 형제노드의 오른쪽 자식 노드를 검은색으로 변경한 후

 부모노드를 기준으로 좌회전 시킨다.