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

1 CÂY ĐỎ ĐEN 1 Nộ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 2 Câ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 17 5 15 35 22 42 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. 4 Giới thiệu Cá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. 2 1 7 11 14 5 8 15 7 Mỗi nút là đỏ hoặc đen 8 Nút gốc và các nút lá (NIL) có màu đen 9 Nếu một nút đen, các con của nó có màu đỏ. 10 Phé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 • 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. X X Y Y 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à node cha của X. • G là node ông bà của X (node cha của P). • Trong quá trình thêm vào node mới có thể vi phạm các quy tắc của cây đỏ đen, chúng ta sẽ thực hiện các thao tác: – Các phép lật màu trên đường đi xuống. – Các phép quay khi node đã được chèn. – Các phép quay trên đường đi xuống. 15 Các phép lật màu trên đường đi xuống • Phép thêm vào trong cây RB như trên cây TKNP: đi theo đường dẫn từ node gốc đến vị trí cần chèn. • Tuy nhiên, trong cây đỏ đen, đến được điểm chèn là phức tạp bởi các phép lật màu và quay. • Để bảo đảm không vi phạm các quy tắc màu  tiến hành các phép lật màu khi cần. • Qui tắc phép lật màu: Nếu phép thêm vào làm xuất hiện tình trạng một node đen có hai node con đỏ, chúng ta đổi các node con thành đen và node cha thành đỏ (trừ khi node cha là node gốc, nó vẫn giữ màu là đen). 16 Các phép lật màu trên đường đi xuống (a) trước khi lật màu (b) sau khi lật màu x1 p x2 p x1 x2 17 Các phép lật màu trên đường đi xuống • Như vậy phép lật màu không vi phạm quy tắc 4. • Quy tắc 3 ( node con và node cha không thể đồng màu đỏ) lại có khả năng bị vi phạm. – Nếu node cha của P là đen  không có vấn đề vi phạm khi P chuyển từ đen sang đỏ, – Nếu node cha của P là đỏ, thì sau khi đổi màu, ta sẽ có hai node đỏ trên một hàng • Giải quyết: cần phải được chuẩn bị trước khi đi xuống theo cây để chèn nút mới  giải quyết bằng một phép quay. • Đối với node gốc thì phép lật màu node gốc và hai node con của nó vẫn làm cho node gốc cũng như hai node con có màu đen. Điều này tránh sự vi phạm quy tắc 2 và quy tắc 3 (xung đột đỏ-đỏ). Trong trường hợp này, chiều cao đen trên mỗi đường đi từ node gốc tăng lên 1, do đó quy tắc 4 cũng không bị vi phạm. 18 Các phép quay khi chèn node 19 Ba khả năng sau khi chèn nút (1) Khả năng 1: P đen (2) Khả năng 2: P đỏ và X là cháu ngoại của G (3) Khả năng 3: P đỏ và X là cháu nội của G G P X G P X P X G 20 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. G P 25 50 75 12 X 21 Khả năng 2: P đỏ và X là cháu ngoại của G • P đỏ và X là cháu ngoại của G, Ta cần một phép quay đơn giản và một vài thay đổi về màu. • X là nút cháu ngoại, chèn node mới X (đỏ)  Xuất hiện lỗi: cha và con đều đỏ. • Trong trường hợp này, áp dụng ba bước để phục hồi tính đỏ-đen và làm cho cân bằng cây: – Đổi màu node G - node ông bà của node X (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 hướng làm nâng node X lên (6). Đây là một phép quay phải. 22 P đỏ và X là cháu ngoại của G – Ví dụ G P 25 50 75 6 12 X (1) Đổi màu (2) Đổi màu (3) Xoay G P 25 50 75 6 12 (1) Đổi màu (2) Đổi màu 23 P đỏ và X là cháu ngoại của G – Ví dụ G P 25 50 75 6 12 X (3) Xoay G P 12 50 75 6 25 X 24 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, cần thực hiện hai phép quay và một vài phép đổi màu. • X là nút cháu nội, chèn node mới X (đỏ)  Xuất hiện lỗi: cha và con đều đỏ. • Hai phép quay: – Phép quay đầu biến X từ một node cháu nội thành node cháu ngoại. – Phép quay thứ 2: phép quay, với node ông bà ở đỉnh, như đã làm trước đây. • Chúng ta cũng cần tô màu lại các nút. Ta làm điều này trước khi làm bất cứ phép quay nào. 25 Khả năng 3: P đỏ và X là cháu nội của G • Các bước là: – Đổi màu node ông bà của node X ( node 25). – Đổi màu node X (không phải màu của node cha; node X đây là node 18). – Quay với node P - node cha của X - ở đỉnh (không phải với node ông bà; node cha đây là 12). – Quay lần nữa với node ông bà của X (25) ở đỉnh, về hướng nâng X lên (quay phải). 26 P đỏ và X là cháu nội của G – ví dụ G P 25 50 75 18 12 X (1) Đổi màu (2) Đổi màu (3) Xoay 25 50 75 12 18 (1) Đổi màu (2) Đổi màu G P X 27 P đỏ và X là cháu nội của G – ví dụ 25 50 75 12 18 (3) Xoay G P X 25 50 75 18 12 28 Khả năng 3: P đỏ và X là cháu nội của G (2) 18 12 25 75 50 25 50 75 18 12 (4) Xoay 29 Ví dụ: đưa các nút 4,7,12, 15, 3, 5, 14, 18, 16, 17 vào cây đỏ đen 7 4 12 12 7 4 15 12 7 4 15 3 5 30 12 7 4 15 3 5 14 7 4 3 5 14 12 15 18 7 4 3 5 14 12 15 18 31 7 4 3 5 14 12 15 18 16 7 4 3 5 14 12 16 18 15 17 32 7 4 3 5 14 12 16 18 15 17 7 4 3 5 14 12 16 18 15 17 33 Ví dụ: Chèn một nút vào cây đỏ đen • Lần lượt chèn vào các nút có giá trị: 50, 75, 25, 80, 100, 110, 105 34 35 36 37 38 39 40 41 42 43 44 45 Ví dụ: xóa các node trên cây đỏ đen 14 7 16 4 12 15 18 3 5 17 3 14 7 16 4 12 15 18 5 17 Xóa nút 3 46 14 7 16 4 12 15 18 5 17 Xóa nút 12 14 7 16 4 15 18 5 17 14 5 16 4 15 18 7 17 restructuring 47 14 5 16 4 15 18 7 17 Xóa nút 17 14 5 16 4 15 18 7 17 Xóa nút 18 14 5 16 4 15 7 recoloring 14 5 16 4 15 7 48 14 5 16 4 15 7 Xóa nút 15 14 5 16 4 7 Xóa nút 16 14 5 4 7 adjustment 14 5 4 7 14 5 4 7 recoloring 49 Bài tập áp dụng • Cho cây đỏ đen như sau: 50 Bài tập áp dụng • Anh (chị) trình bày từng bước xây dựng cây đỏ đen ứng với các thao tác sau: – Thêm các nút: 50, 75, 25, 60, 10, 20, 80, 100, 40, 45 – Hủy các nút: 80, 20, 50, 25 51