이진 탐색트리 삭제 포함 소스

/*
 * http://sosal.tistory.com/
 * made by so_Sal
 */

애혀.. 삭제 추가 되게 어렵네요.. 뇌를자극하는 알고리즘 참고해서 만들었습니다.

#include<iostream>
#include<time.h>
using namespace std;

class node{
private:
    int value;
public:
    node(int val){
        value=val;
    }
    int getValue(){
        return value;
    }
    void setValue(int val){
        value = val;
    }
    node* left;
    node* right;
    ~node(){
        delete this;
    }
};

node* CreateNode(int value);         // 노드생성함수
void InsertNode(node* tree,node* newNode);
void DeleteNode(node* delNode);   // 노드삭제함수
void DestroyTree(node* root);        // 트리 삭제함수
void PrintTree(node* Node);          // 노드 출력함수 (중위식)
node* searchMinNode(node* root);
node* RemoveNode(node* root,node* parent,int target);
int main(){
    srand(time(0));

    node* root = CreateNode(50);    // root 노드를 생성한 후
   
    node* newNode;
    for(int i=0;i<100;i++){
        newNode = CreateNode(rand()%100);
        InsertNode(root,newNode);
    }
   
    PrintTree(root);

    for(int i=90;i<=100;i++)
        RemoveNode(root,NULL,i);

    cout<<"-----------------------------------------------------"<<endl;
    PrintTree(root);

    return 0;
}

node* CreateNode(int value){
    node* newNode = new node(value);   // 생성 후
    newNode->left = NULL;                     // 각 value 초기화
    newNode->right = NULL;

    return newNode;
}

void InsertNode(node* tree,node* newNode){
    if(tree->getValue() < newNode->getValue()){
        if(tree->right == NULL)
            tree->right = newNode;
        else
            InsertNode(tree->right,newNode);
    }
    else if(tree->getValue() > newNode->getValue()){
        if(tree->left == NULL)
            tree->left = newNode;
        else
            InsertNode(tree->left,newNode);
    }

    return;
}

void PrintTree(node* Node){
    if(Node == NULL)
        return;
    PrintTree(Node->left);                  
    cout<<Node->getValue()<<endl;   // 중위식 출력
    PrintTree(Node->right);                 // 재귀
    return;
}

void DeleteNode(node* delNode){
    delete delNode;
    return;
}

void DestroyTree(node* root){
    DestroyTree(root->left);
    DestroyTree(root->right);
    DeleteNode(root);
    return;
}

node* searchMinNode(node* root){
    if(root == NULL)
        return NULL;

    if(root->left == NULL)
        return root;
    else
        return searchMinNode(root->left);
}

node* RemoveNode(node* root,node* parent,int target){
    node* cur=NULL;

    if(root == NULL)
        return NULL;

    if(root->getValue() > target)         // 작은경우
        cur = RemoveNode(root->left, root,target);
    else if( root->getValue() < target) // 큰경우
        cur = RemoveNode(root->right, root,target);
    else{
        cur = root;

        if(root->left == NULL && root->right == NULL)
        {            //삭제하려는 노드가 잎노드인 경우
            if(parent->left == root)
                parent->left = NULL;
            else
                parent->right = NULL;
        }
        else if(root->left != NULL && root->right != NULL)
        {   //삭제하려는 노드가 좌 우 모든 자식노드를 가질경우
            node* minNode = searchMinNode(root->right);
            minNode = RemoveNode(root,NULL,minNode->getValue());
            root->setValue(minNode->getValue());
        }
        else
        {   //삭제하려는 노드가 하나의 자식만을 가질경우
            node* tmp = NULL;
            if(root->left != NULL)
                tmp = root->left;
            else
                tmp = root->right;

            if(parent->left == root)
                parent->left = tmp;
            else
                parent->right = tmp;
        }

    }

    return cur;
}