BST - Thao tác xóa nút C++

Xóa nút trong cây tìm kiếm nhị phân (BST). 3 trường hợp: 1) Nút lá: xóa trực tiếp. 2) Nút 1 con: thay bằng con. 3) Nút 2 con: thay bằng kế thừa in-order (nhỏ nhất cây phải), xóa kế thừa.

Hàm xóa đệ quy

Tìm nút cần xóa. Nếu có 2 con: tìm minValueNode(cây phải), copy giá trị, đệ quy xóa nút min đó. Trả về gốc cây mới.

Ví dụ minh họa

#include <bits/stdc++.h>
using namespace std;

struct Node {
    int key;
    Node *left, *right;
};

Node* newNode(int k) {
    Node* n = new Node();
    n->key = k; n->left = n->right = nullptr;
    return n;
}

Node* insert(Node* root, int key) {
    if (!root) return newNode(key);
    if (key < root->key) root->left = insert(root->left, key);
    else if (key > root->key) root->right = insert(root->right, key);
    return root;
}

Node* minNode(Node* root) {
    while (root->left) root = root->left;
    return root;
}

Node* deleteNode(Node* root, int key) {
    if (!root) return nullptr;
    if (key < root->key) root->left = deleteNode(root->left, key);
    else if (key > root->key) root->right = deleteNode(root->right, key);
    else {
        if (!root->left) { Node* t = root->right; delete root; return t; }
        if (!root->right) { Node* t = root->left; delete root; return t; }
        Node* t = minNode(root->right);
        root->key = t->key;
        root->right = deleteNode(root->right, t->key);
    }
    return root;
}

void inorder(Node* root) {
    if (root) { inorder(root->left); cout << root->key << ' '; inorder(root->right); }
}

int main() {
    Node* root = nullptr;
    root = insert(root, 50);
    root = insert(root, 30);
    root = insert(root, 20);
    root = insert(root, 40);
    root = insert(root, 70);
    root = insert(root, 60);
    root = insert(root, 80);
    
    cout << "Inorder: "; inorder(root); cout << '\n';
    root = deleteNode(root, 20);
    cout << "Xoa 20: "; inorder(root); cout << '\n';
    root = deleteNode(root, 30);
    cout << "Xoa 30: "; inorder(root); cout << '\n';
    root = deleteNode(root, 50);
    cout << "Xoa 50: "; inorder(root);
    return 0;
}

Kết quả

Inorder: 20 30 40 50 60 70 80
Xoa 20: 30 40 50 60 70 80
Xoa 30: 40 50 60 70 80
Xoa 50: 40 60 70 80