R-B Tree의 삽입

R-B Tree란?

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

특징으로는 스스로 균형을 잡는 특징이 있으며 BST의 단점인 worstcase를 개선했다.

위의 그림같은 경우 이진 탐색트리의 시간복잡도는 O(N)이 되지만 R-B Tree는 트리의 균형을 잡음으로써 이를 개선할 수 있다.

 

 

R-B Tree 의 속성

1. 모든 노드는 red 혹은 black이다.
2. 루트 노드는 black이다.
3. 모든 nil노드는 블랙이다.
4. red의 자녀들은 black → red는 연속적으로 존재할 수 없다.
5. 임의의 노드에서 자손 nil 노드들까지 가는 경로들의 black 수는 같다. (자기자신은 제외)

nil 노드란

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

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

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

RB Tree에서 leaf 노드는 nil

 

노드x의 black height

• 노드 x에서 임의의 자손 nil 노드까지 내려가는 경로에서의 black 수
• (자기 자신은 카운트에서 제외)
• 5번 속성을 만족해야 성립하는 개념

RB 트리는 어떻게 균형을 잡는가?

삽입/삭제 시 주로 4,5번 속성을 위반하며 이들을 해결하려고 구조를 바꾸다 보면 자연스럽게 트리의 균형이 잡히게 된다.

nil 노드란

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

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

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

RB Tree에서 leaf 노드는 nil

삽입 Overview

1. 삽입 전 RB 트리 속성 만족한 상태
2. 삽입 방식은 일반적인 BST와 동일
3. 삽입 후 RB트리 위반 여부 확인
4. RB트리 속성을 위반 했다면 재조정
5. RB트리 속성을 다시 만족

삽입 과정

1. 삽입하는 노드는 항상 Red이다.
2. 노드를 삽입할때 nil노드의 색은 black으로 고정한다.
3. → 그러면서 3번 속성 만족
4. 루트 노드는 Black이여야 함으로 Black으로 변경

왜 삽입하는 노드는 RED인가?

→ 삽입 후에도 5번 속성을 유지하기 위해

 

Red노드 삽입 후 4번 속성을 위반했을때

Red 노드를 삽입 후 RB트리의 조건을 위반할 경우가 생긴다 우리는 보통 4번과 5번속성 위반이 많이 발생하게 되는데 4번속성이 위반되었을때 3가지의 case를 해결하는 방법을 알아보겠다.