[자료구조] 균형 탐색 트리 (AVL)

1) 균형 탐색 트리(AVL)

• 균형을 잡기 위해 트리 모습을 수정
• 탐색 효율 O(lgN)을 보장
• 삽입, 삭제 될 때마다 균형 파괴여부 검사하는 시간이 필요
• 트리를 재구성(Rebuilding)하는 시간이 필요

균형 인수(Balance Factor)

• 트리의 균형을 점검할 때 사용하는 인수
• 노드 마다 오른쪽 서브 트리의 높이에서 왼쪽 서브 트리의 높이를 뺀 것
• AVL 트리에서 균형 인수의 값은 반드시 -1, 0, +1 중 하나임

AVL의 회전

• 회전(Rotation)에 의한 균형 회복
• 불균형 노드의 위치를 기준으로 분류
  • LL : 불균형 노드의 왼쪽 서브 트리의 왼쪽 서브 트리의 높이 증가
  • RR : 불균형 노드의 왼쪽 서브 트리의 오른쪽 서브 트리의 높이 증가
  • RL : 불균형 노드의 오른쪽 서브 트리의 왼쪽 서브 트리의 높이 증가
  • RR : 불균형 노드의 오른쪽 서브 트리의 오른쪽 서브 트리의 높이 증가

2) 자체 조정 트리(Self-Restructuring Tree)

• 모든 노드가 동일한 빈도(Frequency)로 탐색되는 것이 아님
• 무조건 균형을 유지할 것이 아니라 자주 탐색되는 노드를 루트 근처에 갖다 놓는 것이 더욱 유리

조정 방법 1

• 어떤 노드가 탐색될 때마다 그 노드를 바로 위 부모 노드로 올리는 방법
• 한번의 회전만으로 충분함

조정 방법 2

• 어떤 노드가 탐색되면 그 노드를 아예 전체 트리의 루트로 올리는 방법
• 한번 탐색된 노드는 이후에 탐색될 가능성이 높다고 간주
• 연속적인 회전이 필요

• 한계점
  • 트리의 균형 면에서 불리
  • 노드 1의 탐색 결과 트리의 높이가 줄지 않고, 그대로 유지됨

3) 스플레이(Splay) 기법

• 조정 방법 2를 개선하여 탐색된 노드를 루트로 올리되, 한번에 두 레벨씩 위로 올리는 방법
• LChild, RChild 링크가 벌어져서(Splay) 활용됨으로 인해 균형에 유리
• 트리의 균형보다는 노드 자체의 탐색 빈도를 기준으로 함
• 어떤 노드가 상대적으로 다른 노드 보다 자주 사용된다면 유리한 구조
• 모두 동일한 빈도로 사용된다면 여전히 트리의 균형이 중요

지그지그(Zig-Zig)

• Left-Left 또는 Right-Right
• 두 레벨을 올리기 위해서 올려질 노드의 부모 노드를 먼저 회전시키고, 노드 3은 나중에 회전시킴

지그재그(Zig-Zag)

• 올리고자 하는 노드가 그보다 두 레벨 위의 노드로부터 Left-Right 또는 Right-Left 경로를 따라 내려올 때를 부름
• 지그재그에 대한 처리는 AVL의 LR 또는 RL회전과 완전히 동일
• 두 레벨씩 위로 올렸을 때, 최종적으로 루트 노드와 레벨 차이가 하나만 날 수도 있음
  • 이 경우 AVL과 마찬가지로 한번만 회전을 가하면 됨

4) 2-3 트리

• AVL은 균형 트리를 지향하는 반면 2-3 트리는 완전 균형 트리를 지향함
• AVL 트리에 비해 상대적으로 단순한 논리

2-3 트리의 삽입

• 반복된 삽입에도 2-3 트리의 높이는 좀처럼 증가하지 않음
• 3-노드를 사용해서 최대한 많은 레코드를 높이 변화 없이 수용

2-3 트리의 삭제

• 왼쪽 또는 오른쪽 자매 노드를 살핌
• 자매 노드들 중에 하나라도 3-노드가 있으면 빌려오되(빈자리, 메모리) 반드시 부모 노드를 거쳐서 빌려옴

• 키 1, 4로 구성된 왼쪽 자매 노드의 키 4인 레코드가 부모 노드로 올라가는 대신 부모 노드의 키 5인 레코드가 삭제된 키 10의 자리로 들어감

• 키 5의 삭제, 왼쪽 오른쪽 3-노드가 없어 노드 자체가 삭제됨
• 따라서 자식 노드가 두 개로 줄어들어 부모 노드도 2-노드로 바뀌어야 함

• 부모 노드의 (왼쪽)키 중 하나가 삭제된 노드의 (왼쪽) 자매 노드로 이동

• 물론 부모 노드의 오른쪽 키가 오른쪽 자매 노드로 이동할 수도 있음

• 아래는 키 20인 노드를 삭제한 최종 결과

• 키 40의 삭제, 키 80 노드로부터 빌릴 키가 없으므로 키 40인 노드는 삭제

• 부모 노드인 키 45 노드는 더 이상 2-노드 상태를 유지할 수 없어 삭제된 노드의 자매 노드인 키 80 노드로 합쳐짐. 키 45 노드가 빈 자리로 남게 됨

• 왼쪽의 자매 노드인 키 4 노드가 보이지만 빌릴 수 없음

• 키 45 노드는 삭제. 키 35인 루트 노드가 2-노드 상태를 유지할 수 없어 왼쪽 자매 노드와 합쳐짐
• 루트 노드 자체가 삭제되고 트리 높이가 감소되나 균형 상태는 유지됨

여러가지 방법

• 삽입, 삭제를 위해서는 삽입 대상 노드의 부모 노드를 접근해야 함
• 삽입 시에 중간 키를 올리기 위해서, 또 삭제 시에 부모 노드의 키를 아래로 내리기 위해서 이진 트리는 부모 노드로부터 자식 노드로 가는 포인터만 유지
• 루트로부터 내려가면서 만나는 모든 노드를 가리키는 포인터 값을 계속적으로 스택에 푸시해 놓으면 팝(Pop) 연산을 통해 직전의 부모 노드에 접근할 수 있음

탐색 효율

• 모든 노드가 3-노드일 때 가장 높이가 낮음
• 레벨 0의 루트 노드가 3-노드라면 그 내부에는 2개의 레코드가 들어감
• 레벨 1에 3개의 3-노드가 있다면 그 내부에는 각각 2개의 레코드가 들어감
• 레벨 h까지의 레코드 수
• N = 2(1 + 3 + 32 + … + 3h) ≈ 3h
• 트리 높이 h는 최대 레벨 수와 일치하므로 결과적으로 h ≈ log3N
• 최악의 경우는 모든 노드가 2-노드로서 트리의 높이 h ≈ log2N
• 2-3 트리에는 2-노드와 3-노드가 섞여 있으므로 효율은 O(log2N)과 O(log3N) 사이에 존재함
• 이에 반해 이진 탐색 트리는 최악의 경우 O(N)으로 전락
• 2-3 트리는 항상 완전 균형 트리를 유지하므로 최악의 경우에도 효율을 보장
• 3-노드는 비교해야 할 키가 2개이므로 비교의 횟수가 증가
• 3-노드는 자식을 가리키는 포인터가 3개 이므로 자식 노드가 없다면 2-노드에 비해 널 포인터가 차지하는 공간적 부담
• 널 포인터는 리프 노드에 다수가 분포

5) 2-3-4 트리

• O(log2N)과 O(log4N) 사이의 탐색 효율을 가짐
• 추가로 4-노드를 정의
  • 자식 노드로 가는 링크(Link)가 4개이고 키가 3개인 노드
  • 왼쪽 자식(Left Child), 오른쪽 자식(Right Child), 왼쪽 중간 자식(Left Middle Child), 오른쪽 중간 자식(Right Middle Child)으로 구분

2-3-4 트리의 장단점

• 높이를 log4N으로 조금 더 낮추기 위함
• 스택이 불필요
• 리프 노드 근처의 널 포인터 공간도 2-3 트리에 비해서 더 많아짐
• 필요시 최대 3개의 키를 비교해야 하는 시간적 부담

2-3-4 트리의 삽입

• 루트로부터 삽입 위치를 찾아서 내려가는 도중에 4-노드를 만나면 무조건 제거하면서 내려감
• 하나의 삽입 작업이 트리 모습을 바꾸면서 내려가는 동안, 동시에 이어서 두 번째 삽입 작업이 루트로부터 내려올 수 있음

• 루트가 4-노드인 경우. 중간 키인 Y가 올라가서 트리 높이 증가

• 내려가면서 만난 4-노드가 2-노드의 자식 노드일 경우. 중간 노드를 올리되, 나머지 노드는 분리되어 부모 노드의 왼쪽 자식과 중간 자식으로 붙게 됨. 높이는 그대로 유지

• 내려가면서 만난 4-노드가 3-노드의 자식 노드일 경우. 부모 노드가 4-노드로 바뀌면서 왼쪽 중간 자식, 오른쪽 중간 자식으로 분리시켜 붙임. 트리 높이는 그대로 유지

6) 레드 블랙 트리(Red-Black Tree)

• 2-3-4 트리를 이진 트리로 표현한 것
• 레드 블랙 트리의 링크(Link)는 색깔을 지님
• 포인터 변수에 색깔이라는 속성을 추가

레드 블랙 트리의 표현

• 모든 2-3-4 트리는 레드 블랙 트리로 표현 가능

• 2-노드는 그대로 둠

• 3-노드는 왼쪽 또는 오른쪽 키를 루트로 하는 이진 트리로 변경, 따라서 트리 모양이 유일하지는 않음

• 빨강 링크는 원래 3-노드, 4-노드에서 같은 노드에 속했었다는 사실을 나타내며 4-노드의 레드 블랙 표현은 유일함

레드 블랙 트리의 속성

• 트리를 내려오면서 연속적인 빨강 링크 2개는 허용하지 않음
• 루트로부터 리프 노드까지 검정 링크의 수는 모두 동일함
• 2개의 자식 노드가 모두 빨강 링크일 때만 4-노드에 해당함
• 만약 첫 트리처럼 연속된 빨강이 존재한다고 가정하면 X-Y가 빨강이므로 그것은 둘째 트리에서 나왔을 것, 이는 다시 셋째 트리에서 유래되었을 것

사용 이유

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