Ok Tôi sẽ thử điều này, và có lẽ những người tốt khác của SO có thể giúp đỡ. Bạn biết làm thế nào một cách suy nghĩ của các nút màu đỏ là như các chỉ số của
- nơi có có sự mất cân bằng/nút mới trong cây, và
- bao nhiêu sự mất cân bằng có.
Đây là lý do tại sao tất cả các nút mới đều có màu đỏ. Khi các nút (cục bộ) cân bằng, chúng trải qua một màu lật, và màu đỏ được chuyển lên cho cha mẹ, và bây giờ cha mẹ có thể trông mất cân đối so với anh chị em của nó.
Như minh hoạ, hãy xem xét một tình huống mà bạn đang thêm các nút từ lớn hơn đến nhỏ hơn. Bạn bắt đầu với nút Z mà bây giờ là gốc và là màu đen. Bạn thêm nút Y, màu đỏ và là một con trái của Z. Bạn thêm một chữ X màu đỏ làm con của Z, nhưng bây giờ bạn có hai màu đỏ liên tiếp, vì vậy bạn xoay phải, tô màu và bạn có cân bằng, tất cả màu đen (không có sự mất cân bằng/"nút mới"!) cây bắt nguồn từ Y [bản vẽ đầu tiên]. Bây giờ bạn thêm W và V, theo thứ tự đó. Lúc đầu, cả hai đều là màu đỏ [bản vẽ thứ hai], nhưng ngay lập tức V/X/W được xoay sang phải và màu bị lật, sao cho chỉ X là màu đỏ [bản vẽ thứ ba]. Điều này quan trọng: X là màu đỏ chỉ ra rằng trái subtree của Y là không cân bằng bởi 2 nút, hoặc, nói cách khác, có hai nút mới trong subtree trái. Vì vậy, chiều cao của các liên kết màu đỏ là số lượng các nút mới, có khả năng không cân bằng: có 2^chiều cao của các nút mới trong cây con màu đỏ.
Note thế nào khi thêm nút, đỏ luôn được thông qua lên: trong lật màu, hai đứa con đỏ trở thành màu đen (= cân bằng cục bộ) trong khi màu đỏ mẹ. Về cơ bản những gì xóa bỏ, là đảo ngược quá trình này. Giống như một nút mới có màu đỏ, chúng tôi cũng luôn muốn xóa một nút màu đỏ. Nếu nút không phải là màu đỏ, sau đó chúng tôi muốn làm cho nó màu đỏ đầu tiên. Điều này có thể được thực hiện bằng cách lật màu (tình cờ, đây là lý do tại sao màu lật trong mã trên trang 3 thực sự là màu trung tính). Vì vậy, nếu đứa trẻ chúng tôi muốn xóa là màu đen, chúng tôi có thể làm cho nó màu đỏ bằng cách lật màu mẹ của nó. Bây giờ đứa trẻ được đảm bảo là màu đỏ.
Vấn đề tiếp theo cần giải quyết là khi chúng tôi bắt đầu xóa, chúng tôi không biết liệu nút đích có bị xóa hay không. Một chiến lược sẽ là tìm ra đầu tiên. Tuy nhiên, theo đọc của tôi về tham chiếu đầu tiên của bạn, chiến lược được chọn có để đảm bảo rằng nút đã xóa có thể được làm đỏ, bằng cách "đẩy" một nút màu đỏ xuống trước nút tìm kiếm khi chúng tôi đang tìm kiếm trên cây cho nút bị xóa. Điều này có thể tạo ra các nút màu đỏ không cần thiết mà thủ tục fixUp() sẽ giải quyết trên đường sao lưu cây. fixUp() có lẽ duy trì các bất biến LLRBT thông thường: "không có nút màu đỏ liên tiếp" và "không có nút màu đỏ bên phải."
Không chắc chắn liệu điều đó có hữu ích hay không, hoặc nếu chúng ta cần kiểm tra mã chi tiết hơn.
Đó là ... phức tạp. – Thomas
@Thomas, rất nhiều RB hoặc LLRB chỉ nói về chèn, không ai thực sự nói về xóa –