red-black-tree의 개념, 값 삽입

Red-Black-Tree!!

얘는 일종의 자기 균형 이진탐색 트리이다.

이진탐색트리란 자신의 왼쪽 서브 트리에는 현재 노드보다 작은 것, 오른쪽 서브 트리에는 큰 것만을 가질 수 있다.

이 덕분에 이진탐색트리에서는 조회를 할 때에 O(log n)의 시간 복잡도를 갖는다.

그런데 만약

요런 식으로 조회하면 O(n)의 시간 복잡도를 갖는다.

Red-Black-Tree 알고리즘은 이런 문제를 해결하기 위해 도입되었다.

트리의 속성

• 모든 노드는 Red 혹은 Black이다.
• root node는 Black!!!
• 모든 nil노드는 Black!!!
  • nil노드?
    • go언어에서 null을 nil로 써넣는데
    • 존재하지 않음을 의미하는 노드이다.
    • 자녀가 없을 때에 자녀를 nil노드로 표기
    • 이 nil노드는 값이 있는 노드와 동등하게 취급된다.
    • Red-Black-Tree에서 leaf노드는 nil노드
    • 
      • 여기서 저 숫자 없는 칭구들이 nil노드이다.
• red의 자녀들은 반드시 black이다.
  • 즉, red가 연속적으로 존재할 수 없다.
• 임의의 노드에서 자손 nil노드들까지 가는 경로들의 black수는 같다.
  • 자기 자신은 카운트에서 제외된다.
  • 여기서 나오는 개념이 black height이다.
    • 노드 x에서 임의의 자손 nil노드까지 내려가는 경로에서의 black수

저 black height에서 알 수 있는 것으로는

부모의 자녀의 색을 바꾸어 줘도 자손 nil노드로 가는 경로들의 black수는 같다는 것을 알 수 있다.

당연한 것인데, 여기서 중요한 것은 바꾼 다음에 바꾸기 이전과 black height가 같다는 것은 아니다.

이를 통해

Red-Black-Tree가 균형을 잡는 방법

새로운 노드의 삽입/삭제 시에 위의 특징을 지키기 위해서 알아서 막 쭈루루루루룩 바뀌고, 이를 통해 트리의 균형이 잡히게 된다.

Red-Black의 삽입 방식

1. 삽입 전 RB트리 속성 만족되어 있는 상태
2. 섭입 방식은 이진탐색트리와 같다.
3. 삽입 후에 이전의 특성들에 대한 위반 여부 확인
4. 위반 시 조정 진행

요렇게 삽입한다.

예시

insert(50)

노드를 삽입할 때에 두 nil노드의 색은 black으로 고정한다.
이렇게 되면 자연스럽게 모든 nil노드는 black이 만족된다.

참고로 처음에 삽입할때는 red를 넣어준다.
-> 이렇게 하면 임의의 노드에서 자손 nil노드들까지 가는 경로들의 black수가 항상 같기 때문이다.

변경

지금 위의 사진에서 root노드가 50인데, 이는 모든 root노드는 black 속성을 위반하였다.

이렇게 하면 모든 속성이 만족된다.

insert(20)

20을 삽입하는데, 20은 50보다 작다.
그러니까 왼쪽으로 빠져서 삽입되게 된다.

이렇게 하면 모든 속성이 만족된다.

insert(10)

10을 삽입하는데, 10은 20보다 작다.
그러니까 왼쪽으로 빠져서 삽입되게 된다.

변경

근데 위를 보면 red가 연속으로 나온다.
이거를 해결하려면 red하나를 반대편으로 옮겨주도록 한다.

요런 식으로 옮겨주는 것이다.
근데 이제 Red-Black-Tree도 이진탐색트리의 특성을 갖는다.

즉, 왼쪽은 자신보다 작고, 오른쪽은 자신보다 큰 특성을 만족해야 한다는 것이다.

그러니까 10, 20, 50은 이제

이런 식으로 바꾸어 준다.

이런 방식을 회전이라고 한다.

이제 회전 방법을 선택해 주자

1. 20과 50의 색을 바꾼다.
2. 50을 기준으로 오른쪽으로 회전한다.
   3. 그러면 50은 내려오고 20은 올라오게 된다.

이렇게 하면 모든 속성이 만족된다.

insert(40)

이제 여기서 40을 넣어주자

요렇게 40이 추가되는데, 이는 또 red밑에 black이 있어야 해서 속성이 위반되었다.

이 또한 회전을 통해 해결한다.
참고로

여기서는 노드가 한번 꺾였는데 50 - 20 - 40 요렇게 돼있다.

요렇게 만들어주기 위해서는

먼저 20을 기준으로 왼쪽으로 회전한다.

요렇게

이렇게 하면 이제 다시 바꾸면 된다.

1. 40과 50의 색을 변경
2. 50기준으로 오른쪽으로 회전

완성!!

이렇게 하면 모든 속성이 만족된다.

insert(30)

여기다가 이제 30을 넣어주자

그럼 이렇게 되는데 이거는 red가 한쪽으로 몰려있지도 않아서 옮기기가 힘들다.

이걸 해결하기 위해 "10, 50을 black으로 바꾸고 20을 red로 일단 바꾼다"

1. 10, 50을 black, 20을 red로 변경
2. 
3. 근데 이렇게 되면 root node가 red가 된다.
4. 20을 다시 black으로 변경한다.

이렇게 하면 모든 속성이 만족된다.