Red-Black 트리

Red-Black 트리

Red-Black 트리 개념

• 이진 탐색 트리(BST)의 한 종류
  • 이진 트리는 모든 노드가 가지는 자식 노드를 최대 2개 가지는 형태다.
  • 이진 탐색 트리는 이진 트리의 모든 노드가 왼쪽 서브 트리는 자기보다 작은 값이, 오른쪽 서브 트리에는 큰 값이 배치되는 특징이 있다.
• 스스로 균형(balancing)을 잡는 트리
• 스스로 균형을 잡음으로서 이진 탐색 트리의 worst case의 단점을 개선할 수 있다.
  • 이진 탐색 트리는 시간복잡도가 O(log N)이지만 worst case인 경우에는 O(N)의 시간이 걸린다.
  • 즉, Red-Black 트리는 worst case인 경우에도 O(log N)의 시간복잡도를 갖는다.
• 모든 노드는 Red 혹은 Black을 갖는다.

Red-Black 트리 속성

• 모든 노드는 Red 혹은 Black 을 갖는다.
• 루트 노드는 Black 을 갖는다.
• 모든 nil 노드는 Black이다 (nil 노드라는 것을 구분하기 위해 회색의 작은 원으로 그렸다.)
• Red 노드의 자식 노드들은 모두 Black 이거나 Red 노드가 연속적으로 존재할 수 없다.
• 임의의 노드 x에서 x의 자식인 nil 노드들까지 가는 경로들의 Black의 수는 모두 같다. (임의의 노드 x는 카운트에서 제외한다.)
  • 예를 들어, 임의의 노드 20의 자식인 nil 노드들까지 가는 경로의 총 수는 5가지이다. 각 5가지는 각각 Black의 수가 모두 2개인 것을 확인할 수 있다.

nil 노드란

• 존재하지 않음을 의미하는 노드
• 자식 노드가 없을 때 자식 노드를 nil 노드로 표기한다.
• nil 노드는 존재하지 않음을 의미하지만 값이 있는 노드와 동등하게 취급한다.
  • 프로그래밍 언어에서 null과 비슷한 의미인 것 같다.

또 한 가지 특징

노드 x의 Black Height

• 노드 x에서 임의의 자식 nil 노드까지 내려가는 경로에서의 Black 수가 Black Height가 된다. (자기 자신 x는 카운트에서 제외)
  • 예를 들어 노드 50에서 임의의 자식 nil 노드 하나를 선택해서 해당 nil 노드까지 Black의 총 수를 구하면 된다. (2가 나온다.)

색을 바꾸면서도 임의의 노드 x에서 x의 자식인 nil 노드들까지 가는 경로들의 Black의 수는 모두 같다.는 특징이 유지한다.

Red-Black 트리가 임의의 노드 x에서 x의 자식인 nil 노드들까지 가는 경로들의 Black의 수는 모두 같다.는 특징을 만족하고 있고, 두 자식 노드가 같은 색을 가질 때 부모와 두 자식 노드의 색을 바꿔줘도 이 특징은 여전히 만족한다.

Red-Black 트리 삽입

1. 삽입할 때 노드는 Red다. 10을 삽입한다.
2. 20과 50의 색을 바꿔준다.
3. 50을 기준으로 오른쪽으로 회전한다.

여기서 중요한 점은 스스로 균형을 잡음으로서 이진 탐색 트리의 특징을 유지할 수 있게 되는 것이다.

Red-Black 트리 삭제

삭제되는 색이 Red

• 삭제되는 색이 Red라면 어떠한 속성을 위반하지 않는다.

삭제되는 색이 Black

1. Delete(15) 수행: 삭제되는 색은 Black이며, 15의 위치를 대체할 nil node에 extra black을 부여한다.
2. 삭제된 노드의 왼쪽 형제도 Black이고 그 왼쪽 형제의 자식 노드가 Red여서 5를 부모의 색인 Red로 바꾸고, 5의 부모인 10과 5의 왼쪽 자식인 2는 Black으로 바꾼다.
3. 10을 기준으로 오른쪽으로 회전한다. 끝

Red-Black 트리 VS AVL 트리

• 삽입/삭제의 경우 Red-Black 트리가 더 빠르다.
  • AVL 트리는 루트 노드까지 balance factor를 계산해서 조건에 맞지 않으면 구조를 바꾼다. 그만큼 AVL 트리는 균형을 엄격하게 잡기 때문에 시간이 더 걸린다.
• 검색 성능은 AVL 트리가 조금 더 빠르다.
  • AVL 트리는 균형을 엄격하게 잡고, 균형이 잘 잡혀있다는 뜻은 그만큼 검색 속도도 증간한다.
• 균형 잡는 방식
  • Red-Black 트리: Red-Black 트리 속성을 만족시키도록 한다.
  • AVL 트리: balance facotr의 값이 {-1, 0, 1} 범주안에 포함되어야 한다.'
• 응용 사례
  • Red-Black 트리: Linux Kernel 내부에서 사용, Java TreeMap 구현, C++ std:map 구현
  • AVL 트리: Dictionary(사전), 한번 만들어 놓으면 삽입/삭제가 거의 없고 검색이 대부분인 상황에서 사용

내용이 많이 부실할 수 있지만 쉬운코드님의 영상을 보면서 레드블랙트리의 동작 방식과 특징들을 이해할 수 있었다. 자세한 동작 방식은 당연히 영상을 무조건 보는 것을 추천한다.

References

• 쉬운코드 - 레드블랙트리