Bài giảng Phân tích thiết kế và giải thuật - Chương 6: Cây đỏ đen

Bài giảng "Phân tích thiết kế và giải thuật - Chương 6: Cây đỏ đen" cung cấp cho người học các kiến thức: Giới thiệu, định nghĩa và tính chất cây đỏ đen, phép quay, cân bằng lại theo kiểu bottom-up, thêm nút mới, loại bỏ nút, tính hiệu quả của cây đỏ đen
Nội dung trích xuất từ tài liệu:
Bài giảng Phân tích thiết kế và giải thuật - Chương 6: Cây đỏ đenCÂY ĐỎ ĐEN 1 1Nội dung• Giới thiệu• Định nghĩa và tính chất cây đỏ đen• Phép quay, cân bằng lại theo kiểu bottom-up• Thêm nút mới, Loại bỏ nút• Tính hiệu quả của cây đỏ đen• Cài đặt 2Cây tìm kiếm nhị phân(binary search tree)• Cây tìm kiếm nhị phân (TKNP) là cây nhị phân mà khoá tại mỗi nút lớn hơn khoá của tất cả các nút thuộc cây con bên trái và nhỏ hơn khoá của tất cả các nút thuộc cây con bên phải. 20 10 35 5 17 22 42 15 37 3 Giới thiệu• Cây tìm kiếm nhị phân thuận lợi lớn về mặt lưu trữ và truy xuất dữ liệu trong phép toán tìm kiếm, thêm vào hay loại bỏ một phần tử.  cây TKNP là một CTDL tốt.• Hạn chế: – Nếu dữ liệu được chèn vào theo thứ tự đã đuợc sắp xếp sẽ không hiệu quả. Khi đó cây nhị phân trở nên không cân bằng.(Lệch về bên trái hoặc bên phải). – Khi cây không cân bằng, khả năng tìm kiếm nhanh (hoặc chèn hoặc xóa) một phần tử đã cho  hạn chế• Cây không cân bằng: => giải quyết: đó là cây đỏ đen, là cây tìm kiếm nhị phân có thêm một vài đặc điểm. 4Giới thiệuCác node được chèn theo thứ tự tăng dần 5Định nghĩa Cây đỏ đen (red-black trees) • Cây đỏ đen là một cây nhị phân tìm kiếm (BST) với các thuộc tính: 1. Mọi node đều được tô màu đỏ hoặc màu đen. 2. Node gốc và các node lá (NIL) phải luôn luôn đen. 3. Nếu một node là đỏ, những node con của nó phải là đen.  Trên mọi đường dẫn từ gốc đến nút lá không có 2 node đỏ liên tiếp 4. Mọi đường dẫn từ gốc đến một lá phải có cùng số lượng node đen. 6 Định nghĩa cây đỏ đen• Số lượng node đen trên một đường dẫn từ gốc đến lá được gọi là chiều cao đen (black height). Ta có thể phát biểu quy tắc 4 theo một cách khác là mọi đường dẫn từ gốc đến lá phải có cùng chiều cao đen. 11 2 14 1 7 15 5 8 7Mỗi nút là đỏ hoặc đen 8Nút gốc và các nút lá (NIL) có màu đen 9Nếu một nút đen, các con của nó có màu đỏ. 10Phép quay (rotations)• Để cân bằng cây  tái sắp xếp node về mặt vật lý. – Nếu tất cả các node nằm bên trái node gốc  di chuyển một vài node qua bên phải. Điều này làm được nhờ các phép quay..• Phép quay là cách tái sắp xếp các nút, chúng được thiết kế làm các công việc sau: – Nâng một số node lên và hạ một số khác xuống để giúp cân bằng cây. – Bảo đảm những tính chất của cây TKNP không bị vi phạm.• Phép quay phải đảm bảo tính chất của cây TKNP. 11 Phép quay Y X X Y• Kết quả của 2 phép quay, thứ tự duyệt cây trong phép duyệt không thay đổi A x B y C• Nếu làm phép quay phải: node đỉnh phải có node con trái. Nếu làm phép quay trái, node đỉnh phải có node con phải. 12 Thêm node mới• Ý tưởng: Chèn x vào cây và x có màu đỏ. Chỉ có thuộc tính thứ 3 có thể bị vi phạm. Có thể điều chỉnh cây bằng cách tô lại màu và quay cho đến khi hết vi phạm. – Thực hiện việc tìm kiếm bình thường để tìm nút rỗng nơi phải chèn khóa mới vào – Thay node rỗng bằng nút lá với khóa mới – Tô màu đỏ cho nút mới này – Thêm vào 2 nút con rỗng (NULL - màu đen) – Nếu nút cha của nút mới có màu đỏ, ta có 2 nút đỏ kề nhau. Vi phạm tính chất cây đỏ đen  Tổ chức lại cây 13 Thêm nút mới• Qui trình chèn: – Gọi X, P, và G để chỉ định nhãn những node liên quan – X là node vi phạm quy tắc ( X có thể là một node mới được chèn, hoặc node con khi node cha và node con xung đột đỏ-đỏ, nghĩa là có cùng màu đỏ). • X là một node cho trước. • P là node cha của X. • G là node ông bà của X (node cha của P). 14 Thêm nút mới• Qui trình chèn: – Gọi X, P, và G để chỉ định nhãn những node liên quan – X là node vi phạm quy tắc ( X có thể là một node mới được chèn, hoặc node con khi node cha và node con xung đột đỏ-đỏ, nghĩa là có cùng màu đỏ). • X là một node cho trước. • P là ...