규태

• C++ 통한 BST 구현

//
//  GBinarySearchTree.h
//  BinarySearchTree
//
//  Created by GyutaeHa on 2014. 9. 18..
//  Copyright (c) 2014년 HAGYUT. All rights reserved.
//

#ifndef __BinarySearchTree__GBinarySearchTree__
#define __BinarySearchTree__GBinarySearchTree__

#include <iostream>
#include <string>
#include <stack>
#include <queue>

template <typename E>
class GBinarySearchTree {

public:
    typedef std::string Key;

protected:
    class Node {
    public:
        Key key;
        E elem;
        Node *parent;
        Node *left_child;
        Node *right_child;
        Node(): key(), elem(), parent(NULL), left_child(NULL), right_child(NULL) {}
        Node(const Key& _key, const E& _elem)
        : key(_key), elem(_elem), parent(NULL), left_child(NULL), right_child(NULL) {}
    };

public:
    GBinarySearchTree();
    int getSize() const { return size; }
    bool isEmpty() const { return size == 0; }

    E& get(const Key& _key);
    void insert(const Key& _key, const E& _elem);
    void erase(const Key& _key);

    void printKeysWithOption(int opt);

private:
    Node* getRoot() { return v_root->right_child; }
    Node* _get(const Key& _key);
    bool _isExternal(Node* p) { return (p->left_child == NULL && p->right_child == NULL); }
    void _printKeysWithPreOrder();
    void _printKeysWithInOrder();
    void _printKeysWithPostOrder();
    void _printKeysWithLevelOrder();

private:
    Node *v_root;   // virtual root
    int size;
};



//* ****************************** IMPLEMENT ****************************** *//

template <typename E>
GBinarySearchTree<E>::GBinarySearchTree() {
    v_root = new Node();
    size = 0;
}

template <typename E>
E& GBinarySearchTree<E>::get(const Key& _key) {

    Node *target = _get(_key);

    return target->elem;
}

template <typename E>
typename GBinarySearchTree<E>::Node* GBinarySearchTree<E>::_get(const Key& _key) {

    Node* p = getRoot();
    while (p != NULL) {
        if (_key < p->key)
            p = p->left_child;
        else if(_key > p->key)
            p = p->right_child;
        else
            break;
    }

    return p;
}

template <typename E>
void GBinarySearchTree<E>::insert(const Key& _key, const E& _elem) {

    Node *node = new Node(_key, _elem);

    if (size == 0) {
        v_root->right_child = node;
        node->parent = v_root;
        size++;
        return;
    }

    Node *p = getRoot();
    while (p != NULL) {
        if (_key < p->key) {
            if (p->left_child != NULL) {
                p = p->left_child;
            }
            else {
                p->left_child = node;
                node->parent = p;
            }
        }
        else if (_key > p->key) {
            if (p->right_child != NULL) {
                p = p->right_child;
            }
            else {
                p->right_child = node;
                node->parent = p;
            }
        }
        else {  // duplicated key
            p->elem = _elem;
            return;
        }
    }

    size++;
}

template <typename E>
void GBinarySearchTree<E>::erase(const Key& _key) {

    Node *target = _get(_key);
    if (target == NULL)
        return;

    if (_isExternal(target)) {
        Node *t_parent = target->parent;
        if (t_parent->left_child == target)
            t_parent->left_child = NULL;
        else
            t_parent->right_child = NULL;
        delete target;
    }

    if (target->left_child != NULL) {
        Node *p = target->left_child;
        while (p->right_child != NULL)
            p = p->right_child;
        target->key = p->key;
        target->elem = p->elem;

        if (p->parent == target) {
            if (p->left_child != NULL)
                target->left_child = p->left_child;
            else
                target->left_child = NULL;
        }
        else {
            if (p->left_child != NULL)
                p->parent->right_child = p->left_child;
            else
                p->parent->right_child = NULL;
        }
        delete p;
    }
    else {
        Node *p = target->right_child;
        while (p->left_child != NULL)
            p = p->left_child;
        target->key = p->key;
        target->elem = p->elem;

        if (p->parent == target) {
            if (p->right_child != NULL)
                target->right_child = p->right_child;
            else
                target->right_child = NULL;
        }
        else {
            if (p->right_child != NULL)
                p->parent->left_child = p->right_child;
            else
                p->parent->left_child = NULL;
        }
        delete p;
    }
}

template <typename E>
void GBinarySearchTree<E>::printKeysWithOption(int opt) {

    switch (opt) {
        case 0:
            _printKeysWithPreOrder();
            break;
        case 3:
            _printKeysWithLevelOrder();
            break;
        default:
            break;
    }

}

template <typename E>
void GBinarySearchTree<E>::_printKeysWithPreOrder() {

    std::stack<Node*> st;
    Node *p = getRoot();
    if (p == NULL)
        return;

    st.push(p);
    while (!st.empty()) {

        p = st.top();
        std::cout << p->key << ", ";
        st.pop();

        if (p->right_child != NULL)
            st.push(p->right_child);
        if (p->left_child != NULL)
            st.push(p->left_child);
    }
    std::cout << std::endl;
}

template <typename E>
void GBinarySearchTree<E>::_printKeysWithPostOrder() {

}

template <typename E>
void GBinarySearchTree<E>::_printKeysWithLevelOrder() {

    std::queue<Node*> q;
    Node *p = getRoot();
    if(p == NULL)
        return;

    q.push(p);
    Node *pp = v_root;
    while (!q.empty()) {

        p = q.front();
        std::cout << p->key << " ";
        q.pop();

        if (pp->right_child == p) {
            std::cout << std::endl;
            pp = p;
        }

        if (p->left_child != NULL)
            q.push(p->left_child);
        if (p->right_child != NULL)
            q.push(p->right_child);
    }
    std::cout << std::endl;
}

#endif /* defined(__BinarySearchTree__GBinarySearchTree__) */