24.11.19 CS

CS

RB Tree

특징

• 이진 탐색 트리의 한 종류로, 노드에 색상을 추가하여 균형을 유지하는 자기 균형 이진 탐색 트리이다.
• 레드-블랙 트리는 다음 5가지 성질을 만족해야 한다.
  1. 노드는 빨간색 또는 검은색이다.
  2. 루트는 항상 검은색이다.
  3. 모든 리프(Leaf, NIL노드)는 검은색이다.
     • 리프 노드는 데이터를 가지지 않는 NIL 노드로 표현한다.
  4. 빨간색 노드의 자식 노드는 모두 검은색이다.
     • 빨간색 노드는 연속해서 나타날 수 없다.
  5. 루트에서 각 리프 노드까지 가는 경로에는 항상 같은 개수의 검은색 노드가 있다.
     • 이 값을 Black Height라고 한다.

장점

1. 삽입/삭제/탐색이 항상 O(log n)으로 효율적이다.
2. 이진 탐색 트리의 단점인 편향된 트리를 방지한다.
3. 구현이 표준화되어 있고, 많은 라이브러리에서 사용된다.

단점

1. 구현이 복잡하다.
2. 특정 시나리오에서 AVL 트리보다 다소 느릴 수 있다.

AVL Tree

특징

• 이진 탐색 트리의 한 종류로, 높이 균형 조건을 유지하는 자기 균형 이진 탐색 트리중 하나이다.

1. 높이 균형 조건
   • 모든 노드에 대해 왼쪽 서브트리와 오른쪽 서브트리의 높이 차이(균형 인수)가 -1, 0, 1이어야 한다.
   • 균형 인수 = (왼쪽 서브트리 높이) - (오른쪽 서브트리 높이)
2. 자기 균형
   • 삽입 또는 삽제 시 균형이 깨질 경우. 회전을 통해 트리를 다시 균형 상태로 만든다.

장점

1. 탐색 성능이 뛰어나다.
   • 항상 더 엄격한 균형 조건을 유지하기 때문에 탐색 경로가 짧다.
   • 특히 읽기 중심 애플리케이션에서 성능이 우수하다.
2. 균형 유지
   • 높이 균형을 엄격하게 유지하므로 최악의 경우에도 O(log n)을 보장한다.
3. 데이터의 순서 보장
   • 키가 항상 정렬된 상태로 유지된다.

단점

1. 회전 연산의 비용
   • 삽입과 삭제 시 균형 복구를 위해 더 많은 회전 연산이 필요하다.
   • 따라서 삽입/삭제가 빈번한 경우 성능이 저하될 수 있다.
2. 구현의 복잡성
   • 레드-블랙 트리에 비해 구현이 더 복잡하다.
   • 더 많은 조건과 연산을 처리해야 하므로 코드 작성이 까다로울 수 있다.