[트리] 균형 검색 트리 (AVL트리, 레드-블랙트리, B-트리)

• 균형 이진 검색 트리
  • 최악의 경우에도 이진 트리의 균형이 잘 맞도록 유지해서 작업들이 항상 O(logn)시간을 보장함

 

AVL 트리

• 자가 균형, 높이 균형
  • 어떤 노드도 좌서브 트리와 우서브 트리의 높이 차가 1보다 크지 않은 상태로 유지되는 이진 검색 트리
• 회전 연산
  • 균형이 깨진 서브 트리 중 가장 낮은 곳에 있는 것부터 수선을 시작함
  • 단일회전, 이중회전

AVL트리 운영

• 삽입과 삭제
  • 새로운 노드를 삽입하거나 노드를 삭제할 때, AVL 트리는 불균형도를 체크하고 필요에 따라 회전을 수행하여 균형을 재조정
• 불균형도 체크
  • 각 노드는 자신의 왼쪽과 오른쪽 자식 트리의 높이를 기반으로 불균형도를 계산. 불균형도가 1을 초과하면 균형이 깨진 것으로 간주
• 회전 유형
  • 균형이 깨진 경우, LL, RR, LR, RL 네 가지 유형의 불균형 상황에 따라 적절한 회전을 적용

 

 

 

레드-블랙 트리

• 레드와 블랙 두 색을 사용해서 균형을 맞춤
• 자식이 없으면 해당 링크를 null값으로 두고, 이  null 각각을 리프 노드로 간주함
• RB특성
  • 루트는 블랙
  • 모든 리프 노드는 블랙
  • 레드 노드 2개가 연속으로 출연할 수 없음
  • 루트 노드에서 임의의 리프 노드에 이르는 경로에서 만나는 블랙 노드의 수는 값음
  • 레드-블랙 트리의 수는 모두 같음

레드-블랙 트리의 운영

• 삽입과 삭제
  • 새로운 노드를 삽입하거나 노드를 삭제할 때, 레드-블랙 트리는 색상 규칙을 유지하기 위해 트리를 재조정(이 과정에서 색상 변경과 회전이 일어날 수 있음)
• 회전 연산
  • 트리의 균형을 유지하기 위해 단일 회전(Single Rotation)과 이중 회전(Double Rotation)을 사용
• 색상 변경
  • 삽입이나 삭제 과정에서 노드의 색상을 변경하여 트리의 균형을 재조정

 

AVL트리와 RB트리의 균형 조정 메커니즘 차이

AVL 트리
균형 재조정: 회전(단일, 이중)을 사용하여 높이 균형 유지

레드-블랙 트리
균형 재조정: 색상 변경과 회전을 통해 균형 유지

 

 

 

B-트리

• 데이터베이스 및 파일 시스템과 같이 대규모 데이터를 저장하고 관리하는 데 효율적인 균형 이진 탐색 트리의 일종
• 멀티-웨이 트리
  • B-트리는 이진이 아닌 멀티-웨이(다중 경로) 트리
  • 각 노드는 여러 개의 자식을 가질 수 있으며, 이는 트리의 깊이를 줄이는 데 도움을 줌
• 균형 유지
  • 모든 리프 노드는 같은 레벨에 있음
• 노드 내 데이터 정렬
  • 각 노드는 키(key)의 배열로 구성되며, 이 키들은 정렬된 순서로 유지됨
• 데이터 액세스 최적화
  • B-트리는 디스크 입출력과 같은 비용이 높은 작업의 수를 최소화하도록 설계되었음

B-트리의 운영

• 노드 구조
  • 각 노드는 여러 개의 키를 포함하고, 각 키 사이에 자식 노드에 대한 포인터를 가짐
• 삽입과 삭제
  • 삽입 또는 삭제 시에 트리는 자동으로 재구성되어 균형을 유지함.
  • 종종 노드의 분할(splitting) 또는 병합(merging)을 포함함
• 오버플로우와 언더플로우 처리
  • 노드에 너무 많은 키가 삽입되어 오버플로우가 발생하면, 노드는 두 개의 노드로 분할됨
  • 반대로 너무 적은 키로 인해 언더플로우가 발생하면, 노드는 인접한 노드와 병합될 수 있음

 

 

 

 

AVL 트리
균형 조건: 노드의 왼쪽과 오른쪽 자식 간 높이 차이 최대 1.
균형 재조정: 회전(단일, 이중)을 사용하여 높이 균형 유지.
적용: 탐색 중심, 메모리 내 데이터에 적합.

레드-블랙 트리
균형 조건: 특정 색상 규칙에 따라 노드 색상 관리.
균형 재조정: 색상 변경과 회전을 통해 균형 유지.
적용: 삽입, 삭제가 빈번한 시나리오에 적합.

B-트리
균형 조건: 각 노드가 여러 키를 가질 수 있으며, 모든 리프 노드는 같은 레벨에 위치.
균형 재조정: 노드 분할 및 병합을 통한 균형 유지.
적용: 대규모, 디스크 기반 데이터셋에 최적화.

 

 

 

참고자료 : 「쉽게 배우는 자료구조 with 자바」