Red-Black Tree 검색중 성능이 가장 좋다

Red Black Tree 의 특징 : 2-3-4 트리를 Binary Tree 로 표현 한것

(2-3-4 트리는 3차 B-Tree 와 돌아가는 것이 동일하다)

먼저 2-3-4 트리를 알아야 하는데

노드의 자식이 2,3,4 개가 존재 할 수 있다고 하여 2-3-4 트리이다

A 를 가지고 있는 노드는 2개의 자식을 갖는다

A B 를 가지고 있는 노드는 3개의 자식을 갖는다

A B C 를 가지고 있는 노드는 4개의 자식을 갖는다

Red Black 트리는?

2-3-4 트리를 이진트리로 나타낸 것

그림에서 2노드 인 경우 A 를 검정색 A 노드로 표현

3노드 인 경우 B 를 빨강으로 내리거나 A 를 빨강으로 내려 표현

4노드의 경우 B 를 제외한 양쪽을 빨강으로 내려 표현

Red-Black 트리에서는 이렇게 자식으로 내리지만 2-3-4 트리에서는 하나의 노드로써 결합의 의미를 갖는다

2-3-4 트리를 보면 B-Tree 의 형태 임을 알 수 있다( 동작도 동일하다 )

즉 B-Tree 를 이진 트리 형태로 바꾼것!!!

---

이진트리와 동일하게 부모노드의 왼쪽 서브트리보다 크고 오른쪽 서브트리보다 작다

Root 에서 Leaf 로 가는 경로의 검정노드의 수는 모두 같다 => B-Tree 에서 빨강이 자식으로 확장된 형태이므로

원래 B 트리는 모든 자식의 레벨이 같다, 그래서 확장된 빨강 노드를 제외하면 루트에서 자식까지 가는 검정노드의 수는 갖게 된다

---

색변환 (color flip)

상향 색변환 : 빨강을 위로 올림 => 검정색의 자식의 두개의 빨강 노드일경우 부모를 빨강으로 바꾸고 두 자식을 검정색으로 바꾸는 것

하향 색변환 : 위에 있는 빨강을 자식을 빨강으로 바꾸는 것 -> 부모는 검정이 된다 (상향 색변환과 반대)

회전 : 이진트리의 규칙을 깨지 않고 트리를 재구성 하는 방법(우회전, 좌회전) => 좌우의 트리 높이를 맞추는 방향으로 회전함=>AVL Tree 의 기본 동작

이렇게 분할 하는 이유는 자료를 삽입하기 위함 ( 트리의 균형을 깨지 않고 )

(노드안에 자료가 3개면 => 4노드)

위 그림이 상향식 변환 ( 위의 그림에서 녹색 부분이 B-Tree 의 설명 아래 있는 것이 RB-Tree )

루트는 원래 검정이라 빨간색으로 자식을 내리건 안내리건 간에 Root 는 검정색이된다

루트가 검정색

---

pivot 은 회전의 축이 된다

회전하면서 자식들의 위치는 이진트리의 부모의 왼쪽은 작고 오른쪽은 큰 순서를 유지하기 위한 순서대로 구성해준다

---

- 트리에서는 노트의 끝을 노드로 표현하지 않고 0 로 표현 할 수 있다

- RedBlack 을 표현하기 우해 bool red; 로 표현 한다

- RB 트리도 기본적으로 중복을 허용하지 않는다( list 등으로 노드에서 중복을 허용하는 구조로 만들 순 있다)

[RB-Tree 검색]

검색 알고리즘은 이진 트리와 동일하다( 키 값으로 비교하여 왼쪽, 또는 오른쪽으로 이동 )

---

[RB-Tree 삽입]

single rotation, double rotation 으로 이루어진다

구조는 이진트리와 동일하기 대문에 노드 순서 규칙은 동일

균형을 맞추기 위해 색변환 -> 노드 분할, 결합등을 하게 된다

=> 이때 빨간노드가 연속되는 상황이 벌어질 수 있는데 이때의 균형을 맞추기 위해 Rotation 을 한다

=> 자료를 삽입할때 부모가 빨간노드이면 Rotation 을 한번 한 후 삽입 한다

right rotation, left rotation => single rotation

right rotation 한다음 left rotation , left rotation 한다음 right rotation => double rotation

[Single rotation]

1. 상향색 조정을 했을때 빨간 노드가 연달아 나타나게 되는 상황이 발생되면

2. 회전을 하면서 노드의 색깔이 변경되고, 그럼으로서 노드의 균형을 맞춘다

회전시키기 위해선 t, p, gp(부모의 선조), ggp 의 4개가 있어야 한다

그림상 B-Tree 부분 에서(각 이미지의 아래에 그려진 트리) 노드안의 자료가 3개일때 분할하는 모습을 볼 수 있다(이것이 rotation 의 회전과 동일)

---

[double rotation]

left-right rotation 그림중에서 1번 을 보면 single rotation 에서와는 달리 두개 연달아 나오는 레드 노드 위로의 선이 반대인 것을 볼 수 있는데

이때는 두번 회전으로 노드를 정리해줘야 한다 => double rotation

1.상향 색조정을 아래에서 한번 하게 되면 레드 노드가 연달아 나오게 된다

2.Right-left rotation 에서 보면 C 를 pivot(중심)으로 해서 한번 회전 하면 선이 펴지게 된다 => 색변환 일어나지 않는다

3. 그다음 C 가 회전 되어진다 => single rotation 처럼 회전 => 색변환이 일어난다

---

[키값에 의한 회전]

왼쪽 상단 그림을 보면 G 를 키 값으로 주고 E 에서 G 쪽으로 향하는 방향으로 회전을 시켜주고

3번째 그림에서는 E 값을 키 값으로 놓고 E 에서 C 의 방향으로 회전을 하게 된다

pivot, child, gchild 는 아직 정해지지 않은 각 노드 포인터

*회전 호출시 pivot 을 정하고 넘겨준다

gchild 를 키값으로 하여 gchild 에서 child 의 방향으로 회전

회전의 방향 = 키값(노드안의 데이터)

회전의 위치 = pivot( pivot 의 왼쪽 또는 오른쪽 노드에 의해서 child 가 결정된다 )

child 와 키 값에 의해서 gchild 가 결정되면서 회전하게 된다

pivot 과 키값(gchild)의 비교에 의해서 child 가 가르킬 노드를 정해준다

child 와 gchild 의 위치관계를 pivot 과 키값에 의해 따져서 회전시켜준다

if (key > child->data || key == child->data)

Rotate left

else

rotate right

// key == child->data 일때도 오른쪽인 이유는 나중에 내부노드 삭제를 할때 루트보다 바로 큰 노드와 바꿔치기 하여 루트를 삭제 하기 위한

처리와 맞춰주기 위함 즉 삭제시 루트에서 오른쪽으로 한번간 후 왼쪽으로 계속가서 루트보다 바로 큰 노드를 찾기 위한 오른쪽 탐색을

하는 처리와 맞춰주기 위함이다

끝난 후 변견된 트리의 pivot 의 자식을 설정해 주어야 하는데

gchild 가 상단으로 올라감으로 gchild 를 pivot 의 자식으로 주어야 한다

그런데 왼쪽으로 줄것인지 오른쪽으로 줄것인지를 결정하기 위하여

key 와 pivot->data 의 비교로 위치를 결정한다

---

[insert ]

삽입시 자식노드 둘다 레드이면 칼라상향조정

칼라 조정후 부모가 레드면 회전

회전하려고 할때 노드 연결이 단방향이 아니고 꺽여 있으다면 double rotation

t,p,gp,ggp 의 관계를 살펴본다

if( p->red ){

if( value > gp-data != value > p->data )

rotation(value, gp);

t= rotation(value,ggp);

t->Red=true;

}

마지막 하단에 노드를 삽입할때도 그때의 부모가 레드면 로테이션( or double rotation) 후 삽입

회전이 다 된후 노드가 맞는 위치에 삽입된다

그래서 좌우 트리가 두배 이하로 유지가 된다

---

[delete]

C++ 알고리즘 참고

delete 에서 color demotion 이 나온다, 왜냐하면 삭제시 노드가 아에 없어지면 자식을 갖지 못하는 상화이 벌어 질 수 있으므로

쉽게 위해 하기 위해서는 B-Tree 로 전 후를 만들어 본 다음 만든 트리를 Red-Black 트리로 변행해 본다음

바뀐것들으 알아보는 것

---

[Red-Black 트리 분석]

트리의 높이

black height => black 노드로 이루어진 레벨의 개수

둘다 black 노드의 높이는 2 이다 , black height

black height 는 2 인데 개수는 왼쪽이 3개, 오른쪽이 15개

N+1 = 노드개수(3)+1 은

s^B <= N+1 <= 4^B (B = black height)

왼쪽은 H(Height) = B(Black Height) = 2

오른쪽은 H(Height) = 2B(Black height) = 4

O(logN) 의 성능을 보인다 => 성능이 좋다