[Red-Black 트리]삽입

SWjungle/#레드블랙트리

[Red-Black 트리]삽입

장영 2023. 9. 4. 00:40

Red-Black 트리의 삽입 방식

📌삽입 overview

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

💡삽입 노드의 색

삽입하는 노드는 항상 RED이다.

삽입 예제

📌레드블랙 트리의 다섯가지 속성
1.모든 노드는 red 혹은 black
2.루트 노드는 black
3.모든 nil노드는 black
4.red의 자녀들은 반드시 black == red가 연속적으로 존재할 수 없다.
5.임의의 노드에서 자손 nii 노드들까지 가는 경로들의 black 수는 같다 (자기 자신은 카운트에서 제외)

📌insert(50)

노드를 삽입 할 때 두 nil 노드의 색은 black으로 고정한다. 그러면 자연스럽게 #3 속성을 만족
red-black 트리 #2 속성 위반, 루트 노드를 black으로 바꾸면 해결
#2속성 : 루트 노드는 black

red-black 트리의 모든 속성을 만족

📌insert(20)

red-black 트리의 모든 속성을 만족

💡왜 새로 삽입하는 노드는 RED인가?

삽입 후에도 #5속성을 만족하기 위해

✏️nil 노드를 표기하지 않아도 삽입되는 노드는 nil노드가 두 개 있고 nil노드는 black임을 기억하자!

📌insert(10)

red-black 트리 #4번 속성 위반
#4 : 노드가 red라면 자녀들은 black
어떻게 해결할수 있을까?
- red가 한쪽으로 몰려있으니 red하나를 반대편으로 옮겨준다면?

잊지 말아야 할 것은 구조를 바꿔준 뒤에 BST 특징 또한 유지되어야 한다.

구조를 바꾸면서도 BST의 특징을 유지시키는 방법은 회전이다.
#4 속성 위반을 해결하기 위해 red하나를 넘겨야하는데 BST특징 또한 유지하면서 넘기려면 회전을 사용해야한다. 회전을 어떻게 사용할지가 관건
#4 : 노드가 red라면 자녀들은 black

📌해결방법

20과 50의 색을 바꿔준다.
50을 기준으로 오른쪽으로 회전한다.

#4 속성을 포함해서 red-black 트리 속성들을 모두 만족

🖋정리

red 삽입 후 #4 속성을 위반했을때
#4 : 노드가 red라면 자녀들은 black

case3 해결하기

삽입된 red 노드가 부모의 왼쪽 자녀 & 부모도 red이고 할아버지 왼쪽 자녀 & 삼촌(=부모의 형제)은 black이라면
부모와 할아버지의 색을 바꾼 후 할아버지 기준으로 오른쪽으로 회전한다.

📌insert(40)

red-black 트리 #4번 속성 위반
#4 : 노드가 red라면 자녀들은 black
#4속성 위반을 해결하기 위해 red하나를 넘겨야 하는데 BST 특징 또한 유지하면서 넘기려면 회전을 사용해야 한다 회전을 어떻게 사용할지가 관건
case.3 와 다른 점은 삽입된 노드를 기준으로 할아버지의 경로가 꺾였다는 점이다.
꺾인 부분을 펴줘서 case.3과 같은 형태로 만들면 case.3과 같은 방식으로 해결가능

📌해결방법