Tree - Heap, B-Tree

Heap

Heap은 complete binary tree의 일종으로 추가로 아래의 조건을 만족하는 tree이다.

모든 노드는 그 자식노드(나아가 Descendant)보다 반드시 크거나 같아야 한다.

 

즉, 데이터를 넣을 때 마다 루트노드쪽으로 갈수록 큰 값이 저장되도록 정렬되는데,

이런 특징일 이용해 priority queue를 구현할 때 heap 구조가 사용된다.

 

데이터의 추가와 삭제를 살펴보자.

push()

1. 일단 complete binary tree가 되게끔 노드를 맨 아래 왼쪽에 추가한다.

2. heap을 만족하는 적절한 위치가 될 때까지 부모노드와 위치를 바꾸며 올라간다.

(reheapification upward)

 

pop()

heap에서 특정 값 pop은 생략한다. 가장 큰 값, 즉, 루트노드만 제거한다.

1. 일단 complete binary tree가 되게끔 맨 아래 왼쪽 노드를 루트노드자리로 옮긴다. (data 복제)

2. heap을 만족하는 적절한 위치가 될 때 까지 루트노드와 자식노드의 위치를 바꾸며 내려간다.

(reheapification downward)

 

heap의 경우에는 complete bianry tree의 일종이기 때문에 굳이 node와 포인터로 구현할 필요 없이

단순한 1차원 배열로도 구현이 가능하다.

루트노드는 [0]

특정노드가 [i]일 때, 자식노드는 [2i+1], [2i+2], 부모노드는 [i/2]

 

 

B-Tree

B-Tree는 BST(Binary Search Tree)의 단점을 극복하고자 고안된 자료구조이다.

만약 1~10의 데이터를 넣는다고 가정해보자.

그럼 BST는 루트노드(1)부터 리프노드(10)까지 오름차순 순서대로 오른쪽으로만 주렁주렁 정렬되어 있을 것이다.

이런 경우에는 트리가 너무 언발란스(?) 하기 때문에 O(nlogn) 탐색시간의 장점을 살릴 수 없다.

이런 특이 케이스의 경우도 극복하고자 B-Tree가 고안되었다.

 

대표적으로 파일 시스템에 사용되는 B-Tree는 특이하게도 하나의 노드가 여러개의 entry(데이터) set을 가질 수 있다.

까다롭지만, 아래의 6개의 조건이 만족되는 트리 구조를 B-Tree로 정의한다.

1. 루트노드를 제외한 모든 노드는 MINIMUM보다 많은 엔트리를 가져야 한다.

2. 루트노드를 포함한 모든 노드는 MAXIMUM이하의 엔트리를 가져야 한다. (MAXIMUM = 2*MINIMUM)

3. 각 노드에 저장된 엔트리는 오름차순으로 정렬되어야 한다.

4. 리프노드를 제외한 모든 노드는 n개의 엔트리를 갖는다면, 반드시 n+1개의 자식노드를 가져야 한다.

 

<Fig. 01: example of B-Tree (small...)>

5. 리프노드를 제외한 모든 노드는 <Fig. 01> 기준 아래의 규칙을 만족해야 한다.

    a. 4 입장에서 왼쪽은 작은 엔트리로 구성된 서브트리, 오른쪽은 큰 엔트리로 구성된 서브트리

    b. 7 입장에서 왼쪽은 작은 엔트리로 구성된 서브트리, 오른쪽은 큰 엔트리로 구성된 서브트리

    (즉 BST의 규칙을 여러 엔트리로 확장한 것이다)

6. 모든 리프노드의 depth는 같아야 한다.

 

B-Tree의 구현 역시 적당히 pseudo code로 작성해보자.

class btree_node {
    ...
    private:
        static const size_t MINIMUM = 200;
        static const size_t MAXIMUM = 2*MINIMUM;
        size_t data_count;
        Item data[MAXIMUM+1];
        size_t child_count;
        set *subset[MAXIMUM+2];
}

count(target)

루트노드에서 data[i] >= target를 처음으로 만족하는 i를 찾는다. (만약 만족하는 data[i]가 없다면, i == data_count가 될 것)

만약 data[i] == target, return 1

만약 루트노드에 자식노드가 없다면, return 0

나머지(자식은 있지만, 찾고자 하는 데이터가 없는 경우), return subset[i]->count(target)

 

insert(entry)

<Fig. 02: insert 18 at b-tree>

이를 구현하기 위해 loose_insert, fix_excess 함수를 추가로 구현할 예정.

만약 loose_entry(entry) == false, return false (추가가 안됬다는 뜻).

만약 data_count > MAXIMUM,

    엔트리가 없는(비어있는) 새 루트노드를 만들고 그 자식으로 기존의 루트노드가 오게 한다.

    기존의 루트노드에 fix_excess 호출.

return true

 

loose_insert(entry): MAXIMUM보다 하나가 더 많은 엔트리를 허용하며 추가하는 함수

루트노드에서 data[i] >= entry를 처음으로 만족하는 i를 찾는다. (만약 만족하는 data[i]가 없다면, i == data_count가 될 것)

만약 data[i] == entry, return false. (이번에 구현할 b-tree에서는 중복된 데이터는 추가하지 않는다)

만약 루트노드에 자식노드가 없다면, i부터 뒤로 밀고, data[i] = entry, return true. (단, 이 때 excess가 발생할 수 있다)

나머지(자식도 있고, 중복되는 데이터가 없는 경우, subset[i]에 들어갈 수 있음),

    bool b = subset[i]->loose_insert(entry)

    subset[i]가 excess하는지 확인.

    excess한다면 fix_excess 호출.

    return b

 

fix_excess()

MAXIMUM+1개의 엔트리를 갖는 노드를 가운데 엔트리를 기준으로 두 개의 노드로 분할하고,

가운데 엔트리는 부모노드로 올린다.

 

erase(target)

insert와 비슷한 방식으로 일단 삭제하고, 부족한 부분을 수정하는 방식으로 진행하는데,

현재 시간이 많이 부족한 관계로 나중에 기회가 되면 적도록 하겠습니다..