Xóa node trong cây nhị phân (Binary Tree Deletion) trong C++

Giới thiệu

Xóa node trong cây nhị phân thông thường (không phải BST). Chiến lược: thay node cần xóa bằng node sâu nhất (deepest rightmost node), sau đó xóa node sâu nhất đó.

Thuật toán

1. Tìm node cần xóa (key_node) và node sâu nhất (deepest_node) bằng BFS
2. Sao chép dữ liệu từ deepest_node vào key_node
3. Xóa deepest_node khỏi cây

Mã nguồn hoàn chỉnh

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

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

Node* newNode(int data) {
    Node* temp = new Node;
    temp->data = data;
    temp->left = temp->right = NULL;
    return temp;
}

void inorder(Node* node) {
    if (!node) return;
    inorder(node->left);
    cout << node->data << " ";
    inorder(node->right);
}

void deleteDeepestNode(Node* root, Node* del_node) {
    queue q;
    q.push(root);
    
    while (!q.empty()) {
        Node* temp = q.front(); q.pop();
        
        if (temp == del_node) {
            temp = NULL;
            delete del_node;
            return;
        }
        
        if (temp->right) {
            if (temp->right == del_node) {
                temp->right = NULL;
                delete del_node;
                return;
            }
            q.push(temp->right);
        }
        
        if (temp->left) {
            if (temp->left == del_node) {
                temp->left = NULL;
                delete del_node;
                return;
            }
            q.push(temp->left);
        }
    }
}

Node* deleteNode(Node* root, int key) {
    if (!root) return NULL;
    
    // Node lá đơn lẻ
    if (!root->left && !root->right) {
        if (root->data == key) return NULL;
        return root;
    }
    
    // BFS tìm key_node và deepest_node
    queue q;
    q.push(root);
    Node* key_node = NULL;
    Node* temp = NULL;
    
    while (!q.empty()) {
        temp = q.front(); q.pop();
        
        if (temp->data == key) key_node = temp;
        
        if (temp->left) q.push(temp->left);
        if (temp->right) q.push(temp->right);
    }
    
    // temp giờ là deepest_node (node cuối cùng trong BFS)
    if (key_node) {
        int deepest_data = temp->data;
        deleteDeepestNode(root, temp);
        key_node->data = deepest_data;
    }
    
    return root;
}

int main() {
    Node* root = newNode(1);
    root->left = newNode(2);
    root->left->left = newNode(3);
    root->left->right = newNode(4);
    root->right = newNode(5);
    root->right->left = newNode(6);
    root->right->right = newNode(7);
    root->right->left->left = newNode(8);
    root->right->left->right = newNode(9);
    
    cout << "Cay truoc khi xoa: ";
    inorder(root); cout << endl;
    
    int key = 5;
    root = deleteNode(root, key);
    
    cout << "Cay sau khi xoa " << key << ": ";
    inorder(root); cout << endl;
    
    return 0;
}

Kết quả chạy chương trình

Cay truoc khi xoa: 3 2 4 1 8 6 9 5 7
Cay sau khi xoa 5: 3 2 4 1 8 6 9 7

Phân tích độ phức tạp

• Thời gian: O(n) - BFS duyệt toàn cây
• Không gian: O(w) - w = độ rộng tối đa (queue BFS)

Lưu ý quan trọng

• Chỉ áp dụng cho Binary Tree (không có tính chất BST)
• Với BST, xóa node phức tạp hơn (cần giữ tính chất BST)
• Phương pháp này thay đổi cấu trúc cây nhưng giữ được tính "hoàn chỉnh" (complete-ness) nếu cây ban đầu là complete

So sánh với xóa trong BST

Kết luận

Xóa node trong binary tree thường dùng chiến lược "thay bằng node sâu nhất" để đơn giản hóa. Không bảo toàn cấu trúc gốc nhưng đảm bảo cây không bị rỗng giữa chừng.