이진 검색 트리를 활용한 다양한 연산 방법을 살펴봅니다. 아래 내용은 이진 검색 트리(BST)에서 값 검색, 유효성 확인, 최빈값 찾기, 공통 조상 찾기, 삽입 및 삭제 등을 다룹니다.

BST에서 값 검색

다음과 같이 반복문을 사용해 특정 값을 검색할 수 있습니다.

Node* searchBST(Node* root, int target) {
    if (!root) return nullptr;
    while (root) {
        if (root->data > target) root = root->left;
        else if (root->data < target) root = root->right;
        else return root;
    }
    return nullptr;
}

유효한 BST 확인

중위 순회를 통해 정렬된 상태를 확인하는 방식입니다.

bool isValidBST(Node* root) {
    Node* prev = nullptr;
    stack st;
    Node* curr = root;

    while (curr || !st.empty()) {
        while (curr) {
            st.push(curr);
            curr = curr->left;
        }

        curr = st.top();
        st.pop();

        if (prev && prev->data >= curr->data) return false;
        prev = curr;
        curr = curr->right;
    }
    return true;
}

BST에서 최빈값 찾기

DFS를 활용하여 각 노드의 빈도수를 계산합니다.

vector<int> findMode(Node* root) {
    unordered_map freqMap;
    function dfs = [&](Node* node) {
        if (!node) return;
        freqMap[node->data]++;
        dfs(node->left);
        dfs(node->right);
    };

    dfs(root);

    vector<int> result;
    int maxFreq = 0;
    for (const auto& pair : freqMap) {
        if (pair.second > maxFreq) {
            result.clear();
            result.push_back(pair.first);
            maxFreq = pair.second;
        } else if (pair.second == maxFreq) {
            result.push_back(pair.first);
        }
    }
    return result;
}

공통 조상 찾기

BST의 특성을 이용해 효율적으로 공통 조상을 찾습니다.

Node* lowestCommonAncestor(Node* root, Node* p, Node* q) {
    if (!root) return nullptr;
    if (p->data < root->data && q->data < root->data)
        return lowestCommonAncestor(root->left, p, q);
    if (p->data > root->data && q->data > root->data)
        return lowestCommonAncestor(root->right, p, q);
    return root;
}

BST에 노드 삽입하기

반복문을 활용한 삽입 방법입니다.

Node* insertIntoBST(Node* root, int value) {
    if (!root) return new Node(value);

    Node* curr = root;
    Node* parent = nullptr;

    while (curr) {
        parent = curr;
        if (value < curr->data) curr = curr->left;
        else curr = curr->right;
    }

    if (value < parent->data) parent->left = new Node(value);
    else parent->right = new Node(value);

    return root;
}

BST에서 노드 삭제하기

삭제 시 여러 가지 경우를 고려해야 합니다.

Node* deleteNode(Node* root, int key) {
    if (!root) return nullptr;

    if (key < root->data) root->left = deleteNode(root->left, key);
    else if (key > root->data) root->right = deleteNode(root->right, key);
    else {
        if (!root->left) return root->right;
        if (!root->right) return root->left;

        Node* minNode = root->right;
        while (minNode->left) minNode = minNode->left;

        root->data = minNode->data;
        root->right = deleteNode(root->right, minNode->data);
    }
    return root;
}

트리 자르기(Trim)

주어진 범위 외의 노드들을 제거합니다.

Node* trimBST(Node* root, int low, int high) {
    if (!root) return nullptr;

    if (root->data < low) return trimBST(root->right, low, high);
    if (root->data > high) return trimBST(root->left, low, high);

    root->left = trimBST(root->left, low, high);
    root->right = trimBST(root->right, low, high);
    return root;
}

정렬된 배열을 BST로 변환

중앙 값을 기준으로 재귀적으로 트리를 구성합니다.

Node* sortedArrayToBST(vector<int>& nums, int start, int end) {
    if (start > end) return nullptr;

    int mid = start + (end - start) / 2;
    Node* root = new Node(nums[mid]);
    root->left = sortedArrayToBST(nums, start, mid - 1);
    root->right = sortedArrayToBST(nums, mid + 1, end);
    return root;
}

Node* sortedArrayToBST(vector<int>& nums) {
    return sortedArrayToBST(nums, 0, nums.size() - 1);
}

누적 합 트리 만들기

오른쪽부터 탐색하며 누적 합을 적용합니다.

void convertToGreaterSumTree(Node* root, int& sum) {
    if (!root) return;

    convertToGreaterSumTree(root->right, sum);
    sum += root->data;
    root->data = sum;
    convertToGreaterSumTree(root->left, sum);
}

Node* bstToGst(Node* root) {
    int sum = 0;
    convertToGreaterSumTree(root, sum);
    return root;
}