RB-TREE란?
Red-black tree는 일종의 자기 균형 이진 탐색 트리(Self-Balancing BST)이다.
그냥 아무것도 모르고 본다면 그냥 빨간색, 검정색이 들어간 이진 탐색트리처럼 보인다.
rb-tree를 구현하기 전에 도대체 이건 왜 생겼을까 궁금해졌다.
그냥 심심해서 만들었을리는 없고 분명 단점을 극복하기 위해 나왔을 텐데,,,
그 단점은 무엇이며 어떻게 극복했을까?
RB-TREE는 왜 생겼을까?
RB-TREE가 자기 균형 이진 탐색 트리라고 했다.
tree 스스로가 계속 균형을 맞추나보다~ 라고 해석해 볼 수 있다.
그럼 이진 탐색 트리(BST)란 무엇일까? (rb-tree가 궁금했다면 이미 bst는 알고 있겠지만...)
자신의 왼쪽 서브트리에는 현재 노드보다 값이 작은 것, 오른쪽 서브트리에는 값이 큰것들만 들어간 tree다.
그렇기 때문에 이진 탐색 트리의 평균 조회 시간복잡도는 O(log n)이다.
하지만! 이진 탐색 트리의 균형이 무너질 경우 조회 시간복잡도는 O(N)까지 증가한다.
그럼 여기서 균형이 무너진다는 건 무슨 뜻일까?
이런 경우를 트리에서 균형이 무너졌다고 말한다.
이 상태에서 3을 찾아간다고 하면 이진탐색트리를 쓰는게 큰 의미가 없어진다. 그래서 나온게?!
균형 이진 탐색트리다.
그럼 어떻게 균형을 맞추는데?
이 다섯가지의 규칙을 지키면 균형이 맞춰진다.
- 모든 노드는 빨간색 혹은 검은색이다.
- 루트 노드는 검은색이다.
- 모든 리프 노드(NIL)들은 검은색이다. (NIL : null leaf, 자료를 갖지 않고 트리의 끝을 나타내는 노드)
- 빨간색 노드의 자식은 검은색이다. (빨간색 노드가 연속으로 나올 수 없다.)
- 모든 리프 노드에서 Black Depth는 같다. (리프노드에서 루트 노드까지 가는 경로에서 만나는 검은색 노드의 개수가 같다.)
생각보다 5가지 규칙을 지키는 것은 쉽지 않다... 특히 삭제 알고리즘을 생각할 때는 내 두뇌의 한계를 경험했다.
삽입 삭제를 짤로 보여준다면 이해가 쉬울 것 같아서 유용한 사이트 하나를 가져왔다!
https://www.cs.usfca.edu/~galles/visualization/RedBlack.html
이론을 공부하고 하나씩 넣어보고 삭제해보면 코드를 짤 때 더 유용할 수도...?
rb-tree 한 줄 요약
5가지 조건을 만족할 때까지 돌려라...
코드는 하단에 git hub 링크를 타고 들어오면 보인다. 주석을 정말 상세하게 달았다. 초등학생도 이해하기 쉬울 정도로... 하지만 바로 코드와 주석을 보기보다는 생각을 해보는 것을 추천한다. 생각안하고 보면 대학생도 이해하기 힘들다.
짱짱 girl인 내가 구현한 코드 보러가기 -> 제발 구경가줘... 내 일주일이 갈려 들어갔다구...!
