[Jungle] Week5. Red-Black Tree 의 삽입 연산

somi·2024년 4월 19일

[Krafton Jungle]

목록 보기

33/68

Red-Black Tree

이진 탐색 트리(BST)의 한 종류

스스로 균형을 잡는 트리
: 자가 균형 이진 탐색 트리(Self-balancing binary search tree) => 대표적으로는 연관 배열 등 구현하는데 쓰이는 자료구조

BST의 worst case의 단점을 개선

: 최악의 경우 이렇게 한쪽으로 편향될 수 있음 -> 시간 복잡도가 O(N) 오래 걸린다는 단점을 레드 블랙 트리는 최악의 경우에도 O(logN)이 되도록 개선!
트리의 n개의 원소가 있을 때 O(log N)의 시간 복잡도로 삽입, 삭제, 검색 가능.

모든 노드는 red or black
레드 블랙 트리는 복잡한 자료구조지만, 실제 사용할 때 매우 효율적이다. 최악의 경우에도 상당히 우수한 실행 시간

참고) 연관 배열 :
하나와 값 하나가 연관되어 있으며 키를 통해 연관되는 값을 얻을 수 있는 구조 대표적으로 파이썬 딕셔너리

레드 블랙 트리의 속성

1. 모든 노드는 Red/Black
2. 루트 노드는 Black
3. 모든 NIL 노드는 Black
4. 노드가 Red면 자식은 Black
: Red는 연속하면 안된다.
5. 임의의 경로(자신을 제외)부터 자손 NIL까지 Black 개수는 동일하다.

모든 노드는 red or black
루트 노드는 black

nil node?

존재하지 않음을 의미하는 노드

자녀가 없을 때 자녀를 nil로 표기

값이 있는 노드와 동등하게 취급

RB Tree에서 Leaf node는 nil node
-> leaf node는 자녀가 없는 노드 => rb tree에서는 nil node

모든 nil(leaf) 노드는 black이다.

red의 자녀들은 black

=> red가 연속적으로 존재할 수 없다.

임의의 노드에서 자손 nil 노드들까지 가는 경로들의 black의 수는 같다. (자기 자신은 카운트에서 제외)

node x의 black height

노드 x에서 임의로 자손 nil 노드까지 내려가는 경로에서의 black 수 (자기 자신은 카운트에서 제외)

=> 임의의 노드에서 자손 nil 노드들까지 가는 경로들의 black 트리의 수는 같다는 속성을 만족해야 성립하는 개념
위의 그림에서 20의 black height = 2
50의 black height = 2

색을 바꾸면서도 임의의 노드에서 자손 nil 노드들까지 가는 경로들의 black 트리의 수는 같다는 속성 유지하기

RB 트리가 임의의 노드에서 자손 nil 노드들까지 가는 경로들의 black 트리의 수는 같다는 속성 을 만족하고

두 자녀가 같은 색일 때

부모와 자녀의 색을 바꿔줘도

그 속성은 여전히 만족한다.
=> 자기 자신은 카운트에서 제외하니까

레드블랙 트리는 어떻게 균형을 잡는가?

=> 삽입 삭제 할 때
노드가 red라면 자녀들은 black이다.
임의의 노드에서 자손 nil 노드들까지 가는 경로들의 black 수는 같다. 를 위반하게 된다.
이를 해결하려고 구조를 바꾸다 보면 자연스럽게 균형이 잡히게 된다.

RB TREE 삽입

삽입 전 RB 트리 속성 만족한 상태

삽입 방식은 일반적인 BST와 동일

삽입 후 RB 트리 위반 여부 확인

RB 트리 속성을 위반했다면 재조정

RB 트리 속성을 다시 만족

삽입하는 노드의 색은 항상 red이다.

red 삽입 후 루트 노드는 black 이라는 속성을 위반한다면
=> 루트 노드를 black으로 바꿔준다.

왜 새로 삽입하는 노드는 red?

삽입 한 후에도 임의의 노드에서 자손 nil 노드들까지 가는 경로들의 black 수는 같다 는 속성을 만족하기 위해서 !

삽입하는 노드가 Red라면 삽입 후에도 nil 노드들까지 가는 경로들의 black 수는 같게 된다.

삽입 처리

insert-fixup (삽입 시 속성 위반 재조정)
삽입 후에
#2 루트 노드는 Black
#4 노드가 Red면 자녀는 Black (Red는 연속하면 안됨)
위반할 경우가 발생하니 다음과 같이 알고리즘 수행하며 속성 위반 해결

while (부모가 Red) {
	//case1 
    if 부모/삼촌 == RED,
    	부모/삼촌 모두 black으로 바꾸고, 할아버지 red로 변경
        할아버지에서 다시 시작
        
    //case2/3. 삼촌 == black
    else {
		//case 2.
        if 할아버지/부모/자신 꺾인 상태
        	회전해서 부모/자신을 펴준다. case3 상태가 됨
            
        //case 3. 할아버지/부모/자신 펴진 상태
        	부모/할아버지 색 서로 바꾸기
            할아버지 기준 회전
	}
}

//종료 전
루트를 black으로 변경

수평으로 배치된 두개의 레드가 있다면, 색상을 블랙으로 변경하고 부모를 레드로 바꿀 수 있다.

노드가 red라면 자녀는 black 속성 위반을 해결하려면
red 하나를 넘겨야 하는데, BST의 특징 또한 유지하면서 넘기려면 회전을 사용해야 한다. -> 회전을 어떻게 사용할 것인가 ?

먼저 색을 바꾸고 (루트 노드는 black) 이어야 하니까, 회전시킨다.