RB_Tree(레드블랙트리)

RB_Tree(레드블랙트리)

1. RB트리 특성

2. RB트리 삽입

이진트리의 경우 계속하여 큰값이나 작은값이 들어올 경우 노드가 한쪽으로 치우칠 수 가 있다.

균형이 맞지 않는(unbalanced) 트리의 예

이경우 특정 key값을 탐색하는데 시간이 늘어나는 단점이 있으며

이를 보완한 것이 자가균형이진탐색트리 Red-Black Tree이다.

래드블랙트리

RBtree의 특성

모든 노드의 색은 빨간색 혹은 검은색 이다. 루트 노드는 검은색 이어야 한다. 모든 리프노드는 루트노드와 같은 검은색이다. 빨간색 노드의 자식은 모두 검은색이다. 루트노드에서 리프노드까지 가는 경로상 만나는 검은색 노드의 수는 모두 동일하다.

RBtree 삽입

기본적 삽입은 이진트리의 삽입과 같다 그러나 삽입과정에서 루트 노드는 검은색이어야 하며 빨간색 노드의 자식은 검은색이어야 한다는등 조건이 있어 RB트리의 특성을 만족하여 특정 key값의 삽입 혹은 삭제시 균형잡힌 트리를 회복하기 위해 아래와 같이 회전이 발생한다.

RB트리의 삽입 left회전 

위 과정에서 생략된 과정은 삽입과정에서 삽입되는 노드의 처음 색은 빨간색이라는 과정이다 이후 만약 이것이 루트노드라면 검은색으로 바꾸어 주는 과정을 거친다.

따라서 맨처음 들어온 10은 빨간색 이었다 그다음 20은 빨간색으로 10보다 크므로 10의 right노드로 들어온다.

그다음 들어올 30도 빨간색을 가지고 들어오며 10보다 크므로 riight 20보다 크므로 right 노드에 위치한다.

이때 20도 빨간색 30도 빨간색이라 <빨간색 노드의 자식은 모두 검은색> 이라는 조건을 어겼기 때문에 회복과정이 필요하다.

단순하게 30의 색을 검은색으로 바꾸면되지 않을까? 하지만 이렇게 되면

<루트노드에서 리프노드까지 가는 경로상 만나는 검은색 노드의 수는 모두 동일하다.>

위 규칙이 안맞게 된다.

위의경우에서는 LEFT 회전으로 RB트리의 조건을 만족시켜 주었다.

삽입과정의 문제 해결

위와같은 삽입 과정의 문제를 해결하기 위한 경우는 크게 아래 3가지 경우로 나뉜다.

1. 삼촌노드가 red인경우

2. 삼촌은 검은색이며 새로 삽입한 노드가 부모노드의 오른쪽 자식인경우

3. 삼촌은 검은색이며 새로 삽입한 노드가 부모노드의 왼쪽 자식인경우

이다.

1. 삼촌 노드가 red인경우

빨간색이 NEW노드 파란색 삼촌 부모노드 ->검은색 조상노드->빨간색

2. 삼촌은 검은색이며 새로 삽입한 노드가 부모노드의 오른쪽 자식인경우

위 애니메이션의 경우 2번경우에 속한다. -> LEFT 회전으로 해결

3. 삼촌은 검은색이며 새로 삽입한 노드가 부모노드의 왼쪽 자식인경우

2번과 반대로 RIGHT 회전을 해주면 해결된다.

공유하기 글 요소 저작자표시

from http://younsw.tistory.com/25 by ccl(A) rewrite - 2021-12-06 00:00:21