[CS - 자료구조] 이진 탐색 트리 (BST, Binary Search Tree), Red-Black Tree

이진 탐색 트리 (Binary Search Tree)

• 배경
  • 이진 트리에서 데이터를 효과적으로 찾는 방법을 고민함
  • 데이터를 효과적으로 찾기 위해 데이터를 효과적으로 저장하는 것이 더욱 효율적이다는 아이디어를 고안해냄

 

• 개념
  • 이진 트리 기반의 데이터 탐색을 위한 자료구조 (이진 트리 + 데이터 저장 규칙)
  • 데이터 저장과 동시에 정렬을 하는 자료구조
  • 이진 트리의 효율적인 탐색 능력을 가지며, 삽입과 삭제 가능

 

• 조건
  • 왼쪽 자식 노드 < 부모 노드 < 오른쪽 자식 노드
  • 모든 노드에서 위의 조건을 충족
  • 모든 노드는 유일한 키를 가짐 (노드 중복값 없음)

 

• operation 시간복잡도 (검색, 저장, 삭제 등)
  • O(logn)
  • worst case : 편향 트리 (skewed tree) → 한쪽으로만 노드가 추가되는 것
    • 이때의 시간복잡도 : O(n)
    • → Linked-List와 다를 게 없어짐
    • → 배열보다 많은 메모리를 차지하고, 시간복잡도도 갖게 되었음 : 비효율적
    • → 해결 방법 : Rebalancing (균형을 잡기 위한 트리 구조의 재조정) 중 Red-Black Tree

 

Red-Black Tree

• 개념
  • BST의 편향 트리를 방지하기 위한 자가 균형 이진 탐색 트리
  • BST의 길이가 n이 되지 않고, logn이 되도록 하는 방법
  • Red-Black Tree는 밑의 조건들을 만족하는 BST이다

 

• 조건
  • 모든 Node의 색은 검정 & 빨강
  • 루트 Node는 무조건 검정
  • 리프 Node는 무조건 검정
  • 빨강 Node의 자식 Node는 무조건 검정 Node
  • 모든 경로의 길이 (루트 Node → 리프 Node) 에서 검정 Node의 수는 동일하다
    • → 이게 BST의 길이를 logn으로 제한하는 핵심 조건

 

• 특징
  • Binary Search Tree 이므로 BST 의 특징을 모두 갖는다
  • 모든 leaf 노드는 nil 값의 검정 Node로 채워져있다
  • 삽입 Node는 무조건 빨강
  • Root node 부터 leaf node 까지의 모든 경로 중 최소 경로와 최대 경로의 크기 비율은 2 보다 크지 않다. 이러한 상태를 balanced 상태라고 한다.

 

• Red-Black Tree의 삽입 과정
  • 빨강 Node로 대소 관계에 맞는 적절한 위치에 삽입된다
  • 만약 부모 Node가 검정 → 정상적으로 삽입 완료
  • 만약 부모 Node가 빨강 → double red 발생 (빨강 Node의 자식 Node는 무조건 검정 Node여야 한다는 조건 위반)
    • 상황에 따른 두 가지 해결 방법 : Restructuring & Recoloring
  • i) 삼촌 Node가 검정 : Restructuring
    • 삽입 Node, 부모 Node, 조상 Node를 오름 차순으로 정렬
    • 이때 BST의 조건에 맞게
    • 중간 크기 → 새로운 부모 Node
    • 최소 → 새로운 왼쪽 자식 Node
    • 최대 → 새로운 오른쪽 자식 Node 로 재배치
    • 새로운 부모 Node는 빨강, 새로운 자식 Node들은 검정으로 색깔 변경
  • ii) 삼촌 Node가 빨강 : Recoloring
    • 색깔 변경
    • 검정 조상 Node → 빨강 조상 Node
    • 빨강 부모 Node, 삼촌 Node → 검정 부모 Node, 삼촌 Node
    • 조상 Node에서 double red 발생했는지 확인 후 계속 Recoloring & Restructuring 반복

• •