크래프톤 정글 week04, day27 - RB트리 개념

레드-블랙 트리(Red-Black Tree)

• 자가 균형 이진 탐색 트리(Self Balance Binary Search Tree)
• RB트리를 만족하기 위한 조건
  1. 모든 노드는 빨간색 혹은 검은색이다.
  2. 루트 노드는 검은색이다.
  3. 모든 리프 노드(NIL)들은 검은색이다.
     1. (NIL : null leaf, 자료를 갖지 않고 트리의 끝을 나타내는 노드)
  4. 빨간색 노드의 자식은 검은색이다.
     1. 빨간색 노드가 연속으로 나올 수 없다.
  5. 모든 리프 노드에서 Black Depth는 같다
     1. 리프 노드에서 루트 노드까지 가는 경로에서 만나는 검은색 노드의 개수가 같다.

• 조건 5번 속성을 만족해야 성립하는 개념
  • 노드 x의 black height
    • 노드 x에서 임의의 자손 nil 노드까지 내려가는 경로에서의 black 수(자기 자신은 카운트에서 제외)
  • 색을 바꾸면서도 5번 속성을 유지하기
    • RB트리가 5번 속성을 만족하고 있고 두 자녀가 같은 색을 가질 때, 부모와 두 자녀의 색을 바꿔줘도 5번 속성은 여전히 만족한다.

• RB트리는 어떻게 균형을 잡는가?
  • 삽입, 삭제 시 주로 4번, 5번을 위반하며 이들을 해결하려고 구조를 바꾸다 보면 자연스럽게 트리의 균형이 잡히게 된다.

• Successor(후임자)
  • 어떤 노드의 Successor는 해당 노드보다 큰 값 중에서 가장 작은 노드를 가리킨다. 다시 말해, 노드의 오른쪽 하위 트리에서 가장 작은 값을 가진 노드가 바로 Successor가 된다.
  • 만약 오른쪽 하위 트리가 없으면, 해당 노드부터 시작해 위로 올라가면서 처음으로 왼쪽 자식으로 연결되는 부모 노드가 Successor가 된다.

• Predecessor(선임자)
  • 어떤 노드의 predecessor는 해당 노드보다 작은 값 중에서 가장 큰 노드를 의미한다. 따라서, 노드의 왼쪽 하위 트리에서 가장 큰 값을 가진 노드가 predecessor가 된다.
  • 만약 왼쪽 하위 트리가 없다면, 해당 노드부터 시작해 위로 올라가면서 처음으로 오른쪽 자식으로 연결되는 부모 노드가 predecessor가 된다.

​

• 시간 복잡도(N = 트리의 노드 수)
  • insert(삽입)
    • 평균 : O(logN), 최악 : O(logN)
  • delete(삭제)  
    
    • 평균 : O(logN), 최악 : O(logN)
  • search(탐색) 
    • 평균 : O(logN), 최악 : O(logN)

 

• RB트리와 AVL 트리의 비교

	Red-Black 트리	AVL 트리
이진 탐색 트리	Yes	Yes
삽입/삭제/검색 시간복잡도	최악의 상황에도 O(logN)	최악의 상황에도 O(logN)
삽입/삭제 성능	AVL트리에 비해 빠르다	RB트리에 비해 느리다
검색 성능	AVL트리에 비해 느리다	RB트리에 비해 빠르다
균형 잡는 방식	RB트리 속성을 만족시키도록	balance factor ∈ {-1, 0, 1}이 되도록
응용 사례	리눅스 커널 내부에서 사용, java TreeMap 구현, c++ std::map 구현	dictionary, 한번 만들어놓으면 삽입/삭제가 거의 없고 검색이 대부분인 상황에 사용

 

 

학습 시간 : 10 ~ 26시