이진 탐색 트리(BST)

: 이진 트리의 일종이고, 효율적인 탐색을 위한 자료구조

규칙

• 각 노드의 키는 유일하다.
• 부모가 왼 자식보다 크고, 오른 자식보다 작다.
• 각 서브노드도 이진탐색트리이다.

탐색

: root부터 시작해, 원하는 key가 작으면 왼쪽 서브트리, 크면 오른쪽 서브트리로 이동

• 시간복잡도: O(log n) . 정확히는 O(h)
  • 최악의 경우(편향된 트리, 즉, 각 노드가 일렬로 되어있는 경우 O(N)이 된다.)

// linked list
bool search(Node* node, int target) {
    if(node == NULL)
        return false;
    if(node->data == target)
        return true;
    return node->data < target ? search(node->right, target) : search(node->left, target);
}

// array
bool search(int index, int target) {
    if(!indexInRange(index) || tree[index] == 0)
        return false;
    if(tree[index] == target)
        return true;
    return tree[index] < target ? search(index * 2 + 1, target) : search(index * 2, target);
}

삽입

: 탐색 후 마지막으로 NULL인 자리에다가 삽입

• 탐색을 바탕으로 하고, 삽입만을 하는 연산 자체는 O(1). 따라서, 전체 복잡도는 탐색이랑 같음 O(log n)

// linked list
void insert(Node* node, int target) {
    if(node->data < target) {
        if(node->right == NULL) { //found
            node->right = new Node(target);
            node->right->left = node;
            return;
        }
        insert(node->right, target);
    }
    else {
        if(node->left == NULL) { //found
            node->left = new Node(target);
            node->left->right = node;
            return;
        }
        insert(node->left, target);
    }
}

// Array. 연결 작업이 없기 때문에 linked list에 비해 간결
void insert(int index, int target) {
    if(isInRange(index) && tree[index] == 0) {
        tree[index] = target;
        return;
    }
    
    tree[index] < target ? insert(index * 2 + 1, target) : insert(index * 2, target);
}

삭제

: 삭제할 노드의 서브트리 갯수에 따라 로직이 상이.

• 0개 일 때: 그냥 지워버림
• 1개 일 때: 지우고 리프를 지운 노드 위치로 승격
• 2개 일 때: 왼쪽 서브트리 중 가장 큰 것 or 오른쪽 서브트리 중 가장 작은 것을 지운 노드 위치로

// linked list

// 오른쪽 서브트리에서의 최솟값을 찾는 함수
Node* searchMinNode(Node* node) {
    return node->left == NULL ? node : searchMinNode(node->left);
}

void delete(Node* root, int target) {
    Node* cur = root;
    
    while(1) { // 지울 node 찾기
        root = cur; // 부모노드 set
        if(cur->data == target)
            break;
        cur = cur->data < target ? cur->right : cur->left;
    }
    
    // leaf 0개 일 때
    if(cur->left == NULL && cur->right == NULL) {
        if(root->right->data == cur->data)
            root->right = NULL;
        else
            root->left = NULL;
    }
    // leaf 1개 일 때
    if(cur->left == NULL || cur->right == NULL) {
        Node* newNode = NULL;
        if(cur->left != NULL)
            newNode = cur->left;
        else
            newNode = cur->right;
        
        if(newNode->data == root->right->data)
            root->right = newNode;
        else
            root->left = newNode;
    }
    // leaf 2개 일 때
    else if(cur->left != NULL && cur->right != NULL){
        Node* minNode = searchMinNode(cur->right);
        minNode = delete(cur, minNode->data); // 옮길 노드의 연결을 유지하기 위한 재귀
        cur->data = minNode->data;
    }   
}

Reference)

https://dailykoding.tistory.com/26

https://ansohxxn.github.io/algorithm/bst/

https://github.com/JaeYeopHan/Interview_Question_for_Beginner/tree/master/DataStructure