이진 탐색 트리 코드 분석

개념 파트는 https://blog.encrypted.gg/1013 를 참고하여
코드는 https://code-lab1.tistory.com/10 을 참고하여 쓴 글임을 미리 밝힙니다.

혼자 썡으로 구현해보았으므로 이진 탐색 트리의 일반적인 알고리즘과 다른 사람의 코드를 공부해보기로 하였다.

1. 개념

1. 노드의 왼쪽 서브트리에는 해당 노드보다 작은 값, 오른쪽 서브트리에는 해당 노드보다 큰값이 저장
2. 중위순회를 하면 오름차순 정렬이 된다.

이진 검색트리는 삽입, 삭제, 탐색이 모두 O(log N)에 처리된다.

(단, 정렬돼서 데이터들이 들어오면 한줄로 나열되어 연결리스트와 차이점이 없게된다.)

Insert는 작은 건 왼쪽으로 큰 건 오른쪽으로

Find도 마찬가지

Erase가 가장 어려운 부분인데

(1) 자식이 없는 정점 지우기 -> 그냥 지우면 된다.
(2) 자식이 한개인 정점 지우기 -> 자식을 지워진 노드의 자리로 옮기면 된다.
(3) 자식이 두개인 정점 지우기 -> 지우고싶은 원소에서 오른쪽으로 가서 그 뒤에 왼쪽으로만 가서 나오는 노드로 대체 가능 (오른쪽 서브트리 중에서는 가장 작고 왼쪽 서브트리의 모든 노드보다 값이 크다.)
또는 지우고 싶은 원소에서 왼쪽으로 간 후 오른쪽으로 계속 가는 것도 가능.

하지만

이 그림에서 34는 자식이 한 개뿐이므로 이가 가능하나 자식이 두개이면 어떡하나?
-> 그런 일은 없다. 그러면 한번 더 왼쪽으로 간다.

2. 코드

삭제가 나와 아이디어가 다르므로 삭제만 코드를 보자.

TreeNode* delete_node(TreeNode* root, int key){
    TreeNode* del = NULL;    // 삭제할 노드     
    TreeNode* parent = NULL;    // 삭제할 노드의 부모 노드 
    TreeNode* successor = NULL;    // 삭제할 노드의 왼쪽 서브트리에서 가장 큰 노드 -> 삭제한 노드를 대체할 노드
    TreeNode* predecessor = NULL;    // successor의 부모노드 ->child와 연결해야함
    TreeNode* child = NULL;        // 삭제할 노드의 자식 노드 
    
    del= root;
    while(del != NULL){    // 삭제할 노드 탐색 
        if(key == del->key){
            break;
        }
        parent = del;
        if(key < del->key){
            del = del->left;
        }else{
            del = del->right;
        }
    }
    
    if(del == NULL){
        printf("Error : 존재하지 않는 키\n");
        return root;
    }
    
    if(del->left == NULL && del->right == NULL){    // 삭제할 노드의 자식노드가 없는 경우 
        if(parent != NULL){    // 부모노드가 있는 경우 
            if(parent->left == del){    // 부모노드의 왼쪽노드가 삭제할 노드일 때 
                parent->left = NULL;
            }else{    // 오른쪽 일 때 
                parent->right = NULL;
            }
        }else{    // 부모노드가 없는 경우 = root 노드 
            root = NULL;//자식 노드가 없는 경우이므로 이것만 하면 된다.
        } 
    }else if(del->left != NULL && del->right != NULL){    // 삭제할 노드의 자식 노드가 2개인 경우 
        predecessor = del;
        successor = del->left;
        
        while(successor->right != NULL){    // 왼쪽 서브트리에서 가장 큰 값 찾기 
            predecessor = successor;
            successor = successor->right;
        }
        
        predecessor->right = successor->left;    // successor의 자식 노드 위치 변경 
        successor->left = del->left;    // successor를 삭제할 노드의 위치로 옮긴 것과 같음 
        successor->right = del->right;     
        
        if(parent != NULL){    // 삭제할 노드의 부모노드가 있을 때 
            if(parent->left == del){
                parent->left = successor;
            }else{
                parent->right = successor;
            }
        }else{
            root = successor;
        }
    }else{    //     삭제할 노드의 자식 노드가 1개인 경우 
        if(del->left != NULL){    // 왼쪽 노드 
            child = del->left;
        }else{    // 오른쪽 노드 
            child = del->right;
        }
        
        if(parent != NULL){    // 부모노드가 있는 경우 
            if(parent->left == del){    // 부모노드의 왼쪽 노드로 삭제할 노드의 자식노드 연결 
                parent->left = child;
            }else{    // 부모노드의 오른쪽 노드로 삭제할 노드의 자식노드 연결  
                parent->right = child;
            }
        }else{
            root = child;
        }
    }
    
    free(del);    // 메모리해제 
    return root; 
}


출처: https://code-lab1.tistory.com/10 [code_lab]