Có lẽ bạn cần suy nghĩ kỹ hơn về việc triển khai danh sách được liên kết. Bạn chỉ ra rằng việc xóa bỏ lười biếng sẽ KHÔNG giúp được theo bất kỳ cách nào vì thời gian tìm kiếm là tất cả thời gian cần thiết để thực hiện xóa.
Hãy suy nghĩ về những gì cần để thực sự XÓA một mục khỏi danh sách được liên kết. lưu ý: điều này giả định danh sách liên kết SINGLY (không phải danh sách liên kết kép) 1) Tìm mục cần xóa (vì đây là danh sách được liên kết SINGLE, bạn luôn phải tìm kiếm, vì bạn cần mục PREV) 2) Keep Các phần tử PREV và TIẾP THEO 3) Sửa phần tử "PREV" để trỏ đến phần tử TIẾP THEO - do đó, cách ly phần tử CURRENT 3.5) trong danh sách được liên kết kép, bạn cũng phải chăm sóc phần tử TIẾP THEO trỏ ngược lại với phần tử PREV. 4) Giải phóng bộ nhớ được liên kết với phần tử CURRENT
Bây giờ, quy trình xóa lười là gì? --- ngắn hơn nhiều 1) Tìm mục cần xóa (bạn thậm chí có thể không thực hiện tìm kiếm, vì bạn đã có con trỏ đến đối tượng bạn muốn xóa?) 2) đánh dấu mục để xóa.
*) Chờ cho "Thu gom rác" chủ đề để chạy và thực sự thực hiện các bước còn lại khi hệ thống đang "nhàn rỗi"
Một cây nhị phân thực hiện như một danh sách liên kết trong đó mỗi phần tử có một trái và một bên phải - tuy nhiên, bạn vẫn thực hiện các bước tương tự trong tìm kiếm. Tìm kiếm cây nhị phân chỉ hiệu quả hơn với O (Log (n)) tôi tin. Tuy nhiên, việc xóa từ các lệnh này trở nên phức tạp hơn vì bạn có nhiều con trỏ hơn để giải quyết (cả "TRÁI" và "QUYỀN") - vì vậy sẽ có thêm hướng dẫn để khắc phục, đặc biệt khi bạn xóa nút cây có con trỏ đến các nút cho cả hai bên trái và bên phải - một trong số chúng sẽ cần được nâng cấp lên thư mục gốc mới - tuy nhiên, điều gì sẽ xảy ra nếu chúng cũng có cả con trỏ trái và phải được gán? nút "trái/phải" gốc ở đâu? - Bạn phải cân bằng lại cây tại thời điểm này. Vì vậy, có một khoản tiết kiệm đáng kể bằng cách đánh dấu xóa từ góc nhìn của người dùng và có một bộ sưu tập rác "nhàn rỗi" để xử lý các chi tiết bộ nhớ (vì vậy người dùng không phải đợi điều đó).