Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
thực hiện tương đương với một hoạt động phân chia. Cụ thể, chúng tôi làm một recoloring: màu v và w màu đen và màu đỏ u cha mẹ của họ (trừ khi u là gốc rễ, trong trường hợp này, nó là màu đen). Có thể rằng, sau khi recoloring như vậy, màu đỏ lại xuất hiện vấn đề tăng gấp đôi, mặc dù cao hơn trong cây T, | perform the equivalent of a split operation. Namely we do a recoloring we color v and w black and their parent u red unless u is the root in which case it is colored black . It is possible that after such a recoloring the double red problem reappears albeit higher up in the tree T since u may have a red parent. If the double red problem reappears at u then we repeat the consideration of the two cases at u. Thus a recoloring either eliminates the double red problem at node z or propagates it to the grandparent u of z. We continue going up T performing recolorings until we finally resolve the double red problem with either a final recoloring or a trinode restructuring . Thus the number of recolorings caused by an insertion is no more than half the height of tree T that is no more than log w 1 by Proposition 10.9. Figure 10.29 Recoloring to remedy the double red problem a before recoloring and the corresponding 5-node in the associated 2 4 tree before the split b after the recoloring and corresponding nodes in the associated 2 4 tree after the split . 646 Figures 10.30 and 10.31 show a sequence of insertion operations in a red-black tree. Figure 10.30 A sequence of insertions in a red- black tree a initial tree b insertion of 7 c insertion of 12 which causes a double red d after restructuring e insertion of 15 which causes a double red f after recoloring the root remains black g insertion of 3 h insertion of 5 i insertion of 14 which causes a double red j after restructuring k insertion of 18 which causes a double red l after recoloring. Continues in Figure 10.31. 647 Figure 10.31 A sequence of insertions in a red- black tree m insertion of 16 which causes a double red n after restructuring o insertion of 17 which causes a double red p after recoloring there is again a double red to be handled by a restructuring q after restructuring. Continued from Figure 10.30. .
