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) 의 성능을 보인다 => 성능이 좋다