TAILIEUCHUNG - Cấu trúc dữ liệu : CÂY ĐỎ ĐEN part 2

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 đỏ . .

• Cơ sở dữ liệu
• Cấu trúc dữ liệu
• tài liệu Cấu trúc dữ liệu
• đề cương Cấu trúc dữ liệu
• giáo trình Cấu trúc dữ liệu
• bài giảng Cấu trúc dữ liệu
• cấu trúc dữ liệu và giải thuât
• bài giảng cấu trúc dữ liệu và giải thuât
• tài liệu cấu trúc dữ liệu và giải thuât
• giáo trình cấu trúc dữ liệu và giải thuât
• bài tập cấu trúc dữ liệu và giải thuât
• Cấu trúc dữ liệu và giải thuật
• Cấu trúc dữ liệu cây AVL
• Cấu trúc dữ liệu cây
• Thuật toán DSW
• Cây nhị phân tìm kiếm
• Cấu trúc dữ liệu cây đỏ đen
• Cấu trúc dữ liệu cho nút cây đỏ đen
• Phép biến đổi cây đỏ đen cân bằng
• bài tập cấu trúc dữ liệu
• lập trình dữ liệu
• Vị trí cấu trúc dữ liệu
• Áp dụng tin học
• Cơ sở dữ liệu
• Quan hệ giải thuật
• Cấu trúc dữ liệu cơ bản
• Đánh giá cấu trúc dữ liệu
• Định nghĩa kiểu dữ liệu
• Kiểu dữ liệu có cấu trúc
• Đánh giá thuật toán
• Thiết kế cấu trúc dữ liệu
• Bài giảng Cấu trúc dữ liệu và giải thuật
• Kiểu dữ liệu trừu tượng
• Kiểu dữ liệu cây
• Phân loại cây
• Cấu trúc dữ liệu giải thuật
• Bài giảng Cấu trúc dữ liệu giải thuật
• Ngôn ngữ lập trình
• Cấu trúc chương trình
• Cấu trúc điều khiển
• Cấu trúc dữ liệu căn bản
• Khái niệm cấu trúc dữ liệu
• Độ phức tạp thuật toán
• tiếp cận lập trình
• thuật toán
• thuật toán trong cấu trúc dữ liệu
• cấu trúc dữ liệu động
• kỹ thuật sắp xếp