RBT - 레드블랙트리

레드 블랙 트리란(RBT)?

이진탐색트리의 일종이다 트리의 높이를 제한해서
최악의 경우에도 탐색/삽입/삭제가 O(log n)이 되도록 만든 구조

핵심 속성

1. 노드는 빨간색 또는 검은색
2. 루트는 항상 검은색
3. 모든 리프는 검은색
4. 어떤 노드도 빨간색 자식을 둘 수 없다.
5. 어떤 노드에서 리프까지 가는 경로에는 같은 수의 검은색 노드가 있다.
   -> 흑색높이(black height)
   노드 8의 black height : 2
   노드 13의 black height : 2

[ 노드 x의 black height ]

• #5 속성: 임의의 노드에서 자손 nil 노드들까지 가는 경로들의 black 수는 같다. (자기 자신은 카운트에서 제외)
• 노드 x에서 임의의 자손 nil 노드까지 내려가는 경로에서의 black 수 (자기 자신은 카운트에서 제외)
• 위의 속성 중 5번을 만족해야 성립하는 개념이다.

✔️ Red-Black 트리는 어떻게 균형을 잡을까?

#4 속성: red의 자녀들은 반드시 black이어야 한다. (즉, red가 연속적으로 존재할 수 없다.)

#5 속성: 임의의 노드에서 자손 nil 노드들까지 가는 경로들의 black 수는 같다. (자기 자신은 카운트에서 제외)

삽입/삭제 시 주로 속성 #4, #5를 위반하며 이들을 해결하기 위해 구조를 바꾼다.

그러다 보면 자연스럽게 트리의 균형이 잡히게 된다.

이렇게 균형을 잡으며 편향되지 않는다.

삽입과 삭제

• 삽입할 땐 일반 BST처럼 넣은 뒤, 위 규칙 위반을 수정하면서 회전 + 색 바꿈을 한다.
• 삭제도 마찬가지로 규칙을 위반하지 않도록 여러 단계를 거쳐서 균형을 유지한다.

검색 : O(log n)
삽입 : O(log n)
삭제 : O(log n)

이진 탐색트리(BST)의 단점

균등 트리 : 노드 개수가 N개일 때 O(log n)
편향 트리 : 노드 개수가 N개일 때 O(N)

이진 탐색 트리는 최악의 경우 한쪽으로 편향된 트리일 때 O(N) 시간이 걸린다.

이 말은 모든 노드를 한 번씩 다 확인해줘야 한다는 의미이다.
이러한 단점을 개선한것이 RBT

AVL 트리와 비교했을 때!

삽입/삭제가 거의 없고 검색이 대부분인 상황에서는 AVL트리를 사용하고
삽입/삭제가 많을 때는 red-black tree를 사용하면 좋다.

왜냐하면 AVL트리는 검색 성능이 빠르고 red-black tree는 삽입/삭제 성능이 좋기 때문!

AVL트리는 균형을 좀 더 엄격하게 잡는다.
엄격하니깐 검색 성능은 더 좋지만 삽입/삭제는 red-black tree에 비해 느리다.