[자료구조] 효율적인 이원 탐색 트리(Efficient Binary Search Trees)

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

static optimality problem: 노드가 정해져서 수정할 수 없음.

dynamic optimality proble: 노드를 추가/삭제 할 수 있음.

 

static Optimality Problem

정적 원소들의 집합에 대한 이원 탐색트리 구조

- 삽입/삭제 없이 탐색만 수행

- iterSearch 이용

element* iterSearch(treePointer tree, int key)
{
    while (tree) {
        if (key == tree->data) return tree;
        if (key < tree->data)
            tree = tree->left_child;
        else
            tree = tree->right_child;
    }
    return NULL;
}

 

- while 루프가 탐색 비용 결정-> 노드 레벨 수를 노드 비용으로 이용

 

 

일반적으로 complete binary tree일 때에 최악과 평균 탐색시간이 우수하지만,

노드 접근에 대한 확률에 따라 달라질 수 있음.

 

특별한 사각형 노드를 추가하면 유용-확장 이진 트리

-외부 노드(실패노드): n+1개의 사각 노드

-내부 노드: 원래의 n개 노드

 

외부 경로 길이(external path length): 루트에서 각 외부 노드까지의 경로 길이 합

내부 경로 길이(internal path length): 루트에서 각 내부 노드까지의 경로 길이 합

외부 경로 길이 E = 내부 경로 길이 I + 2n

 

I의 최소 값

- 최악의 경우: n*(n-1)/2

- 일반적인 경우: 0+2*1+4*2+8*3+....

- 완전 이진 트리일 경우 O(nlog_2(n))

 

정적 원소 집합을 이원탐색 트리로 표현

1) 탐색이 성공적: ∑ pi*level(ai) //pi는 ai를 탐색할 확률

2) 탐색이 실패: ∑ qi*(level(failure node i)-1) //qi는 탐색중인 원소가 Ei에 있을 확률

3) 이원탐색트리의 총 비용: (1+2)

 

 

 

최적 이원탐색 트리 찾기

- a1<a2<a3...<an인 n개의 키

- T_ij = 최적 이원탐색 트리

- w_ij는 Tij의 가중치

- c_ij = T_ij의 비용. c_ii = 0

- r_ij = T_ij의 root, r_ii = 0

 

- T_ij가 a_i+1,,,,,a_j와 r_ij =k에 대한 최적 이원 탐색 트리 -> k는 i<k<=j를 만족

- T_0n = a1,,,,an노드를 갖는 최적 이원 탐색 트리 -> c_0n = 비용, r_0n = root, w_0n: 가중치

 

 

 

 

AVL 트리

 Binary Search Tree의 문제점.

평균은 O(log n)이지만, 최악은 O(n)

 

 

AVL 트리의 정의

공백 트리는 높이 균형을 이룬다

T_L과 T_R을 가진 공백이 아닌 이진 트리라 할 때

- 각각 왼쪽/오른쪽 서브트리

- |h_L - h_R}| <=1: 즉 양쪽 서브트리의 높이 차이는 1보다 작거나 같다.

 

균형 인수(balance factor)

- BF(T) = h_L - h_R : 양쪽 서브트리 간의 높이 차

- 어떠한 노드 T에 대해서도 BF(T) = -1, 0, 1

 

균형 인수가  ±2가 된 원인 (=균형이 깨지는 원인)

1) LL: 새 노드 Y는 A의 왼쪽 서브트리의 왼쪽 서브트리에 삽입

2) RR: 새 노드 Y는 A의 오른쪽 서브트리의 오른쪽 서브트리에 삽입

3) LR: 새 노드 Y는 A의 왼쪽 서브트리의 오른쪽 서브트리에 삽입

4) RL: 새 노드 Y는 A의 오른쪽 서브트리의 왼쪽 서브트리에 삽입

 

Rotations

LL Rotation: LL Line 상의 중앙 노드를 부모로

RR Rotation: RR Line 상의 중앙 노드를 부모로

(이상 2개는 Single Rotation)

LR Rotation과 RL Rotaiton은 Double Rotation으로 부르며

LL유형을 만들고 LL Rotation / RR 유형을 만들고 RR Rotation 적용

 

2-3 트리

Binary Tree의 확장

- 한 노드가 세 개까지 자식을 가질 수 있는 트리

- 2-node: Key 값 하나, 자식 2개

- 3-node: Key 값 두개, 자식은 3개

 

*중요

2-node가 자식을 하나만 가지는 것, 3-node가 자식을 하나 또는 둘만 가지는 것은 허용되지 않음.

 

삽입, 분할

데이터를 삽입할 때, 노드에 빈 공간이 없을 경우 노드 split

(이떄, 중앙 키가 부모로 이동)

 

삽입 알고리즘

현재 노드가 외부 노드가 아닐 동안

- 삽입 키가 왼쪽 키보다 작으면 왼쪽 자식으로

- 삽입 키가 오른쪽 키보다 작으면 중간 자식으로

- 삽입 키가 오른쪽 키보다 크면 오른쪽 자식으로

 

현재 노드가 3-node이면

- 현재 노드를 분할 한다.

- 만약 그 부모 노드도 3-node면 삽입 경로를 거치면서 분할

현재 노드가 2-node이면 삽입키 추가

 

삭제

삭제는 리프 노드에서만.

삭제할 아이템이 리프노드가 아니라면

->삭제할 노드의 후속 노드와 SWAP 후 노드 삭제

리프 노드에 있다면

-> 노드에 다른 아이템이 존재하면 단순 삭제

-> 그렇지 않다면 형제 노드에서 아이템을 빌리고 삭제

-> 형제 노드에서 빌릴 수 없으면 부모와 병합

 

 

 

2-3-4 트리

2-4 트리, B tree of order 4

(2-3 트리는 B tree of order 3)

Red-Black Tree는 2-3-4 Tree의 Binary Search Tree version

내부 노드는 자식을 2,3,4개를 가짐.(1개는 불가능)

Key검색은 2-3트리와 동일

 

삽입 시 분할 방식이 2-3 트리와 다름

2-3 트리

- 3 node의 두 개의 키와 새로 입력되는 키를 정렬

- 중간 키가 부모, 작은 키는 부모의 왼쪽, 큰 키는 오른쪽에 위치

2-3-4 트리

- 분할은 4 node에 새로운 Key가 삽입될 때 실시

- 4 node의 중간 키를 부모로 올리고 작은 키를 왼쪽, 큰 키를 오른쪽에 둔 뒤 새로운 키 삽입

 

삽입 알고리즘

현재 노드가 외부 노드가 아닐 동안

- 현재 노드가 4 node이면 분할

- 삽입 키가 첫번째 키보다 작으면 첫 번째 자식으로

- 삽입 키가 두번째 키보다 작으면 두 번째 자식으로

- 삽입 키가 세번째 키보다 작으면 세 번째 자식으로

- 삽입 키가 세번째 키보다 크면 네 번째 자식으로

외부 노드가 4 node면 분할

외부 노드에 삽입 키를 삽입

 

2-3-4 트리의 노드 분할 과정은

AVL Tree 처럼 삽입이나 삭제 후 전체적인 균형도를 조사할 필요가 없고

2-3 트리처럼 삽입된 경로를 유지해야하는 불편이 없는 장점이 있다.(삽입 Key가 분할의 대상이 되지 않는다.)

 

삭제 알고리즘

삭제는 리프에서만 이루어짐

Case 1: 3 node, 4 node leaf일 때

- 단순 삭제

Case 2: non leaf 일 때

- inorder successor key와 swap

- leaf node가 3 node/4 node -> 단순 삭제

Case 3: 2 node leaf

- parent와 sibling이 모두 2 node가 아니면 borrow

- sibling이 2-node -> merge

- parent가 2 node-> merge

 

 

2-3-4 트리의 장단점

장점

- AVL 트리처럼 삽입, 삭제 후 균형도를 맞출 필요가 없다.

- 2-3 트리처럼 삽입된 경로를 유지해야 하는 불편이 없다.(삽입 노드가 분할의 대상이 되지 않는다.)

 

단점

- 2 node, 3 node의 경우 메모리 낭비가 발생

- 2-3-4 트리는 내부 검색법으로 사용하기는 부적절

 

단점 극복을 위한 방법

내부 검색-> node 크기를 동일하게 -> Red Black Tree

외부 검색-> B Tree의 개념으로 활용

 

 

Red-Black Tree

Red-Black Tree는 2-3-4 트리의 기본 개념을 활용

Red-Black Tree는 Binary Search Tree

Node는 색을 가짐- red, black

2-3-4 노드를 색으로 구분

 

정의(definition)

1. 루트와 모든 외부 노드들은 black이다.

2. 루트에서 외부 노드로의 경로는 두 개의 연속적인 레드 노드를 가질 수 없다.

3. 루트에서 외부 노드로의 모든 경로들에 있는 블랙 노드의 수는 동일하다.

4. 삽입 노드는 모두 레드.

 

불균형 종류

 

요약하면

XYb -> rotation

XYr -> color flip