Tree - Binary Search Tree

Binary Tree 중, 아래의 조건을 만족하는 Tree이다.

1. 루트노드의 왼쪽 서브트리의 노드는 루트노드보다 작거나 같아야 한다.

2. 루트노드의 오른쪽 서브트리의 노드는 루트노드보다 커야한다.

 

BST로 언제나 그랬 듯 가방을 만들건데,

이 부분은 코드보단 개념과 데이터 추가/삭제를 이해하는 편이 좋기 때문에 pseudo code로 작성하겠다.

 

생성자

루트 포인터를 NULL로 초기화.

 

복제 생성자

인자로 들어온 루트 포인터를 복사하고, 그 결과를 루트 포인터로 가리키게 한다.

앞서 구현한 tree_copy함수를 사용

 

파괴자

모든 노드를 해제한다.

앞서 구현한 tree_clear함수를 사용

 

size()

모든 노드의 갯수를 세는 함수

1 + size(왼쪽 서브트리) + size(오른쪽 서브트리) 이렇게 재귀적으로 구현

 

= (assignment operator overloading)

LHS = RHS가 같은지 검사. 같다면 본인 자신이 들어온 것이기에 다른 행동없이 바로 리턴

현재 할당받은 모든 메모리를 해제. (tree_clear로 제거)

RHS의 트리를 복제(tree_copy 사용) 후 self 리턴

 

insert(entry)

*new_ptr = new node(entry)로 새로운 노드를 생성

만약 트리가 비어있다면, root_ptr = new_ptr 그리고 리턴

아니라면, 아래의 기능을 반복

case1. entry <= node_ptr->data()

    if node_ptr->left() == NULL, node_ptr->set_left(new_ptr), 리턴

    else node_ptr = node_ptr->left();

case2. entry > node_ptr->data()

    if node_ptr->right() == NULL, node_ptr->set_right(new_ptr), 리턴

    else node_ptr = node_ptr->right();

 

erase_one(target)

이게 좀 까다롭다. 45라는 노드를 제거하는 경우를 생각해보자.

<Fig. 01: easy>

<Fig. 01>과 같은 경우는 간단히 node_ptr을 53으로 바꾸고, 45를 delete하면 된다.

하지만 아래의 경우가 머리가 아파진다.

 

<Fig. 02: ...wow>

이런 경우에는 단순히 45를 제거할 수 없다. (서브트리들이 분리되기 때문)

이런 경우에는 왼쪽 서브트리에서 가장 큰 값(17)을 제거한 후, 45자리에 그 값(17)을 넣어주면 된다.

따라서 erase_one을 구현하기 위해 bst_remove, bst_remove_max 두 개의 함수를 구현하여 해결할 예정이다.

 

bst_remove(root_ptr, target)

1. 트리가 비어있는 경우

그냥 리턴한다.

 

2. target < root_ptr->data()

bst_remove(root_ptr->left(), target을 재귀호출

 

3. target > root_ptr->data()

bst_remove(root_ptr->right(), target을 재귀호출

 

4. target == root_ptr->data()

case1. root_ptr가 왼쪽 자식노드가 없는 경우 (<Fig. 01>의 경우)

    oldroot_ptr = root_ptr;

    root_ptr = root_ptr->right();

    delete oldroot_ptr

case2. root_ptr가 왼쪽 자식노드가 있는 경우 (<Fig. 02>의 경우)

    bst_remove_max(root_ptr->left(), root_ptr->data());

 

bst_remove_max(root_ptr, removed_item)

case1. root_ptr가 오른쪽 자식노드가 없는 경우 (본인이 가장 큰 값인 경우)

    removed_item = root_ptr->data();

    oldroot_ptr = root_ptr;

    root_ptr = root_ptr->left();

    delete oldroot_ptr;

case2. root_ptr가 오른쪽 자식노드가 있는 경우

    bst_remove_max(root_ptr->right(), removed_item); 재귀호출

 

 

+= (operator overloading)

insert_all 함수를 재귀호출하는 방식으로 구현.

template <class Item>
void bag<Item>::operator+=(const bag<Item> &addend) {
    if (this == &addend) {
        binary_tree_node<Item> *add_ptr = tree_copy(addend.root_ptr);
        insert_all(add_ptr);
        tree_clear(add_ptr);
    }
    else
        insert_all(addend.root_ptr);  // addend.root_ptr == root_ptr
}


template <class Item>
void bag<Item>::insert_all(const binary_tree_node<Item> *tree_ptr) {
    if (tree_ptr != NULL) {
        insert(tree_ptr->data());
        insert_all(tree_ptr->left());
        insert_all(tree_ptr->right());
    }
}

여기서 본인을 복사하는 경우에 따로 add_ptr로 미리 복사하는 이유는

insert_all 하는 과정에서 본인에게 노드가 추가되기 때문에 add_ptr로 복사를 안하고 본인을 인자로 호출한다면

무한 복사가 일어나기 때문