Giải dùm bài tập CTDL và giải thuật thầy Dũng!!!

[11520132]

Xóa nút 50 làm xuất hiện dấu hiệu đen, phải thực hiện xoay và đổi màu cây con bên trái

[11520114]

Đối với xóa node 50 thì sẽ rơi vào trường hợp anh em đỏ có 2 con đen, do đó chúng ta sẽ thực hiện lần lượt:
+ Xoay 37 và 17 sau đó đảo màu của chúng
+Sau đó, KQ hiện tại rơi vào trường hợp anh em đen và có cháu họ nội đỏ, do đó ta sẽ xoay 37 và 35 1 lần nữa và đảo màu chúng, Node 29 sẽ theo màu ông nội nó là màu đen!
Kết quả sau khi xóa sẽ là hình sau:
PrtScr capture.jpg

[10520437]

Còn xóa node 50 thì sao, có "pờ rồ" nào giúp không?!

Đối với xóa node 50 thì sẽ rơi vào trường hợp anh em đỏ có 2 con đen, do đó chúng ta sẽ thực hiện lần lượt:
+ Xoay 37 và 17 sau đó đảo màu của chúng
+Sau đó, KQ hiện tại rơi vào trường hợp anh em đen và có cháu họ nội đỏ, do đó ta sẽ xoay 37 và 35 1 lần nữa và đảo màu chúng, Node 29 sẽ theo màu ông nội nó là màu đen!
Kết quả sau khi xóa sẽ là hình sau:
[ATTACH=CONFIG]3173[/ATTACH]

Kết quả của minh cũng tương tự.

Có 2 trường hợp:
- Nút xóa có 2 con thì xóa bình thường như cây thông thường, không làm ảnh hưởng tính đỏ đen
- Nút có 1 nút con hoặc "vô sinh" thì sẽ có 5 trường hợp để lập:
+ Anh em nút xóa là đỏ: đổi anh em với cha, đổi màu luôn.
+ Cha đen, Anh em đen và có 2 con đen cũng đen: đổi màu anh em đó là ok
+ Cha đỏ, anh em và 2 con đều đen: đổi màu cha và anh em
+ Anh em có con trái đỏ: lật hằng con trái đỏ đó lên làm cha của anh em đó, rồi đổi màu 2 đứa luôn
+ Anh em có con phải là đỏ, hằng anh em đó là con phải của cha: lật anh em đó làm cha luôn, hằng con nó đổi sang màu đen

[11520377]

Capture.jpg
Cây như thế có vi phạm tính chất gì ko?!
Lần đầu mình cũng xoay giống như các bạn, nhìn lại thì thấy ko cần nữa
Nhưng mới đọc lại 1 tài liệu thì thấy vẫn cần phải xoay.hic, tại sao vậy nhỉ??

[11520114]

[ATTACH=CONFIG]3174[/ATTACH]
Cây như thế có vi phạm tính chất gì ko?!
Lần đầu mình cũng xoay giống như các bạn, nhìn lại thì thấy ko cần nữa
Nhưng mới đọc lại 1 tài liệu thì thấy vẫn cần phải xoay.hic, tại sao vậy nhỉ??

Không vi phạm tính chất gì bạn à! 1 tính chất quan trọng trong cây đỏ đen là chiều cao đen (số node đen trên các nhánh cho đến 1 node la bất kì) phải bằng nhau.
Bạn cứ làm đúng như 5 trường hợp thêm là được!

TH1 Node gốc luôn đen
TH2 Cha đen -> thêm bình thường
TH3 Cha đỏ, chú đỏ: Đổi màu cha, chú, ông nội. Xét ông nội từ TH1
TH4 Cha đỏ, chú đen, cháu ngoại: Xoay 2 cha con -> Qua TH5
TH5 Cha đỏ, chú đen, cháu nội : Xoay cha, con, ông nội. Đổi màu cha, ông nội

[11520215]

số 37 với 90 mình lại ra màu đỏ. cả 2 đáp án mình đều thấy hợp lý. h sao ta?

cho mình hỏi, cây đỏ đen của mình ra như vậy có đúng không.

[11520377]

uhm, mình hiểu rùi, nhưng mình không thích việc nhớ tất cả các TH, tóm lại là, xoay sao thì xoay, đổi màu sao đó tùy, miễn ko vi phạm tính chất gì là ok đúng hok.hì, sáng đề thầy Dũng cho dễ nhỉ,

[10520437]

[ATTACH=CONFIG]3174[/ATTACH]
Cây như thế có vi phạm tính chất gì ko?!
Lần đầu mình cũng xoay giống như các bạn, nhìn lại thì thấy ko cần nữa
Nhưng mới đọc lại 1 tài liệu thì thấy vẫn cần phải xoay.hic, tại sao vậy nhỉ??

Chỉ xóa nút 50 mà không xoay lại là sai rồi đó bạn.
Bạn xem kĩ, nút con phải NULL của nút 37 lúc này đường đi chỉ có 3 đen, trong khi các nút khác đều là 4 đen (vi phạm quy tắc Đường đi đen đến các là đều bằng nhau)
-p/s Mỗi nút nằm ở cuối trong cây trên, nếu không có nút nào gắn vô, đều mặc định có 2 nút con đen (mang giá trị NULL) bên dưới. Có thể hiểu là Nút 37 có con trái là 17 Red, và nút con phải là NULL Black. Viết kiểu trên là do ta viết vấn tắc để gọn hơn, nhưng khi nhắc đến cây đỏ đen ta phải mặc định điều đó.

[11520114]

uhm, mình hiểu rùi, nhưng mình không thích việc nhớ tất cả các TH, tóm lại là, xoay sao thì xoay, đổi màu sao đó tùy, miễn ko vi phạm tính chất gì là ok đúng hok.hì, sáng đề thầy Dũng cho dễ nhỉ,

Đề này thầy cho khá dễ, thầy bỏ luôn phần xóa node cây đỏ đen và trình bày giải thuật câu 1 luôn.

[11520317]

Đề này thầy cho khá dễ, thầy bỏ luôn phần xóa node cây đỏ đen và trình bày giải thuật câu 1 luôn.

Đôi khi đề dễ qúa cũng chán....