Bài giảng Phân tích và Thiết kế giải thuật nâng cao - Phần 2, Chương 3: Cây cân bằng Balanced trees - PGS.TS. Trần Cao Đệ

Nội dung text: Bài giảng Phân tích và Thiết kế giải thuật nâng cao - Phần 2, Chương 3: Cây cân bằng Balanced trees - PGS.TS. Trần Cao Đệ

1. Phần 2: Các giải thuật nâng cao Chương 3: Cây cân bằng Balanced trees PGS. TS. TRẦN CAO ĐỆ Đại Học Cần Thơ 1 2013
2. Cây tìm kiếm nhị phân binary search tree ⚫ Cây tìm kiếm nhị phân 20 (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 10 35 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. 5 17 22 42 typedef KeyType; typedef struct Node{ KeyType Key; 15 37 Node* Left; Node* Right; }; typedef Node* Tree; 2
3. thêm một khoá vào cây TKNP void InsertNode(KeyType x,Tree& Root ){ 20 /* thêm nút mới chứa khoá x */ if (Root == NULL){ Root=(Node*)malloc(sizeof(Node)); 10 35 Root->Key = x; Root->Left = NULL; Root->Right = NULL; } 5 17 22 42 else if (x Key) InsertNode(x,Root->Left); else if (x>Root->Key)InsertNode(x,Root->Right); 15 19 37 } 3
4. 20 Xóa một nút trên cây TKNP 10 10 NULL35 5 17 Xóa nút 17 Xóa nút 35 Xóa nút 20 20 15 10 35 5 17 25 42 22 24
5. Xóa một nút trên cây TKNP KeyType DeleteMin (Tree& Root ){ KeyType k; if (Root->Left == NULL){ k=Root->Key; Root = Root->Right; return k; } else return DeleteMin(Root->Left); } void DeleteNode(KeyType x,Tree& Root){ if (Root!=NULL) if (x Key) DeleteNode(x,Root->Left); else if (x > Root->Key) DeleteNode(x,Root->Right); else if ((Root->Left==NULL) && (Root->Right==NULL)) Root=NULL; else if (Root->Left == NULL) Root = Root->Right; else if (Root->Right==NULL) Root = Root->Left; else Root->Key = DeleteMin(Root->Right); } 5
6. Phân tích BST ⚫ Tìm kiếm một nút trên cây TKNP – Mất O(1) duyệt trên mỗi nút – Mỗi lần duyệt đi sâu xuống một mức – Vậy thời gian tìm kiếm là O(h) với h là chiều cao của cây ⚫ Thời gian tìm kiếm 1 nút, thêm một nút, xóa một nút trên cây TKNP là O(h), với h là chiều cao của cây TKNP ⚫ Chiều cao của cây TKNP có n nút: Logn ≤ h ≤ n 6
7. Cây AVL ⚫ Trong trường hợp xấu nhất ⚫ Chứng minh Gọi N số nút cây AVL có chiều cao h. thời gian thực hiện các phép h N ≥ N + N + 1 toán trên BST là O(n) h h-1 h-2 ≥ 2Nh-2 + 1 ⚫ Cân bằng AVL ≥ 1 + 2(1 + 2Nh-4) 2 – Do Adelson Velski và = 1 + 2 + 2 Nh-4 2 3 Landis ≥ 1 + 2 + 2 + 2 Nh-6 – AVL: Cây TKNP mà chiều ≥ 1 + 2 + 22 + 23 + + 2h/2 cao của hai cây con của = 2h/2+1 – 1 mọi nút chênh lệch nhiều Vậy nhất là 1. 2h/2+1 – 1 < n ⚫ Trên cây AVL các phép tìm h/2 +1 < log2(n + 1) kiếm, thêm, xoa một nút là h < 2 log2(n + 1) O(log n), n là số nút ⚫ Phân tích sâu sắc theo số Fibonacci, giới hạn trên là 1.44 log(n + 2). 7
8. Thêm một nút vào cây AVL ⚫ Đầu tiên thêm một nút vào cây TKNP. Cây có thể mất cân bằng. ⚫ Cân bằng lại – Xét cây AVL: tree T=(r,Tl,Tr) trong đó Tl có chiều cao hl và Tr có chiều cao hr – Giả sử nút thêm vào trên Tr. ⚫ Nếu hl=hr+1: sau khi thêm vẫn cân bằng ⚫ Nếu hl=hr : sau khi thêm vẫn cân bằng ⚫ Nếu hl=hr-1 thì sau khi thêm sẽ mất cân bằng→cân bằng lại. – Tương tự nếu thêm nút vào Tl 8
9. Single Rotation-RR RR rotation 9
10. Single rotation LL LL 10
11. Double rotation-LR LR 11
12. Double rotation-RL RL 12
13. 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
14. Ví dụ thêm 1 khóa LL Thêm khóa 1 Thêm khóa 32 14
15. Xóa nút 4 4 RR rotation LL rotation
16. AVL Trees Implementation in java ⚫ See 3.6.1 chapter 3, Algorithm design, Goodrich 16
17. 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
18. 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
19. 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
20. 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)
21. 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
22. 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
23. 11 6 15 5 8 10 1514 17 6 11 5 8 10 15 17
24. 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
25. 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
26. 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
27. Tương đương giữa cây đỏ đen và cây (2,4) 27
28. 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
29. 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
30. 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ự
31. 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
32. Tương tự u v w z u w v u z w v z
33. Recoloring u v w z u w v u z w v z
34. 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
35. 7 7 4 12 4 14 3 5 15 3 5 12 15 14 18 7 4 14 3 5 12 15 18
36. 7 7 4 14 4 14 3 5 12 15 3 5 12 16 18 15 18 16 17
37. 7 4 14 3 5 12 16 14 15 18 7 16 17 4 12 15 18 3 5 17
38. 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
39. 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
40. Case 2, 3 40
41. Đị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
42. 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
43. 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
44. ⚫ 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
45. 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
46. 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!
47. 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
48. 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
49. Đị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
50. 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
51. 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
52. 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
53. 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
54. Red Black Trees Implementation in java ⚫ See 3.6.1 chapter 3, Algorithm design, Goodrich 54