개념
- 삽입 전 RB트리 속성을 만족한 것을 전제로 한다.
- 삽입 방식은 일반적인 BST와 동일하다.
- 삽입하는 노드는 Red이다.
- 삽입 후 RB트리의 위반 여부를 확인하고, 위반했다면 재조정하여 다시 만족하도록 바꾼다.
삽입방식
전제조건
탐색대상의 부모가 Red인 경우, 계속 검사해준다.
case 1
- 탐색 대상의 부모와 삼촌이 Red인 경우
- 자동적으로 할아버지는 Black이 된다.(4번 규칙에 따라)
- 부모와 삼촌을 Black으로, 할아버지를 Red로 바꾼다.
- 탐색 대상을 할아버지로 바꾼다.
case2
- 탐색 대상의 부모만 Red인데 할아버지 ~ 부모 ~ 탐색대상이 일직선상에 놓이지 않은 경우
- 일직선상에 놓이도록 만들어준다.
- 탐색 대상을 부모로 바꾼다.
- 일직선상에 놓이도록 부모에서 회전을 시켜준다.
- 이후 case3에서 해결한다.
case3