Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 3: Cây cân bằng Balanced trees

Nội dung text: Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 3: Cây cân bằng Balanced trees

1. Double rotation-LR LR 11
2. Double rotation-RL RL 12
3. Các định lý ⚫ 4 phép quay LL, RR, LR, và RL phủ toàn bộ các trường hợp cần phải cân bằng lại ⚫ Trường hợp cây AVL trở nên mất cân bằng khi thêm một nút chỉ cần một phép quay để làm cho cây cân bằng lại. ⚫ Trường hợp cây AVL trở nên mất cân bằng khi Xóa một nút có thể cần tới O(log n) phép quay để làm cho cây cân bằng lại (từ nút mất cân bằng đến gốc). 13
4. Ví dụ thêm 1 khóa LL Thêm khóa 1 Thêm khóa 32 14
5. Xóa nút 4 4 RR rotation LL rotation
6. AVL Trees Implementation in java ⚫ See 3.6.1 chapter 3, Algorithm design, Goodrich 16
7. d-cây ⚫ Cây đa phân: là cây mỗi nút có ⚫ Mỗi d-nút (có các nút con từ hai con trở lên. v1, ,vd) sẽ lưu d-1 phần tử ⚫ Cây có thứ tự: các nút có tt dạng (k1,x1), , (kd-1,xd-1) và ⚫ Nút v là d-nút: V có d≥2 nút con mỗi phần tử (k,x) lưu trong ⚫ Cây tìm kiếm đa phân (multi- cây con gốc vi phải thỏa way search tree) là cây có thứ mãn: ki-1 ≤ k < ki tự với các tính chất sau: – Mỗi nút trong là một d-nút có ít ( k0= -∞ còn kd = +∞) nhất 2 nút con. ⚫ Định lý: cây tìm kiếm đa – Mỗi nút lưu trữ một tập hợp các phần tử dạng (k,x), phân chứa n phần tử ⚫ k là khóa có (n+1) nút ngoài ⚫ x là giá trị kết hợp với khóa 17
8. Ví dụ: 3-cây 22 5 10 25 3 4 6 8 14 23 24 27 11 13 17 Xem thêm các giải thuật B-Cây trong giáo trình GT của Nguyễn Văn Linh 18
9. Cây 2-3-4 hoặc cây (2,4) ⚫ Cây (2,4) là 4-cây cân bằng: 25 – Mỗi nút có tối đa 4 nút con 50 5 15 – Các nút lá cùng một độ sâu ⚫ Định lý: 0 3 6 7 9 17 19 20 40 70 Cây (2,4) chứa n phần tử có chiều cao (logn) 19
10. Thêm 1 phần tử vào cây (2,4) thêm 4,6,12,15,3,5,10,8 4 12 5, 12 4, 6 3, 4, 6 15 3, 4 6,10 15 4, 6, 12 12 5, 12 4, 6, 12, 15 3, 4, 5, 6 15 3, 4 6, 8, 10 15 split split 5, 12 12 3, 4 6 15 SỐ lần split khi thêm 20 4, 6 15 1 phần tử là O(logn)
11. Xóa một phần tử trong cây (2,4) ⚫ Xóa một phần tử có khóa k – Tìm kiếm nút chứa khóa k – Xóa phần tử. ⚫ Ta luôn có thể giả sử phần tử bị xóa nằm tại nút v là lá. ⚫ Nếu phần tử bị xóa là pt thứ i của nút z, tức là (ki,xi), là nút trong, ta đổi (ki,xi) với một phần tử thích hợp: – Tìm nút cực phải trên cây con thứ i của z, gọi đó là nút v – Đổi chổ (ki,xi) với phần tử cuối cùng của v. ⚫ Việc xóa như trên: – bảo toàn độ sâu – Không bảo toàn điều kiện về số phần tử ⚫ chuyển phần tử từ anh em (3-nút, 4-nút) sang, hoặc ⚫ Kết hợp 2 nút 21
12. 12 11 5, 10 15 6 15 4 6 8 11 13 14 17 5 8 10 13 14 17 11 1211 6 15 6 10 15 5 8 10 14 17 5 8 11 13 14 17
13. 11 6 15 5 8 10 1514 17 6 11 5 8 10 15 17
14. Hiệu quả của cây (2,4) ⚫ Thêm, xóa, tìm một phần tử với thời gian O(logn) 24
15. Cây đỏ-đen red – black trees ⚫ Cây đỏ đen là cây TKNP với các nút được tô màu đỏ/đen: – Gốc: đen – Nút ngoài: đen – Con nút đỏ là nút đen – Tất cả các nút ngoài (NIL) có cùng độ sâu đen (cùng số nút đen tiền bối) ⚫ Định lý: Cây đỏ-đen chứa n nút sẽ có độ cao O(Logn) – CM: Tr172 25
16. Tương đương giữa cây đỏ đen và cây (2,4) 10 10 14 13 13 14 13 14 14 13 14 20 13 20 26
17. Tương đương giữa cây đỏ đen và cây (2,4) 27
18. Các phép quay Right-Rotation(B) Left-Rotation(A) Định lý: Các phép quay trái và quay phải như trên bảo tồn trật tự các nút trên cây TKNP. 28
19. Thêm một phần tử vào cây đỏ đen ⚫ Thêm phần tử có khóa x vào cây đỏ đen – Tìm kiếm và thêm vào cây TKNP – Tô màu: Đen nếu là ROOT, Đỏ ngược lại – Như vậy: ⚫ Tính chất cân bằng “đen” bảo toàn ⚫ Tính chất nút đỏ có thể bị vi phạm: Cha nút mới có thể là nút đỏ (double red). – Gọi z là nút mới thêm, v là cha của z: Nếu v là nút đỏ thì cha của v là u phải là nút đen. Gọi w là sibling của v. 29
20. double red: Tô màu lại u Trường hợp 1: w là nút đen 30 u 30 v 10 w v 20 w z z 20 10 u u 10 10 w v v w 30 20 z z 30 20 b 20 a c a,b,c là 3 nút Rotation 10 30 theo thứ tự duyệt trung tự
21. double red: Tô màu lại Trường hợp 1: w là nút đỏ u 30 10 20 30 40 v 20 40 w z 10 Recoloring 30 u 30 v 10 20 40 20 40 w z 10
22. Tương tự u v w z u w v u z w v z
23. Recoloring u v w z u w v u z w v z
24. Ví dụ: đưa các nút 4,7,12, 15, 3, 5, 14, 18, 16, 17 vào cây đỏ đen 4 7 7 4 12 12 15 7 7 4 12 4 12 15 3 5 15 34
25. 7 7 4 12 4 14 3 5 15 3 5 12 15 14 18 7 4 14 3 5 12 15 18
26. 7 7 4 14 4 14 3 5 12 15 3 5 12 16 18 15 18 16 17
27. 7 4 14 3 5 12 16 14 15 18 7 16 17 4 12 15 18 3 5 17
28. RB-INSERT(T, x){ BST-TREE-INSERT(T, x) color[x] ← RED //only RB property 3 can be violated while (x ≠ root[T] and color[p[x]] = RED) do { if p[x] = left[p[p[x]] then { y ← right[p[p[x]] // y = aunt/uncle of x if color[y] = RED then Case_1 else if x = right[p[x]] then { Case_2 // Case 2 falls into Case 3 Case_3 } } else 〈“then” clause with “left” and “right” swapped〉 } color[root[T]] ← BLACK
29. Case 1 Là một cây đỏ đen hợp lệ (Gốc đen, các nhánh đều có cùng số nút đen) 39
30. Case 2, 3 40
31. Định lý ⚫ Thêm một phần tử vào cây đỏ đen chứa n nút cần O(logn) phép recoloring và O(1) phép quay để cấu trúc lại cây. 41
32. Xóa một nút trên cây đỏ đen ⚫ Tìm kiếm và xóa phần tử trên cây TKNP – Ta luôn xóa nút lá hoặc nút chỉ có 1 nút con – Gọi v là nút bị xóa, w là nút con ngoài của v, r là nút anh em của w, x là nút cha của v. ⚫ Xóa v và w, cho r là con của x. x x v r w r 42
33. Nếu v là nút đỏ (thì r đen) hoặc r đỏ (thì v đen) thay v bởi r, tô r đen và dừng x x v v r r w w 43
34. ⚫ Nếu v đen và r cũng đen: – Sau khi xóa thì r được đặt màu “giả” double- black) – Cấu trúc lại bộ 3 nút ( 3-nodes restructuring) x x v v w r double-black
35. Trường hợp 1: nút y anh em của r là đen, nút y có một con màu đỏ (z). Gọi a,b,c là ba nút x,y,z theo thứ tự duyệt trung tự 30 x 30 x y y 20 40 r 10 40 r z z 10 20 b Restructuring(z) 20 a c 10 30 r 40
36. Trường hợp 2: nút y anh em của r là đen, nút y có hai con đen. X màu đỏ 10 10 Recoloring 30 x 30 x y y 20 40 r 20 40 r Done!
37. Nếu x đen, tô màu lại thì x trở thành double black 30 x 30 x Recoloring y y 20 40 r 20 40 r Double black propagated
38. Trường hợp 3: nút y anh em của r màu đỏ Adjustment: IF (y == right(x)) THEN z=right(y) ELSE z=left(y) adjustment 30 x 20 y y z x 20 40 r 10 30 z Black r 10 Black 40 Then, apply case 1 or case 2 without reappearing double black
39. Định lý ⚫ Giải thuật xóa một phần tử trên cây đỏ đen chứa n phần tử có độ phức thời gian O(logn). Giải thuật cần nhiều nhất là một phép hiệu chỉnh (adjustment) và một phép cấu trúc lại bộ 3 nút (3-nodes restructuring). Như vậy nó cần nhiều nhất là 2 phép cấu trúc lại bộ 3 nút. 49
40. Ví dụ 14 7 16 4 12 15 18 3 5 17 14 7 16 Xóa nút 3 4 12 15 18 3 5 17
41. 14 14 7 16 7 16 4 12 15 18 4 15 18 5 17 5 17 Xóa nút 12 restructuring 14 5 16 4 7 15 18 17
42. 14 14 5 16 5 16 4 7 15 18 4 7 15 18 17 17 Xóa nút 17 Xóa nút 18 14 14 recoloring 5 16 5 16 4 7 15 4 7 15
43. 14 14 5 16 5 16 4 7 15 4 7 Xóa nút 15 Xóa nút 16 14 5 adjustment 5 4 14 4 7 5 7 4 14 recoloring 7
44. Red Black Trees Implementation in java ⚫ See 3.6.1 chapter 3, Algorithm design, Goodrich 54