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과 같은 방식으로 해결가능
📌해결방법
1. 20을 기준으로 왼쪽으로 회전한다. 회전 후에도 #4속성 외의 속성들을 만족하며 이제 case.3의 형태가 됐다.
2. 40과 50의 색을 바꾼다.
3. 50 기준으로 오른쪽 회전을 한다.
- #4속성을 포함해서 red-black 트리 속성들을 모두 만족
🖋정리
- red 삽입 후 #4 속성을 위반했을때
- #4 : 노드가 red라면 자녀들은 black
- 삽입된 red노드가 부모의 오른쪽 자녀&부모도 red이고 할아버지의 왼쪽 자녀&삼촌(=부모의 형제)은 black이라면 부모를 기준으로 왼쪽으로 회전한 뒤 case.3의 방식으로 해결
📌insert(30)
- Red-Black 트리 #4 속성 위반 red가 한 쪽으로 몰려있지 않아서 옮길 수가 없다.
- #4 : 노드가 red라면 자녀들은 black
- #5번과 관련 특징 : 자녀의 색이 둘다 같으면 부모와 자녀의 색을 바꿔줘도 5번 속성을 그대로 유지한다.
- #4를 만족시키면서 #5를 유지하려면 10과 50을 black으로 바꾸고 20을 red로 바꾸면 된다.
- 하지만 20이 루트 노드라서 #2 속성을 위반한다. 20을 black으로 바꿔준다.
- #2 : 루트노드는 black
- 최종적으로 red-black 트리 모든 속성을 만족한다.
🖋정리
- red 삽입 후 #4 속성을 위반했을때
- case.1 해결하기 삽입된 red 노드의 부모도 red & 삼촌(=부모의 형제)도 red라면 부모와 삼촌을 black으로 바꾸고 할아버지를 red로 바꾼뒤 할아버지에서 다시 확인을 시작한다.
red-black 트리 예제
📌insert(40)
- #4 속성을 위반한 case.1 상태, 부모와 삼촌을 black으로 할아버지는 red로 변경하자!
- #4 : 노드가 red 라면 자녀들은 black
- 할아버지인 50에서 확인 후 모든 속성을 만족하기 때문에 상황 종료
📌insert(35)
- #4 속성을 위반한 case.2 상태 40을 기준으로 오른쪽으로 회전해서 case.3의 형태로 만들자!
- #4 : 노드가 red라면 자녀들은 black
- #4 속성을 위반한 case.3의 상태! , 30과 35의 색을 바꾸고 30을 기준으로 회전하자
- #4 : 노드가 red라면 자녀들은 black
- red-black 트리 속성 모두 만족
📌insert(25)
- #4 속성을 위반한 case.1 상태
- 부모와 삼촌을 black으로, 할아버지는 red로 변경하자
- #4 : 노드가 red라면 자녀들은 black
- 할아버지인 35에서 확인해보니 #4속성을 위반한 case.2상태 !
- 50을 기준으로 오른쪽 회전해서 case.3의 형태를 만들자
- #4 : 노드가 red라면 자녀들은 black
- #4 속성을 위반한 case.3 상태이므로 20과 35의 색을 바꾸고 20을 기준으로 왼쪽으로 회전한다.
- 최종적으로 red-black 트리 속성 모두 만족
'SWjungle > #레드블랙트리' 카테고리의 다른 글
| [Red-Black 트리]삭제 - 구현 (3) | 2023.09.06 |
|---|---|
| [Red-Black 트리]삽입- 구현 (0) | 2023.09.05 |
| [Red-Black 트리]삭제 (0) | 2023.09.04 |
| [Red-Black 트리] 소개 (2) | 2023.09.03 |