Để xóa một nút trong cây nhị phân, chúng ta phải tìm kiếm nút đó là gì. Đó là có thể trong tối thiểu O (log N) và tối đa O (N). Tùy thuộc vào nút, chúng ta phải sắp xếp lại các con trỏ. Làm cách nào để tính toán độ phức tạp của thời gian đó.Độ phức tạp về thời gian của việc xóa một nút trong cây nhị phân
Hầu hết sự phức tạp là tìm kiếm nút. Một khi nó đã được tìm thấy - miễn là nút cha được giữ lại, nó chỉ là một vài nhiệm vụ nữa để xóa nút. Vì vậy, nó là một thứ tự liên tục.
Điều đó tùy thuộc vào cách bạn thực hiện xóa. Cách phổ biến nhất liên quan đến việc tìm kiếm người kế thừa của nút, sau đó thay thế nút với người kế nhiệm đó. Điều này có thể được thực hiện trong O (h), trong đó h là chiều cao của cây. Trong trường hợp xấu nhất này là O (n), nhưng trong một cây cân bằng là trường hợp xấu nhất O (lg n).
Bạn nhận được "thời gian tìm kiếm tồi tệ nhất ở mức tối đa O (N)" ở đâu? Điều đó sẽ không bao giờ xảy ra trong BST. Tại tồi tệ nhất, nó phải là tối đa O (h) cho tìm kiếm và xóa, trong đó 'h' là chiều cao của cây. Xem số này helpful article.
O (h) có thể là O (n) trong cây thoái hóa bệnh. – templatetypedef
Có phức tạp trường hợp tốt nhất là O (logn) (khi hoàn toàn cân bằng) và
tồi tệ nhất trường hợp phức tạp là O (n)
1 - 2 - 3 - 4
Nhưng vấn đề chính với xóa BST (Hibbard Deletion) là nó không đối xứng. Sau nhiều lần chèn và xóa BST trở nên ít cân bằng hơn. Các nhà nghiên cứu đã chứng minh rằng sau khi đủ số lượng chèn ngẫu nhiên và chiều cao xóa của cây trở thành sqrt (n). vì vậy bây giờ mọi hoạt động (tìm kiếm, chèn, xóa) sẽ mất sqrt (n) thời gian không tốt so với O (logn).
Đây là vấn đề mở rất dài (khoảng 50 năm) để xóa đối xứng hiệu quả đối với BST. đối với cây cân bằng được đảm bảo, chúng tôi phải sử dụng RedBlack Tree, v.v.
+1, Đẹp và ngắn gọn. –