Binary Tree

전체구조

Binary Tree의 구조는 다음과 같습니다. 각 Node 객체끼리 왼쪽 노드, 오른쪽 노드, 부모 노드로 연결되어 있으며 최상위 노드는 부모 노드가 없으며 서로 연결된 노드를 통해 접근 할 수 있습니다. 부모 노드의 값을 기준으로 값이 적으면 왼쪽, 값이 크면 오른쪽으로 구성 됩니다.

Node 구조

class Node {
public:
    int data;
    Node* left;
    Node* right;
    Node* parent;
 
    Node(int data) {
        this->data = data;
        left = right = parent = NULL;
    }
};

데이터를 의미하는 int data와 왼쪽, 오른쪽 부모 노드를 가르키는 Node* 타입의 변수와 기본 생성자로는 매개변수로 받은 data 값을 넣고 노드를 가르키는 값은 NULL로 초기화 합니다.

Binary Tree 클래스 구조

public:
    Node* root;
    BinaryTree() {
        root = NULL;
    }

 

시작 노드는 최상위 노드를 의미합니다.

Node 전체 삭제 함수

void treeDelete(Node* cur) {
        if (cur == NULL) return;
        if (cur->left != NULL)treeDelete(cur->left);
        if (cur->right != NULL) treeDelete(cur->right);
        delete cur
}

 

매개변수로 들어온 값이 NULL이면 무시하고 왼쪽 또는 오른쪽 노드가 비어있지 않다면 순환하면서 맨 밑의 노드부터 차례로 delete를 이용해 메모리 해제 합니다.

특정 Node 삭제 함수

void deleteNode(int data) {
        Node* del = findNode(data);
        if (del == NULL) {
            return;
        }
        if (del->left == NULL && del->right == NULL) {
            if (del == root) {
                delete root;
                return;
            }
            else {//루트가 아니라면
                if (del->parent->left == del) {
                    del->parent->left = NULL;
                }
                else {
                    del->parent->right = NULL;
                }
                delete del;
            }
 
        }
        else if ((del->left != NULL && del->right == NULL) || (del->left == NULL && del->right != NULL)) {
            if ((del->left != NULL && del->right == NULL)) { //왼쪽 자식만 있는경우
                if (del == root) {
                    root = del->left;
                    delete del;
                }
                else {
                    if (del->parent->left == del) {
                        del->parent->left = del->left;
                        del->left->parent = del->parent;
                    }
                    else {
                        del->parent->right = del->left;
                        del->left->parent = del->parent;
                    }
                    delete del;
                }
 
 
            }
            else {//has only right child
                if (del == root) {
                    root = del->right;
                    delete del;
                }
                else {
                    if (del->parent->left == del) {
                        del->parent->left = del->right;
                        del->right->parent = del->parent;
                    }
                    else {
                        del->parent->right = del->right;
                        del->right->parent = del->parent;
                    }
                    delete del;
                }
            }
        }
        else {//have two child
            Node* Succ = findSucc(del);
            if (Succ->right == NULL) {
                if (Succ->parent->left == Succ) {
                    Succ->parent->left = NULL;
                }
                else {
                    Succ->parent->right = NULL;
                }
            }
            else {
                if (Succ->parent->left == Succ) {
                    Succ->parent->left = Succ->right;
                    Succ->right->parent = Succ->parent;
                }
                else {
                    Succ->parent->right = Succ->right;
                    Succ->right->parent = Succ->parent;
                }
            }
            del->data = Succ->data;
            delete Succ;
        }
    }

 

 

CASE1: 왼쪽과 오른쪽 노드의 값이 NULL 일 경우

맨 아래층에 있다는 것을 의미 하므로 부모노드의 left 또는 right 값을 NULL로 설정 후 delete로 메모리 해제합니다.

 

CASE2: 왼쪽 또는 오른쪽 한쪽만 NULL이 아닌 경우

NULL이 아닌 노드로 이동해서 부모의 값을 현재 노드의 부모값으로 변경 후 현재 노드를 메모리 해제합니다.

 

CASE3: 왼쪽, 오른쪽 둘다 NULL이 아닌 경우

우선 삭제 할려는 대상의 위치를 findNode 함수를 이용하여 주소 값을 받아옵니다. 이 노드를 삭제하기 전에 이 노드의 자식들 중에서 현재 값보다는 가장 큰 값중 가장 작은 값을 가진 노드를 찾기 위해서 한칸 오른쪽 노드로 이동 후 가장 왼쪽 노드로 계속 이동하여 주소 값을 succ 변수에 저장 합니다. 만약 succ 변수의 오른쪽 노드의 값이 NULL이 아닐 경우는 succ의 부모 노드의 왼쪽 노드 주소를 succ의 오른쪽 노드의 값으로 합니다. 마지막으로 삭제하려던 노드의 data 값을 succ변수의 값으로 대체 해줍니다.

Node 찾기 함수

 Node* findNode(int data) {
        Node* cur = root;
        if (cur == NULL) { 
            return NULL;
        }
        while (cur != NULL && cur->data != data) {
            if (cur->data > data) {
                cur = cur->left;
            }
            else {
                cur = cur->right;
            }
        }
        return cur;
}

 

최상위 부모 노드부터 시작해서 찾고자 하는 값이 현재 기준 노드보다 값이 작다면 왼쪽 노드로 이동하고 값이 크다면 오른쪽으로 이동하면서 순차적으로 검색합니다.

Node 삽입 함수

void insertNode(int data) {
        Node* newNode = new Node(data);
        Node* find = root;
        Node* follow = NULL;
        if (find == NULL) {
            root = newNode;
            return;
        }
 
        while (find != NULL) {
            if (find->data > data) {
                follow = find;
                find = find->left;
 
            }
            else {
                follow = find;
                find = find->right;
            }
 
        }
        if (follow->data > data) {
            follow->left = newNode;
            newNode->parent = follow;
        }
        else {
            follow->right = newNode;
            newNode->parent = follow;
        }
 
}

 

최상위 부모 노드부터 시작하여 Node* find 변수에는 왼쪽 또는 오른쪽으로 노드를 이동하는 현재 노드위치 주소를 담고 Node* follow 변수에는 이동하기 직전 부모노드의 주소의 값을 저장합니다.  data 값을 비교하여 최종 노드가 삽입 될 위치를 구하면 새로 생성한 Node* newNode 변수에 부모 노드에 follow 변수를 저장하고 follow->data의 값을 비교하여 보다 작으면 left 값을 newNode 크면 right 값을 newNode로 저장합니다.