12강 제 6장 탐색 알고리즘 (흑적트리, B 트리 )

6.4.2 흑적 트리

 

균형 탐색 트리. 이진 탐색 트리

 

(성질1) 모든 노드는 흑색이거나 적색이다. 

 

(성질2) 루트 노드와 리프 노드는 흑색이다.

  • 모든 리프 노드는 Null노드이다. 

 

(성질3) 적색 노드의 부모 노드는 항상 흑색이다. 

  • 적색 노드가 연달아 나타날 수 없다. 

 

(성질4) 임의의 노드로부터 리프 노드까지의 

경로 상에는 동일한 개수의 흑색 노드가 존재한다.

 

(1) 탐색 연산

> 이진 탐색 트리에서의 탐색 방법과 동일

 

(2) 삽입 연산 

> 적색 노드가 연달아 나타나는 경우에 적용하는 규칙

(규칙1) 부모 노드의 형제 노드가 적색인 경우

   ⇒ 부모 노드,부모 노드의 형제 노드,부모 노드의 부모 노드의 색깔을 모두 변경 

 

(규칙2) 부모 노드의 형제 노드가 흑색이고, 현재 노드의 키값이 부모 노드와 부모 노드의 부모 노드의 키값의 사이인 경우인 경우 ⇒ 현재 노드와 부모 노드를 회전시킴

 

(규칙3) 부모 노드의 형제 노드가 흑색이고,현재 노드의 키값보다 부모 노드와 부모 노드의 부모 노드의 키값이 

큰 ( 또는 작은 ) 경우 ⇒ 부모 노드와 부모 노드의 부모 노드를 회전시키고 색깔을 변경

 

(3) 성능 분석

> 탐색 시간 → O(logn)

  - 모든 리프 노드의 깊이가 두 배 이상 차이 나지 않으므로 

   최악의 트리의 높이는 O(logn)

> 삽입/삭제 시간 → O(logn)

 

(4) 특징 

> 사실상 이진 탐색 트리

  - 탐색 연산은 이진 탐색 트리와 동일

  - 삽입 연산은 회전,색깔 변경과 같은 추가 연산이 필요

> 2-3-4트리를 이진 탐색 트리로 표현한 것

 

 

6.4.3. B 트리

균형 탐색 트리

(성질1) 루트 노드는 한 개 이상 2t개 미만의 오름차순으로 정렬된 키를 가짐 균형 탐색 트리 

 

(성질2) 루트 노드가 아닌 모든 노드는 (t-1)개 이상 2t개 미만의 오름차순으로 정렬된 키를 가짐 

 

(성질3) 내부 노드는 자신이 가진 키의 개수보다 하나 더 많은 자식 노드를 가짐 

 

(성질4) 한 노드의 한 키의 왼쪽 서브트리에 있는

모든 키값은 그 키값보다 작고,오른쪽 서브트리에

있는 모든 키값은 그 키값보다 크다. 

 

(성질5) 모든 리프 노드의 레벨은 동일

 

 

(1) 삽입연산 

 

> 루트 노드에서부터 탐색을 수행하여 리프 노드에도 

   존재하지 않으면 해당 노드에 추가

 

> 노드 분할 

  - 삽입을 위한 탐색 과정에서 (2t-1)개의 키를 갖는 노드를 만나면, 

    이 노드를 (t-1)개의 키를 갖는 두 개의 노드로 분할

  - 삽입으로 인해 노드의 키의 개수가 2t개가 되는 것을 방지 

 

 

 

(2) 성능 분석

> 탐색,삽입,삭제 시간 복잡도

  -  트리의 높이 h,각 노드에서 키의 위치를 찾는 시간 O(t)→ O( t h) 

    -  각 노드에서는 (t-1)~(2t-1)개의 키와 t~2t개의 자식 노드를 가짐

    - 모든 리프 노드의 레벨은 동일

  - 트리의 높이 h→  O(logt n) (n:키의 개수 )

  - 각 노드에서의 키 관리에 흑적 트리를 이용하면 O(t)→ O(log t )

(3) 특징 

> 내부 탐색과 외부 탐색에 모두 활용

 - 내부 탐색의 경우, t=2또는 3으로 지정 

   -  t=2이면 2-3-4트리

 -  외부 탐색의 경우,t를 충분히 크게 지정

   - 한 노드의 크기가 디스크 한 블록에 저장되도록

 

2020/05/07 - [방송통신대학/알고리즘] - 11강 제 6장 탐색 알고리즘(탐색, 순차 탐색, 이진 탐색)

불러오는 중입니다...