Chapter 10. Efficient Binary Search Trees (효율적 이원탐색 트리)

이미지는 전부 직접 제작한 것입니다. 퍼가실 때에는 반드시 출처를 명시해주세요.

1. Optimal Binary Search Trees (최적 이원 탐색 트리)

2. AVL Trees

1. AVL
   - Adelson-Velskii와 Landis가 서브트리들의 높이가 균형을 이루는 이진트리구조를 제안
   - 모든 노드의 왼쪽과 오른쪽 서브트리의 높이 차이가 1 이하인 이진 탐색 트리
   - 평균, 최선, 최악 시간 복잡도 :
    ⇒ 동적 검색, 삽입/삭제 : O(log(n)) 시간 안에 가능.
   - 균형 인수 (balance factor)
    : (왼쪽 서브트리의 높이 - 오른쪽 서브트리의 높이)   ...음수 가능
      → 양수 : 왼 > 오 ,   음수 : 왼 < 오
    : 노드 하나 짜리 트리는 높이 0
    : 빈 트리의 높이 -1
    : 모든 노드의 균형 인수는 -1, 0, +1 중 하나의 값을 가짐
    : insertion, deletion 시 균형이 깨진 트리 ( 균형 인수 범위가 벗어난 트리)는
      균형을 회복 시켜야 한다
   

   

2. Insertion 연산
   - 이진 탐색 트리와 동일
   - 삽입 연산과 삭제 연산 시 균형 상태가 깨질 수 있음
   - 균형 인수의 값이 -1, 0, 1이 아닐 경우 노드는 회전 실시
   - 삽입되는 위치에서 루트로의 경로에 있는 조상 노드들의 균형인수에 영향을 줄 수 있음
    > 불균형이 탐지된 가장 가까운 조상 노드의 균형인수를 1 이하로 재 균형 시켜야 함
   
   - 회전의 유형
      ㅁㅁ회전 == ㅁㅁ(타입을 위한) 회전
   (1) RR 타입 회전 : 불균형으로 판명된 노드(x)의 우측(R) 자식의 우측(R) 서브트리에 삽입
   (2) LL 타입 회전 : 불균형으로 판명된 노드(x)의 좌측(L) 자식의 좌측(L) 서브트리에 삽입
   (3) LR 타입 회전 : 불균형으로 판명된 노드(x)의 좌측(L) 자식의 우측(R) 서브트리에 삽입
   (4) RL 타입 회전 : 불균형으로 판명된 노드(x)의 우측(R) 자식의 좌측(L) 서브트리에 삽입
   
   (참고) RR, LL → 단일 회전 / LR, RL → 이중 회전
   
   - 균형
    > 삽입 위치에서 루트까지의 경로에 있는 조상 노드들의 균형 인수 영향
    > 삽입 후에 불균형 상태로 변한 가장 가까운 조상 노드 (균형인수가 2가 된 가장 가까운 조상 노드)의 서브 트리들에 대하여 다시 재균형
    > 삽입 노드로부터 균형 인수가 2가 된 가장 가까운 조상 노드까지 회전
   
   - AVL 트리의 균형이 깨지는 4가지 경우
    (삽입된 노드 N부터 가장 가까우면서 균형 인수가 2가 된 조상 노드가 A라면)
   
   (1) RR 타입 : N이 A의 우측(R) 자식의 우측(R) 서브트리에 삽입
   (2) LL 타입  : N이 A의 좌측(L) 자식의 좌측(L) 서브트리에 삽입
   (3) LR 타입 : N이 A의 좌측(L) 자식의 우측(R) 서브트리에 삽입
   (4) RL 타입 : N이 A의 우측(R) 자식의 좌측(L) 서브트리에 삽입
   
   
   ## AVL INSERTION AND ROTATION 참고 URL
   http://www.youtube.com/watch?v=4UfekZU9fZw
   
   - 각 타입별 재균형 방법
   (1) RR 회전 : A부터 N까지의 경로상 노드의 오른쪽 회전
   (2) LL 회전  : A부터 N까지의 경로상 노드의 왼쪽-오른쪽 회전
   (3) LR 회전 : A부터 N까지의 경로상 노드의 왼쪽 회전
   (4) RL 회전 : A부터 N까지의 경로상 노드의 오른쪽-왼쪽 회전
   

1. RR 회전
   

   

   
   
   
   

   

   
   
   # 알고리즘
   rotateRR(A)
     B = A 의 오른쪽 자식
     A의 오른쪽 자식 = B의 왼쪽 자식
     B의 왼쪽 자식 = A
     return B // 원래 B 자리에 A가 올라왔기 때문에 포인터를 리턴하여 위치 저장
   

2. LL 회전
   

   

   

   
   
   # 알고리즘
   rotateLL(A)
     B = A의 왼쪽자식
     A의 왼쪽 자식 = B의 오른쪽 자식
     B의 오른쪽 자식 = A
     return B
   

3. RL 회전
   - LL → RR
   

   

   
   
   
   # 알고리즘
   rotateRL(A)
    B = A의 오른쪽 자식
    A의 오른쪽 자식 = rotate RR(B)
    return rotateLL(A)
   

4. LR 회전
   - RR →  LL
   

   

   
   
   # 알고리즘
   rotateLR(A)
    B = A의 왼쪽 자식
    A의 왼쪽 자식 = rotateRR(B)
    return rotateLL(A)
   
   

5. 이중 회전 알고리즘
   ⇒ 한 level 올라가서 회전
   
   

   

   
   
   
   
   - 균형인수 구하기 ⇒ 자식들의 높이를 구해서 그 차이를 알아야 함
   -  *** 코드는 드라이브에 올리겠다능

3. Deletion 연산 (안나와있닷)
   

3. Red-Black Trees (2-3트리 및 2-3-4 트리 본 후에 보기)
   
   - 2-3-4 트리를 이진트리로 표현한 것
   - 레드-블랙 트리의 링크(Link)는 색깔을 지님 (옛날에 이랬음) ⇒ 오늘날은 노드가 색깔 지님
   - 포인터 변수에 색깔이라는 속성 추가
   - 노드 자료구조
    * 키를 포함한 데이터 필드,
    * LChild 포인터, RChild 포인터
    * LColor, RColor
    * 색깔 변수 하나만 사용하려면, 부모노드로부터 자신을 향한 포인터의 변수를 표시
   
   - 모든 2-3-4 트리는 레드-블랙트리로 표현가능
   - 2-노드는 그대로
   - 3-노드는 왼쪽 또는 오른쪽 키를 루트로 하는 이진트리로, 따라서 트리 모양이 유일하진 않음
   - 빨강 링크는 원래 3-노드, 4-노드에서 같은 노드에 속했었다는 사실을 나타냄.
   ⇒ insert/ delete 하기 쉬움

1. 4-노드의 레드 블랙 표현은 유일함
     *** 레드-블랙 트리의 속성
      (1) 트리를 내려오면서 연속적인 빨강 링크 2개는 허용하지 않음
      (2) 루트로부터 리프노드까지 검정 링크의 수는 모두 동일함
      (3) 2개의 자식 노드가 모두 빨강 링크일 때만 4-노드에 해당
      ** 모든 root와 leaf 노드는 BLACK
     [4-node]
      

   

   
   
   
   
   
   
   
   [3-node]
   

   

   
   
   [2-node]
   

   

   
   
   

2. 사용 이유
   - 2-3-4 트리의 복잡한 노드 구조 그리고 복잡한 삽입/삭제 코드
   - 레드 블랙 트리는 이진 탐색트리의 함수를 거의 그대로 사용
   - 2-3-4 트리의 장점인 단일 패스 삽입/삭제가 그대로 레드블랙 트리에도 적용
   - 언제 회전에 의해 균형을 잡아야 하는지가 쉽게 판별됨
   

3. Red-Black Tree Example
   

   

   
   
   

   

   

4. 레드 블랙트리의 4-노드 제거
   - 루트 노드가 4-노드인 경우
   - (a)의 2-3-4 트리를 레드블랙으로 표현한 것이 (a`)
   - 2-3-4 트리에서 4-노드를 제거하기 위해서는 (b)와 같이 중간 키를 루트로 하는 트리로 변형
   - (a’)의 레드 블랙 트리는 이미 (b)에 갖춰져 있음
   - 링크의 색깔만 빨강에서 검정으로 뒤집음 (Color Flip / 색깔반전)
   

5. 부모 노드가 2-노드인 경우에 4-노드인 자식 노드를 제거
   - 2-3-4 트리 (a)에서 4-노드를 제거하면 (b)가 됨
   - (a)를 나타내는 레드 블랙트리는 (a’)
   - (a’)에서 4-노드를 제거하는 과정은 키 x를 중심으로 부모와 자식의 링크 색상을 반전
   - X-Z 간의 링크를 검정에서 빨강으로, 그리고 X-W, X-Y 간의 링크를 빨강에서 검정으로 바꾸면 (b’)가 됨
   - 만약 (b’)의 루트를 중심으로 오른쪽으로 회전(LL Rotation)시켜도 동일한 2-3-4 트리를 나타냄
   

6. 부모노드가 3-노드인 경우에 4-노드인 자식노드를 제거
   - 4-노드인 w를 중심으로 부모와 자식 링크에 대해 색상을 반전
   - z-y-w로 이어지는 빨강 링크가 연속으로 2개
   - 연속적인 2개의 빨강 링크를 허용하지 않으므로 이를 피하기 위해 회전(RR Rotation)을 가함
   

7. 레드-블랙 트리의 구성 예
   - 왼쪽 칼럼이 레드블랙 트리, 오른쪽 칼럼은 상응하는 2-3-4 트리
   - 키 20이 들어올 때 루트는 아직 4-노드 상태가 아니므로 빨강 링크로 삽입
   - 키 30이 삽입되면 2개의 빨강 링크가 연속되므로 회전
   - 결과 키 20을 루트로 하는 트리가 좌우에 빨강 링크이므로 4노드임이 표시됨
   - 키 40이 루트로 들어오는 순간 루트가 4-노드이므로 색상 반전에 의해 이를 제거한 뒤에 삽입
   - 키 50이 삽입될 때 두개의 연속된 빨간 링크이므로 회전에 의해서 변형
   - 키 60이 삽입되어 내려올 때, 4-노드인 40의 부모와 자식의 링크 색상이 반전
   

   

   
   
   

   

   
   
   
   

4. Splay Trees

이미지는 전부 직접 제작한 것입니다. 퍼가실 때에는 반드시 출처를 명시해주세요.