Hình 6. Ba khả năng sau khi chèn nút i) Khả năng 1: P đen ii) Khả năng 2: P đỏ và X là cháu ngoại của G iii) Khả năng 3: P đỏ và X là cháu nội của G Chúng ta sẽ xét các khả năng trên một cách cụ thể như sau: i) Khả năng 1: P đen P đen là trường hợp đơn giản. Node thêm vào luôn đỏ. Nếu node cha đen, không có xung khắc đỏ-đỏ (quy tắc 3), và không có việc cộng thêm vào số node đen (quy tắc 4). Do vậy,. | Hình 6. Ba khả năng sau khi chèn nút i Khả năng 1 P đen ii Khả năng 2 P đỏ và X là cháu ngoại của G iii Khả năng 3 P đỏ và X là cháu nội của G Chúng ta sẽ xét các khả năng trên một cách cụ thể như sau i Khả năng 1 P đen P đen là trường hợp đơn giản. Node thêm vào luôn đỏ. Nếu node cha đen không có xung khắc đỏ-đỏ quy tắc 3 và không có việc cộng thêm vào số node đen quy tắc 4 . Do vậy không bị vi phạm quy tắc về màu. Thao tác chèn đã hoàn tất. ii Khả năng 2 P đỏ và X là cháu ngoại của G Nếu node P đỏ và X là node cháu ngoại ta cần một phép quay đơn giản và một vài thay đổi về màu. Bắt đầu với giá trị 50 tại node gốc và chèn 8 các node 25 75 và 12. Ta cần phải làm một phép lật màu trước khi chèn node 12. Bây giờ chèn node mới X là 6. hình 7a. xuất hiện lỗi cha và con đều đỏ vì vậy cần phải có các thao tác như sau hình 7 Trong trường hợp này ta có thể áp dụng ba bước để phục hồi tính đỏ-đen và làm cho cân bằng cây. Sau đây là các bước ấy -Đổi màu node G - node ông bà của node X trong thí dụ này là node 25 . -Đổi màu node P - node cha của node X node 12 -Quay với node G 25 ở vị trí đỉnh theo huớng làm nâng node X lên 6 . Đây là một phép quay phải. Khi ta hoàn tất ba buớc trên sẽ bảo toàn cây đỏ đen. Xem hình 7b. Trong thí dụ này node X là node cháu ngoại của một node con trái. Có một trường hợp đối xứng khi node X là node cháu ngoài nhưng của một node con phải. Thử làm điều này bằng cách tạo nên cây 50 25 75 87 93 với phép lật màu khi cần . Chỉnh sửa cây bằng cách đổi màu node 75 và 87 và quay trái với node 75 là node đỉnh. Một lần nữa cây lại được cân bằng. 9 Hình 7. Node P đỏ và X là node cháu ngoại iii Khả năng 3 P đỏ và X là cháu nội của G Nếu node P đỏ và X là node cháu nội chúng ta cần thực hiện hai phép quay và một vài phép đổi màu. Cây đỏ đen được tạo thành từ các node 50 25 75 12 và 18. cần phải lật màu trước khi chèn node 12 . Xem hình 8a. Lưu ý là node 18 là node cháu nội. Node này và node cha đều đỏ cha và con đều đỏ . .
