JArchive 프로그래밍 일기

이진탐색트리

이진 탐색 트리란?

이진 트리는 자식 노드가 최대 2개인 트리 입니다.

이진 탐색 트리는 이진 탐색을 위한 이진 트리 입니다.

이진 탐색은 집합이 '배열'인 경우에만 가능합니다.

왜냐하면 처음과 끝을 알아야 하고, 집합의 전체 길이를 알아야 합니다.

가장 중요한 것은 인덱스를 이용하여 바로 중앙 요소에 접근할 수 있어야 합니다.

그러나, 링크드 리스트 처럼 동적으로 집합의 크기가 달라지는 경우에는 사용할 수 없습니다.

부모 노드('나')를 기준으로, 왼쪽 자식노드는 나보다 작고, 오른쪽 자식 노드는 나보다 큽니다.

이 규칙을 기반하여 탐색합니다.

탐색

Node* SearchNode(Node* tree, int target){
    if(tree == NULL){
        return NULL;
    }

    if(tree->data == target){ // 탐색 성공

    }else if(tree->data < target){ // 현재 데이터가 타겟보다 작다면, 오른쪽으로
        return SearchNode(tree->right, target);
    }else{
        return SearchNode(tree->left, target); // 타겟보다 크다면, 왼쪽으로 가본다
    }
}

삽입

새 노드를 어디에 삽입할지 찾아야 합니다.

루트 노드와 새 노드를 인자로 받습니다.

void InsertNode(Node** tree, Node* child){

    if((*tree)->data < child->data){ // 새 노드가 현재 노드보다 큰 경우, 

        if((*tree)->right == NULL){
            (*tree)->right = child;
        }else{
            InsertNode(&(*tree)->right, child);
        }

    }else if((*tree)->data > child->data){ // 새 노드가 현재 노드보다 작은 경우,
        if((*tree)->left == NULL){
            (*tree)->left = child;
        }else{
            InsertNode(&(*tree)->left, child);
        }
    }
}

삭제

삭제할 노드가 트리의 맨 끝 리프노드라면 쉽습니다.

하지만 리프노드가 아닌 경우의 삭제 처리가 복잡합니다.

삭제할 노드가 자식을 양쪽 다 가진 경우.

삭제할 노드가 자식을 한 쪽만 가진 경우.

양쪽 자식을 가진 경우

삭제되는 노드의 오른쪽 하위 트리중에서 가장 작은 값을 삭제되는 노드의 부모에게 연결해줍니다.

왜 삭제되는 노드의 오른쪽 하위 트리가 필요한 걸까?

삭제되는 노드의 오른쪽 하위에 있는 노드들은 삭제된 노드보다 전부 큰 수를 가지고 있습니다.

그 하위 트리 중에서 가장 작은 수를 삭제된 자리에 집어넣는 것입니다.

하위 트리 중에서 가장 작은 수는 그 트리에서 왼쪽 가장 끝에 있을 것 입니다.

외자식을 가진 경우

삭제되는 노드의 자식 트리를 부모에게 연결해줍니다.

삭제 코드

• 삭제할 타겟을 탐색합니다.
• 타겟을 찾고 나서, 아래를 수행합니다.
• 잎 노드인 경우, 삭제하고 끝납니다.
• 양쪽 자식을 가진 경우, 최소값을 가진 노드를 찾아내서 삭제한 노드 자리에 갖다 놓습니다.
• 외자식을 가진 경우, 삭제한 노드의 자식을 부모에게 이어줍니다.

Node* RemoveNode(Node* tree, Node* parent, int target){

    // 삭제할 타겟 노드 
    Node* remove_node = NULL;

    // 타겟을 탐색
    if(tree == NULL){
        return NULL;
    }

    if(tree->data < target){
        remove_node = RemoveNode(tree->right, tree, target);
    }else if(tree->data > target){
        remove_node = RemoveNode(tree->left, tree, target);

    }else{ // 타겟 찾음 (3가지 노드 종류에 따라 삭제 수행)

        if(tree->left == NULL && tree->right == NULL){  // 1. 타겟이 잎노드인 경우,

            if(parent->right == tree){
                parent->right = NULL;
            }else{
                parent->left = NULL;
            }

        }else if(tree->left != NULL && tree->right != NULL){ // 2. 양쪽 자식 있는 경우,

            // 오른쪽 자식트리에서 '최소값'가진 노드를 탐색
            Node* minNode = SearchMinNode(tree->right);
            remove_node = RemoveNode(tree, NULL, minNode->data); // 최소값 노드를 제거 
               tree->data = minNode->data; //타겟 자리에 최소값을 갖다놓음    

        }else{ // 3. 외자식 있는 경우, 

            Node* tempTree = NULL;

            if(tree->right != NULL){ // 어느 쪽 자식트리인지 확인 
                tempTree = tree->right;
            }else{
                tempTree = tree->left;
            }

            // 타겟의 자식트리를 자신의 부모에게 이어준다.
            if(parent->right == tree){
                parent->right = tempTree;
            }else{
                parent->left = tempTree;
            }
        }
    }

    return remove_node;
}

양쪽 자식이 있는 경우에서 최소값 노드 찾는 SearchMinNode() 함수

해당 트리 내에 최소값을 찾습니다.

따라서 계속 왼쪽으로만 탐색해서 발견된 값을 리턴하면 됩니다.

Node* SearchMinNode(Node* tree){

    if(tree == NULL){
        return NULL;
    }

    if(tree->left == NULL){ // 자신이 마지막 왼쪽노드면 자신을 리턴!
        return tree;
    }else{
        return SearchMinNode(tree->left);  // 더 왼쪽으로 가본다.
    }

}