Xóa nút trong BST trong C++

Cho cây tìm kiếm nhị phân (BST) và khóa k. Xóa khóa k khỏi BST và trả về BST đã cập nhật. Ví dụ: xóa khóa 3 từ cây cho kết quả cây mới.

Giải thuật

• Hàm deleteRoot(root) xóa nút gốc:
  • Nếu root == null trả về null.
  • Nếu không có cây con phải: trả về cây con trái.
  • Tìm nút kế thừa inorder x của gốc.
  • Gán x->left = root->left.
  • Trả về root->right.
• Hàm deleteNode(root, key):
  • Nếu root == null hoặc root->val == key trả về deleteRoot(root).
  • curr := root.
  • Vòng lặp vô tận:
    • x := curr->val.
    • Nếu key < x:
      • Nếu curr->left == null hoặc curr->left->val == key: curr->left = deleteRoot(curr->left), thoát.
      • curr = curr->left.
    • Ngược lại:
      • Nếu curr->right == null hoặc curr->right->val == key: curr->right = deleteRoot(curr->right), thoát.
      • curr = curr->right.
  • Trả về root.

Ví dụ mã C++

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

class TreeNode {
public:
    int val;
    TreeNode *left, *right;
    TreeNode(int data) { val = data; left = NULL; right = NULL; }
};

class Solution {
public:
    TreeNode* deleteNode(TreeNode* root, int key) {
        if (!root || root->val == key) return deleteRoot(root);
        TreeNode* curr = root;
        while (true) {
            int x = curr->val;
            if (key < x) {
                if (!curr->left || curr->left->val == key) {
                    curr->left = deleteRoot(curr->left);
                    break;
                }
                curr = curr->left;
            } else {
                if (!curr->right || curr->right->val == key) {
                    curr->right = deleteRoot(curr->right);
                    break;
                }
                curr = curr->right;
            }
        }
        return root;
    }
    TreeNode* deleteRoot(TreeNode* root) {
        if (!root) return NULL;
        if (!root->right) return root->left;
        TreeNode* x = root->right;
        while (x->left) x = x->left;
        x->left = root->left;
        return root->right;
    }
};

Đầu vào

[5,3,6,2,4,null,7] 3

Đầu ra

[5, 4, 6, 2, null, 7, ]