Xóa chuỗi số thứ tự từ BST

Question

Tôi đã có câu hỏi này trong một kỳ thi và tôi không thể tìm thấy câu trả lời nhanh.

Có một mảng A chứa một số số thứ tự A = [1,3,6,9,11] và BST có số là khóa. Tôi phải cung cấp một thuật toán đệ quy hiệu quả để xóa các số trong A từ BST.

Sự cố tôi không có trong việc xóa các nút, nhưng trong cách sử dụng thực tế là mảng được sắp xếp để xóa các nút.

Ai đó có thể giúp tôi với một số gợi ý không?

Answer 1

Dưới đây là một cách tiếp cận có thể có.

Bạn có thể đồng thời duyệt cả BST (sử dụng standard recursive algorithm) và A (từ trái sang phải). Mỗi lần truyền tải sẽ mang lại các yếu tố theo thứ tự tăng dần. Bạn đang tìm kiếm các yếu tố phù hợp để xóa chúng khỏi cây.

Thuật toán ngây thơ sẽ có độ phức tạp thời gian O(size(BST)).

Trong một số trường hợp, bạn có thể tránh nhìn vào cây con trái hoàn toàn: giá trị của nút "hiện tại" trong cây cho bạn giới hạn trên trên các giá trị trong cây con trái, vì vậy nếu giá trị này nhỏ hơn giá trị của phần tử "hiện tại" của A, bỏ qua cây con bên trái.

Bạn cũng có thể dừng thuật toán ngay khi bạn đã cạn kiệt A.

Answer 2

Để cho BST được biểu thị bằng nút gốc của nó.

Chức năng delete-array-from-bst với đối số array và bst là:

• nếu array hoặc bst trống: return
• chia mảng thành ba subarrays, các giá trị nhỏ hơn, bình đẳng, và lớn hơn bst Giá trị nút gốc
• recurse trên subarray với các giá trị nhỏ hơn với BST bên trái, sau đó trên subarray với các giá trị lớn hơn trên BST phụ phải, cuối cùng xóa giá trị bằng nhau, nếu appli cable

Tách mảng là tìm kiếm nhị phân, do đó bạn không cần phải so sánh từng giá trị mảng với nút gốc. Các mạng con có thể chia sẻ cấu trúc với mảng ban đầu. Xóa giá trị bằng nhau cuối cùng đảm bảo rằng bạn không nhấn trường hợp xóa tồi tệ nhất cho mỗi giá trị trong mảng.