[기술면접] RB Tree(Red-Black Tree)에 대한 질문 모음

1. RB Tree란 무엇인가요?

- RB tree는 데이터를 저장하거나 검색하기 위한 자료구조로, 이진 검색 트리입니다.

루트에서 리프까지의 경로에 나타나는 노드의 색깔을 제한함으로써, 트리의 균형을 근사적으로 유지합니다.

 

- BST의 삽입, 삭제 연산과정에서 발생할 수 있는 문제점을 해결하기 위해 만들어진 자료구조입니다.

 

- node 구조체의 parent, color, key 멤버들의 값을 확인하며 규칙을 지킴으로써 양쪽의 균형을 맞추게 됩니다. 회전하는 것도 연산이 들어가기 때문에 완전한 균형 알고리즘은 아닙니다. 

2. RB Tree의 작동 원리는 어떻게 되나요?

- RB 트리는 다음 다섯 가지 속성을 만족해야합니다.

1. 모든 노드는 빨간색, 검은색 둘 중 하나이다.
2. 루트 노드는 검은색이다.
3. 모든 리프(NIL)은 검은색이다.
4. 노드가 빨간색이면 그 노드의 자식은 모두 검은색이다. 
5. 각 노드로부터 그 노드의 자손인 리프로 가는 경로들은 모두 같은 수의 흑색 노드를 포함한다. 

3. RB Tree의 삽입 알고리즘은 어떻게 구현되나요?

1. BST(Binary Sear Tree: 이진 탐색 트리)의 특성을 유지하면서 노드를 삽입합니다.
2. 삽입된 노드를 빨간색으로 지정합니다. (Black-height를 최소화하기 위해서)
3. RBT의 특성을 위배했을 경우, 노드의 색깔을 조정합니다.
4. Black-Height가 위배되었을 경우, rotation을 통해 height를 조정합니다.

4. RB Tree의 삭제 알고리즘은 어떻게 구현되나요?

1. BST의 특성을 유지하면서 노드를 삭제합니다.
2. 삭제될 노드의 child의 개수에 따라 rotation 방법이 달라집니다.

5. RB Tree의 시간 복잡도는 어떻게 되나요?

- 탐색, 입력, 삭제에 O(logN)의 시간이 걸립니다. 

6. 다른 이진 탐색 트리 알고리즘들과 비교했을 때, 어떤 장점이 있나요?

- Worst Case에서도 O(logN)의 탐색 시간으로 탐색하기 위해서는 자가 균형 이진 트리가 필요합니다. 자가 균형 이진 트리의 종류는 대표적으로 레드블랙 트리, AVL 트리가 있습니다.

- AVL 트리는 레드블랙 트리보다 더 엄격하게 균형이 잡혀있기 때문에, 삽입과 삭제를 할 때 최악의 경우 더 많은 회전(rotation)을 필요로 합니다. 레드 블랙 트리는 실 사용에 효율적이고, 최악의 경우에도 우수한 실행 시간을 보입니다.  n개의 노드가 있을 때 O(logN)의 시간복잡도로 삽입, 삭제, 검색을 할 수 있는 장점이 있습니다. 

7. RB Tree가 사용되는 예시는 어떤 것이 있나요?

1. Java Collection API의 Map Interface 구현체인 HashMap의 Seperate Chaining 구현에서 사용한다.

: Key 값의 Collision이 발생할 경우 같은 Hash 값을 가지는 원소들을 Collection으로 관리하는데, 이 때 원소의 개수가 많아지면 RB Tree를 이용해서 관리하여 연산 시간을 O(logn)으로 관리한다.

 

⇒ 데이터의 개수가 일정 이상일 때에는 링크드 리스트 대신 트리를 사용하는 것이 성능상 이점이 있다.

⇒ 링크드 리스트를 사용할 것인가 트리를 사용할 것인가에 대한 기준은 하나의 해시 버킷에 할당된 키-값 쌍의 개수이다.

즉, 하나의 해시 버킷에 8개의 키-값 쌍이 모이면 링크드 리스트를 트리로 변경한다. 만약 해당 버킷에 있는 데이터를 삭제하여 개수가 6개에 이르면 다시 링크드 리스트로 변경한다. 트리는 링크드 리스트보다 메모리 사용량이 많고, 데이터의 개수가 적을 때 트리와 링크드 리스트의 Worst Case 수행시간 차이 비교가 의미가 없기 때문이다.

 

2. RB Tree는 Radix Tree와 더불어 Linux Kernel에서 가장 많이 사용하는 Tree 자료구조 입니다.

: 기존 Tree 자료구조의 단점은 최악의 경우 노드가 Linked-List의 형태로 저장되어 탐색 시간 복잡도가 O(N)이 된다는 점이다. RB Tree는 노드의 삽입과 삭제가 이루어질 때, Tree가 조건에 맞게 스스로 균형을 이루기 때문에 O(logN)의 시간복잡도를 보장한다.

 

3. Linux의 기본 스케줄러인 CFS 스케줄링 알고리즘에서 사용합니다.

: 테스크의 소요 시간 기준으로 프로세스를 관리하기 위해 RB Tree를 이용해서 스케줄링을 관리한다.

8. RB Tree를 사용할 때 주의해야 할 점은 무엇인가?

- RB Tree는 동적으로 메모리를 할당하고 해제해야하는 자료구조입니다.

따라서 RB Tree를 사용할 때는 메모리 누수가 발생하지 않게 하기 위해 메모리 할당/해제를 올바르게 해야합니다. 

 

 

+ 참고 : RBT 왜, 어디서 쓰는가?