›
›

Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 5 đến 8 - Hồ Sĩ Đàm

ppt 152 trang hoanguyen 4690
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 5 đến 8 - Hồ Sĩ Đàm", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pptbai_giang_cau_truc_du_lieu_va_giai_thuat_chuong_5_den_8_ho_s.ppt

Nội dung text: Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 5 đến 8 - Hồ Sĩ Đàm

  1. CHƯƠNG V CÂY (TREE) 1. Một số khái niệm 1.1. Định nghĩa 1.2. Các ví dụ về cấu trúc cây 1.3. Các khái niệm 2. Cây nhị phân 2.1. Định nghĩa 2.2. Tính chất 2.3. Biểu diễn cây nhị phân 2.4.* Cây k-phân 2.5.* Cây tổng quát 3. Cây tìm kiếm nhị phân 4. Cây có thứ tự bộ phận
  2. 1. Một số khái niệm 1.1. Định nghĩa C= V: Tập hữu hạn các phần tử (nút) E: Tập hữu hạn(cung) thể hiện mối quan hệ phân cấp là quan hệ “ cha – con”. ◼ Nút gốc (root). ◼ Cây rỗng (null tree)
  3. 1. Một số khái niệm Định nghĩa đệ quy: ◼ Mỗi nút là một cây ◼ n là nút và n1, n2, ,nk là gốc của các cây C1,C2, Ck; (không có nút chung). ◼ n là cha của các nút n1, n2, .,nk thì có một cây mới C.
  4. 1. Một số khái niệm b) Các ví dụ về cấu trúc cây ◼ Mục lục của một cuốn sách ◼ Cấu trúc thư mục trên đĩa máy tính. ◼ Dùng cây để biểu diễn biểu thức số học, chẳng hạn: ( a+b) x (c-d/e)
  5. x - + / c a b d e
  6. Trường đại học Khu A Khu B . . . Khoa 1 Khoa 2 . . . Khoa N Khoa 1 Khoa 2 Khoa M Sinh viên Sinh viên . . . . . . . . . . Giảng viên . . . . . chính qui tại chức . . . . .
  7. 1. Một số khái niệm c) Các khái niệm i) Số các con của một nút gọi là cấp của nút đó ii) Nút có cấp bằng 0 gọi là nút lá (leaf) iii) Các nút không phải nút lá gọi là nút nhánh ( branch) iv) Cấp cao nhất có trong các nút của một cây gọi là cấp của cây đó.
  8. V)Gốc của cây có mức 1, nếu một nút có mức i thì các nút con của nút đó có mức i+1. vi) Chiều cao (height) của cây là số mức cao nhất của các nút có trên cây đó vii) Tập hợp các cây phân biệt gọi là một rừng (forest).
  9. 1 A 2 B C D 3 E F G H I 4 J K
  10. 2. Cây nhị phân (Binary tree) a) Định nghĩa: ◼ Cây nhị phân là cây mà mọi nút của nó có tối đa hai cây con. Với mỗi nút xác định cây con trái và cây con phải.
  11. . Cây nhị phân (Binary tree) ◼ Cây nhị phân suy biến : cây lệch trái, cây lệch phải, cây dích dắc. 1 1 1 2 2 2 3 3 3 4 4 4 5 5 5
  12. 2. Cây nhị phân (Binary tree) ◼ Cây nhị phân hoàn chỉnh (complete binary tree) có chiều cao là h thì mọi nút có mức < h-1 đều có đúng 02 nút con.
  13. 2. Cây nhị phân (Binary tree) ◼ Cây nhị phân đầy đủ ( full Binary tree) có chiều cao h thì mọi nút có mức <=h-1 đều có đúng 02 nút con
  14. 2. Cây nhị phân (Binary tree) b) Một số các tính chất: Nếu số lượng nút là như nhau thì cây nhị phân suy biến có chiều cao lớn nhất, cây nhị phân đầy đủ có chiều cao nhỏ nhất. Số lượng tối đa các nút trên mức i là 2i-1 và tối thiểu là 1 ( i>=1)
  15. Số lượng tối đa các nút trên cây nhị phân có chiều cao h là 2h-1 và tối thiểu là h ( h>=1) Cây nhị phân hoàn chỉnh có n nút thì chiều cao của nó là h=[ lg(n)] +1
  16. 2. Cây nhị phân (Binary tree) A 1 c) Biểu diễn cây nhị phân ◼ Biểu diễn bằng mảng: Đánh số thứ tự các nút 2 B E 3 theo “ trên – dưới” và “trái – phải”. C D F G 4 5 6 7 Với nút i thì ◼ nút con trái của nó 2i và nút con phải là 2i+1. 1 2 3 4 5 6 7 ◼ Nút cha là [i/2]. A B E C D F G
  17. 2. Cây nhị phân (Binary tree) ◼ Biểu diễn bằng danh sách liên kết Một trường Data lưu giá trị Một trường Left chứa liên kết trỏ tới nút con trái hoặc Null. Một trường Right chứa liên kết trỏ tới nút con phải hoặc Null. Như vậy nút gốc sẽ là nút đầu tiên của danh sách móc nối, với các nút lá các trường Left và Right đều chứa giá trị Null.
  18. 2. Cây nhị phân (Binary tree) d) Duyệt cây nhị phân Cách 1. Duyệt theo thứ tự trước (preorder traversal) Nút đang xét Cây con trái Cây con phải.
  19. Tree Traversal • Traversal = visiting every node of a tree • Three basic alternatives Pre-order  • Root • Left sub-tree  • Right sub-tree   x A + x + B C x D E F L R L R L
  20. Cách 2. Duyệt theo thứ tự giữa (inorder traversal) Cây con trái Nút dang xét Cây con phải.
  21. Tree Traversal • Traversal = visiting every node of a tree • Three basic alternatives In-order • Left sub-tree  • Root   • Right sub-tree 11  A x B + C x D x E + F   L L R
  22. Cách 3. Duyệt theo thứ tự sau (postorder traversal) Cây con trái Cây con phải Nút đang xét.
  23. Tree Traversal • Traversal = visiting every node of a tree • Three basic alternatives Post-order • Left sub-tree 11 • Right sub-tree   • Root A B C + D E x x F + x   L   L R
  24. 2. Cây nhị phân (Binary tree) e) Cây k-phân mỗi nút có không quá k nút con. A B F J C M G H I D E K L
  25. CHƯƠNG V: CÂY (TREE) 2. Cây nhị phân (Binary tree) e) Cây k-phân ◼ Biểu diễn cây k-phân bằng mảng Bổ sung thêm một số nút giả sao cho mỗi nút của cây đều có đúng k nút con, các nút con đều xếp thứ tự từ nút con thứ nhất cho đến nút con thứ k.
  26. Đánh số thứ tự trên cây cũng theo nguyên tắc “ trên-xuống” và “ trái phải” ◼ Nút con thứ j của nút I sẽ có số thứ tự là k.i +j. ◼ Nếu I không phải là nút gốc thì nút cha của nút I là [( i-1)/k] Dùng mảng C để lưu trữ cây thì C[i] sẽ lưu trữ giá trị của nút thứ i.
  27. ◼ Biểu diễn cây k-phân bằng DS liên kết Trường Data ghi giá trị của nút. K trường, trường j là liên kết trỏ đến nút con thứ j của nút đang xét. Trường hợp không có nút con thì ghi giá trị null.
  28. 2. Cây nhị phân (Binary tree) f) Cây tổng quát ◼ Định nghĩa: cây không hạn chế số lượng nút con của mỗi nút. ◼ Biểu diễn cây tổng quát bằng mảng Cho cây có n nút, các nút được gán một số thứ tự tùy chọn. Ta có thể xây dựng một cấu trúc dữ liệu như sau: Một mảng Data gồm n phần tử, phần tử Data[i] lưu giá trị của nút i
  29. Một mảng Children chia thành n đoạn, đoạn thứ i gồm một dãy liên tiếp các chỉ số các nút con của nút i. Như vậy mảng Children sẽ có n phần tử ( với các đoạn tương ứng với lá sẽ là đoạn rỗng, không có nút con). Một mảng Head gồm n phần tử. Head[i] là vị trí đứng liền trước đoạn i. Quy ước Head[n+1]=n- 1 Một biến lưu chỉ số của nút gốc
  30. 2. Cây nhị phân (Binary tree) Cây tổng quát Lưu trữ cây tổng quát bằng danh sách liên kết: Trường Data chứa giá trị của nút Trường FirstChild chứa liên kết trỏ đến nút con đầu tiên của nút tương ứng. Nếu nút không có con thì ghi giá trị đặc biệt là Null. Trường Sibling chứa liên kết trỏ tới nút em kế cận bên phải ( nút cùng cha). Nếu không có nút em thì ghi giá trị đặc biệt null.
  31. ◼ Bằng cách xây dựng cấu trúc như vậy rõ ràng là từ một nút i bất kì ta có thể đi theo liên kết FirstChild để đến nút con cả sau đó đi theo liên kết Sibling ta có thể duyệt qua tất cả các nút con của nút i.
  32. 3. Cây tìm kiếm nhị phân a) Định nghĩa Là một cây nhị phân: ◼ Giá trị của các nút của cây con trái nhỏ hơn giá trị của nút gốc; ◼ Giá trị của các nút cây con phải lớn hơn giá trị của nút gốc; ◼ Cây con trái và cây con phải cũng là cây tìm kiếm nhị phân. ◼ Các giá trị khóa là khác nhau.
  33. 3. Cây tìm kiếm nhị phân b) Phép tìm kiếm: Có nút nào chứa giá trị bằng khóa? Bắt đầu từ gốc, đối sánh giá trị nút với khóa: Bằng nhau thì Kết thúc Nhỏ hơn thực hiện trên cây con trái Lớn hơn thực hiện trên cây con phải
  34. 3. Cây tìm kiếm nhị phân c) Phép chèn Xin cấp bộ nhớ cho một nút mới, Gán giá trị mới vào trường Data của nút mới. Trường Left và trường Right của nút mới đều được gán giá trị đặc biệt Null.
  35. 3. Cây tìm kiếm nhị phân Từ gốc, đối sánh với giá trị mới cần thêm vào: Nếu bằng nhau kết thúc Ngược lại duyệt theo cây con trái ( nếu )
  36. 3. Cây tìm kiếm nhị phân Khi gặp nút x không có nút con trái/phải xác định được ví trí cần chèn. Chỉnh sữa các trường liên kết để con trỏ trái/phải của nút x trỏ tới nút mới.
  37. 3. Cây tìm kiếm nhị phân d) Phép xóa ◼ Nếu nút x là nút lá ta chỉ cần “cắt bỏ” x 4 4 2 6 2 6  1 3 5 7 1 3 7 9 9
  38. 3. Cây tìm kiếm nhị phân d) Phép xóa ◼ Nếu x có một trong hai cây con là cây rỗng thì điều chỉnh lại con trỏ của nút cha của x bằng cách trường liên kết tương ứng thay vì trỏ đến x thì bây giờ trỏ tới nút gốc của cây con duy nhất của x và giải phóng bộ nhớ đã cấp cho x
  39. 4 4 2 5 2  1 3 7 1 3 7 6 6 9 9
  40. 3. Cây tìm kiếm nhị phân d) Phép xóa ◼ Nếu nút x có hai cây con (có gốc tương ứng là x1 và x2) và một trong hai cây con (chẳng hạn x1) không có con thì ta thay nút x1 làm nút cha của cây con có gốc là x2. Ta thay đổi trường liên kết như sau:
  41. Trường liên kết nút cha của x thay vì trỏ tới x thì nay trỏ tới nút con x1. Trường liên kết của nút con x1 thay vì là null nay trỏ vào nút x2
  42. 4 4 2 5 2  1 7 7 3 1 3 6 6 9 9
  43. 3. Cây tìm kiếm nhị phân ◼ Trường hợp tổng quát: 1. Thay giá trị của x bằng giá trị nút lá bên phải cùng của cây con trái ( hoặc bằng giá trị nút lá bên trái cùng của cây con phải) 2. Cắt bỏ nút có giá trị vừa gán cho nút x. Vì nút được lựa chọn để thay thế là bên phải/ trái cùng nên không thể có hai con, việc cắt bỏ nó sẽ thực hiện theo các cách đã nêu trên
  44. CHƯƠNG V: CÂY (TREE) 3. Cây tìm kiếm nhị phân d) Phép xóa 4 3  2 5 2 5 1 3 7 1 7 6 9 6 9 4 5  2 5 2 7 1 3 7 1 3 6 9 6 9
  45. 3. Cây tìm kiếm nhị phân e) Đánh giá thời gian thực hiện các phép toán ◼ Với phép tìm kiếm. Phép toán tích cực: phép so sánh . Coi thời gian thực một phép toán so sánh = là thời gian đi từ một đỉnh đến đỉnh con của nó → thời gian thực hiện tìm kiếm có thể coi là thời gian đi trên quảng đường đi từ gốc đên một đỉnh nào đó.
  46. Trường hợp với cây nhị phân đầy đủ thì độ cao của cây là xấp xỉ logn. Giả sử mức thấp nhất là k: 1+ 2+ 22 + +2k-1 =n Hay 2k -1 =n, do vậy log(n+1) -1 <=k < log(n+1) , nghĩa là k xấp xỉ logn. Vì thế độ phức tạp thuật toán là O( logn) Trong trường hợp xấu nhất, nghĩa là cây suy biến lệch trái hoặc lệch phải thì độ phức tạp thuật toán là O(n) ◼ Với các phép toán chèn và xóa cũng có cách
  47. 4. Cây có thứ tự bộ phận Cây có thứ tự bộ phận còn gọi là cấu trúc Heap: Cây nhị phân hoàn thiện, ở mức cuối cùng, tất cả các nút lá đều xuất hiện liên tiếp từ trái sang phải. Giá trị khóa của mỗi nút không nhỏ hơn giá trị nút hai con của nó. Mỗi cây con trái và phải của nó cũng là cây có thứ tự bộ phận. Ta gọi các điều kiện trên là các tính chất Heap.
  48. 10 21 15 8 7 10 12 6 2 3 6 (a) 10 12 10 6 6 2 7 10 21 8 7 15 15 8 3 6 2 3 6 (b) (c)
  49. ◼ Một số heap khác nhau tạo từ cùng một dữ liệu
  50. 4. Cây có thứ tự bộ phận ◼ Phép chèn (Insert) Giả sử ta cần chèn thêm một nút mới có giá trị chẳng hạn là X. Tạo nút mới, ghi giá trị X vào trường Data của nút mới đó. Thay giá trị Null trong trường liên kết của nút có một nút lá trỏ vào nút mới.
  51. 4. Cây có thứ tự bộ phận Nếu tính chất Heap bị phá vỡ thì sử dụng thủ tục Upheap: Lần lượt từ nút lá đó “ đi ngược lên”. Nếu tại một nút mà giá trị khóa của nút đó lớn hơn giá trị khóa của nút cha nó thì tráo đổi hai giá trị đó cho nhau.
  52. ◼ Ví dụ thêm nút 15
  53. 4. Cây có thứ tự bộ phận Phép xóa Thay giá trị của nút gốc bằng giá trị nút lá sau cùng ở mức cuối cùng Xóa nút lá đó đi Sử dụng thủ tục Downheap: Lần lượt từ nút gốc “ đi xuống “, Khi cần, tráo đổi giá trị khóa của nó với giá trị khóa của nút con có giá trị không nhỏ hơn. Quá trình trên cùng lắm là dừng lại khi đến nút lá.
  54. ◼ Xóa nút gốc
  55. 4. Cây có thứ tự bộ phận ◼ Phép xóa 10 2 8 9 8 9 7 4 6 1 7 4 6 1 3 5 2 3 5 10
  56. 9 5 8 6 8 6 7 4 2 1 7 4 2 1 3 5 3 9
  57. CHƯƠNG VII: SẮP XẾP 1. Giới thiệu 2. Sắp xếp bằng lựa chọn 3. Sắp xếp bằng tráo đổi 4. Sắp xếp chèn 5. Sắp xếp vun đống 6. Sắp xếp trộn 7. Sắp xếp nhanh 8. Sắp xếp theo cơ số 9. Tính ổn định của thuật toán sắp xếp
  58. 1. Giới thiệu ◼ Sắp xếp là bố trí lại vị trí các phần tử của một tập đối tượng theo một trật tự nào đó. ◼ Ví dụ: Sắp xếp các từ trong từ điển Sắp xếp dữ liệu trong máy tính, Sắp xếp kết quả điểm thi tuyển sinh Sắp xếp danh sách sinh viên theo thứ tự ABC,
  59. Sorting • Card players all know how to sort • First card is already sorted • With all the rest, Scan back from the end until you find the first card larger than the new one, Move all the lower ones up one slot insert it           A K 10 2 J 2 2 Q 9  9 
  60. 1. Giới thiệu Các thuộc tính đối tượng có thể thuộc nhiều kiểu dữ liệu khác nhau. Thông thường yêu cầu sắp xếp chỉ căn cứ vào các thành phần gọi là trường khóa sắp xếp ( gọi tắt là trường khóa).
  61. ◼ Thực hiện qua hai pha Pha 1: Dựa vào giá trị trường khóa và yêu cầu sắp xếp ta xác định vị trí của mỗi đối tượng trong tập sau khi sắp xếp. Pha 2: Chuyển toàn bộ thông tin của đối tượng ( STRUCT) về đúng vị trí tương ứng đã xác định trong Pha 1.
  62. 1. Giới thiệu Cho dãy K gồm n giá trị khóa k1, k2, , kn. Cần xếp lại vị trí các khóa sao cho: k’1 <= k’2<= k’n, ki thuộc tập { k1, k2, , kn.} a) Dữ liệu gốc b) Sau khi sắp xếp
  63. 2. Sắp xếp bằng lựa chọn ◼ Ý tưởng Tráo đổi giá trị nhỏ nhất khóa k1 ở lươt thứ hai ta chọn trong số ( n-1) khóa còn lại khóa nhỏ nhất và tráo đổi giá trị đó cho khóa k2, Tiếp tục quá trình tương tự như vậy.
  64. Cài đặt C++ template void selectionsort(T data[], int n){ for (int i = 0; i < n-1; i++){ int j, least = i; T tmp; for (j = i+1; j < n; j++) if (data[j] < data[least]) least = j; tmp = data[i]; ◼ data[i] = data[least]; ◼ data[least] = tmp; ◼ } ◼ }
  65. i 1 2 3 4 5 6 ki 9 6 1 10 7 4 Lượt 1 1 6 9 10 7 4 Lượt 2 4 9 10 7 6 Lượt 3 6 10 7 9 Lượt 4 7 10 9 Lượt 5 9 10
  66. 2. Sắp xếp bằng lựa chọn Đánh giá Phép toán so sánh là phép toán tích cực. Số lượng các phép toán tích cực là: (k-1) +(k-2) + +2+1= k* (k-1)/2 Do đó O(k2)
  67. 3. Sắp xếp bằng tráo đổi Ý tưởng ◼ Với mỗi cặp số hạng đứng liền kề trong dãy K, nếu chúng không thoả mãn điều kiện cần sắp xếp ta tiến hành đổi chỗ chúng cho nhau. ◼ Việc làm đó được lặp lại, cho đến khi không có bất kì một cặp số hạng liền kề nào cần đổi chỗ.
  68. 3. Sắp xếp bằng tráo đổi template void bubblesort(T data[], int n){ for (int i = 0; i i; j) if (data[j] < data[j-1]) { T tmp = data[j]; data[j] = data[j-1]; data[j-1] = tmp; } }
  69. Mô phỏng các bước thực hiện của thuật toán . Dãy A 6 1 5 3 7 8 10 7 12 4 Lượt 1 1 5 3 6 7 8 7 10 4 12 Lượt 2 1 3 5 6 7 7 8 4 10 Lượt 3 1 3 5 6 7 7 4 8 Lượt 4 1 3 5 6 7 4 7 Lượt 5 1 3 5 6 4 7 Lượt 6 1 3 5 4 6 Lượt 7 1 3 4 5 Lượt 8 1 3 4 Lượt 9 1 3 Lượt 10 1
  70. CHƯƠNG VII: SẮP XẾP 3. Sắp xếp bằng tráo đổi Đánh giá Tổng số lượng các phép toán tích cực là: (N-1) +(N-2) + +2+1= N* (N-1)/2 Do đó O(N2)
  71. 4. Sắp xếp chèn Ý tưởng k1 có thể coi là đã sắp xếp. Thêm k2, nếu k2 <k1 thì chèn nó vào trước k1. Thêm k3, vì dãy 02 phần tử k1 và k2 là đã sắp xếp, cần tìm cách chèn k3?
  72. 4. Sắp xếp chèn Tổng quát, dãy k1, k2, , ki-1 là dãy đã sắp, ta cần chèn thêm ki vào dãy đó sao cho dãy sau khi chèn cũng là dãy đã sắp.
  73. 4. Sắp xếp chèn ◼ So sánh ki lần lượt với các khóa của dãy đã sắp từ ki-1 cho đến khi tìm được j mà kj-1 <= ki < kj thì dừng lại.
  74. ◼ Chuyển dịch đoạn con từ vị trí thứ j đến (i-1) sang phải một ví trí. ◼ Chèn ki vào ví trí rỗng có được sau khi chuyển dịch.
  75. C++ ◼ template void insertionsort(T data[], int n){ for (int i=1,j; i 0 && tmp < data[j-1]; j ) data[j] = data[j-1]; data[j]=tmp; ◼ } ◼ }
  76. Lượt 3 1 4 1 5 9 2 6 5 4 1 3 1* 4 1 5 9 2 6 5 4 2 1 3 4* 1 5 9 2 6 5 4 3 1 3 4 1* 5 9 2 6 5 4 4 1 1 3 4 5* 9 2 6 5 4 5 1 1 3 4 5 9* 2 6 5 4 6 1 1 3 4 5 9 2* 6 5 4 7 1 1 2 3 4 5 9 6* 5 4 8 1 1 2 3 4 5 6 9 5* 4 9 1 1 2 3 4 5 5 6 9 4* 10 1 1 2 3 4 4 5 5 6 9
  77. 4. Sắp xếp chèn ◼ Đánh giá Dãy cho trước là dãy đã sắp, O(n). Dãy có thứ tự ngược với thứ tự cần sắp O(n2) Trung bình, có thể coi ở lượt thứ i thuật toán cần trung bình i/2 phép so sánh nên tổng là:(1/2) +(2/2)+(3/2) + +(n/2) = (n+1) * n/4 Vậy thuật toán có độ phức tạp là O(n2).
  78. 5. Sắp xếp vun đống ◼ Ý tưởng Heapsort do W.j.William đề xuất dựa trên cấu trúc heap ( xem chương VI) gồm các thao tác sau: (i) Từ dãy a1 . an cho trước ta xây dựng cấu trúc heap bằng cách sử dụng (N-1) phép chèn, mỗi lần chèn một phần tử của dãy K và chỉnh sữa để cấu trúc sau mỗi lần chèn luôn có tính chất heap ( Xem chương VI).
  79. ◼ (ii) Từ cấu trúc heap đã xây dựng được thực hiện (N-1) lần tráo đổi giá trị ở gốc với giá trị số hạng thứ i ở lượt thứ i, bắt đầu từ an ( i= N, (N-1), 3,2).
  80. 5. Sắp xếp vun đống Sau mỗi lần tráo đổi như vậy: ◼ Số hạng KI không còn tham gia vào đống và đó là phần tử lớn nhất (nằm ở gốc tại bước thứ i-1); ◼ “ vun đống” lại để cấu trúc bảo toàn tính chất heap ( Xem chương VI) đối với cây có (i-1) nút.
  81. 10 2 8 9 8 9 7 4 6 1 7 4 6 1 3 5 2 3 5 10
  82. 9 5 8 6 8 6 7 4 2 1 7 4 2 1 3 5 3 9
  83. C++ Heapsort ◼ template ◼ void heapsort(T data[], int size) { ◼ for (int i = size/2 – 1; i >= 0; i) // tạo cây heap; ◼ moveDown (data, i, size - 1); ◼ for (int i = size – 1; i >= 1; 1) { ◼ swap(data[0], data[i]); // đổi nút lớn nhất ra vị trí i; ◼ moveDown (data, 0, i-1);// tạo lại cây heap từ phần còn lại; ◼ } ◼ }
  84. 5. Sắp xếp vun đống ◼ Đánh giá Nếu cần sắp theo tiêu chí tăng dần thì phải dùng một phép đảo dãy kết quả. Phép toán tích cực là phép so sánh. Như đã biết, heap là một cây hoàn chỉnh, có N nút thì chiều cao của nó là [lg(N)] +1, vì thế độ phức tạp của thuật toán này sẽ là O( NlgN).
  85. 6. Sắp xếp trộn ◼ Ý tưởng Chỉ cần sắp xếp dãy con nhập mới rồi “trộn” hai dãy đã được sắp thành một dãy được sắp. Như vậy thao tác “trộn” là phép toán chủ đạo của thuật toán Mergesort.
  86. Trộn Cho hai dãy đã sắp xếp: B={b1,b2 bm} C={c1 Cn }cần trộn thành dãy D={d1, dn+m } phải là dãy được sắp.
  87. (i) Lần lượt xác định di ( 1<=i<=n+m) bằng cách chọn phần tử nhỏ hơn trong hai phần tử bj và ck ( 1<=j<=m; 1<=k<=n) tại mỗi bước.
  88. Chú ý (ii) Trong cài đặt thường thêm một phần tử có giá trị lớn hơn giá trị các phần tử trong dãy vào cuối mỗi dãy B và C để khi tất cả các phần tử của một dãy đã được lựa chọn cho dãy D thì các phần tử còn lại của dãy kia sẽ chuyển thành các phần tử còn lại của dãy D.
  89. Ví dụ, cần trộn hai dãy được sắp (B)= (1, 5, 7, 8, 9) và (C)=(2, 6, 10, 11, 12, 35). Dãy B j Dãy C i Khóa nhỏ nhất Dãy D k 1,5,7,8,9 1 2,6,10,11,12,35 0 1 1 1 5,7,8,9 1 2,6,10,11,12,35 1 2 1, 2 2 5,7,8,9 2 6,10,11,12,35 1 5 1,2,5 3 7,8,9 2 6,10,11,12,35 2 6 1,2,5,6 4 7,8,9 3 10,11,12,35 2 7 1,2,5,6,7 5 8,9 4 10,11,12,35 2 8 1,2,5,6,7,8 6 9 5 10,11,12,35 2 9 1,2,5,6,7,8,9 7 [] 10,11,12,35 3 Đưa phần còn 1,2,5,6,7,8,9,10,11, 8,9,10,11 lại vào D 12,35
  90. 6. Sắp xếp trộn ◼ Đánh giá Sắp xếp trộn là một thuật toán sắp xếp cổ điển nhất ( do J. Von Neumann đề xuât năm 1945), nhưng cho tới nay đó là thuật toán được coi là thuật toán sắp xếp ngoài mẫu mực nhất.
  91. Phép toán tích cực trong phép trộn là phép đưa một phần tử khóa vào dãy kết quả nên độ phức tạp của trộn là O(N). Trong sắp xếp trộn sử dụng không quá [lgn] lần trộn nên độ phức tạp của thuật toán sắp xếp trộn là O(NlgN). Nhược điểm là phải dùng thêm không gian để lưu trữ dãy khóa d ( trong việc trộn).
  92. Sắp xếp trộn ◼ Chia đôi dãy đã cho thành 02 nữa đầu và cuối ( hơn kém nhau không quá một phần tử). ◼ Với mỗi dãy con đầu và cuối được sắp xếp một cách đệ quy. ◼ Trộn hai dãy con đã sắp lại .
  93. Sắp xếp trộn ( trộn 02 đường trực tiếp) ◼ Mỗi phần tử ai là một dãy con với độ dài bằng 1( dãy một phần tử dãy đã được sắp). ◼ Trộn hai dãy con liền kề đã sắp thành một dãy con lớn hơn cũng là dãy được sắp. Tiếp tục như vậy, số lượng các dãy con trong dãy giảm dần sau mỗi lần trộn.
  94. Sắp xếp trộn hai đường Cho dãy: ( 3,5,4,6,9,7,12,13,11, 8) ◼ Trộn từng cặp hai số hạng liền kề, thu được: (3,5), (4,6), (7,9), (12, 13),(8,11) ◼ Trộn từng cặp hai dãy liền kề, thu được: (3,4,5,6) , (7,9,12,13), (8,11) ◼ Lặp lại như trên, thu được: (3,4,5,6,7,9,12,13) và (8,11) Trộn hai dãy con đã sắp, nhận được kết quả: ◼ ( 3,4,5,6,7,8 ,9,11,12,13).
  95. 7. Sắp xếp nhanh ◼ Ý tưởng Quicksort là một thuật toán rất hiệu quả do C.A.R. Hoare xây dựng vào năm 1960, gồm hai pha: Phân đoạn ( partition) Sắp xếp (sort).
  96. ◼ Phân đoạn Với dãy đã cho ta chọn ngẫu nhiên một chỉ số j làm chốt (Pivot) Chuyển tất cả các số hạng của dãy có giá trị nhỏ hơn kj đứng trước chốt và tất cả các số hạng có giá trị lớn hơn hoặc bằng kj. đều đứng sau kj.
  97. Quicksort • Partition • Choose a pivot • Find the position for the pivot so that • all elements to the left are less • all elements to the right are greater pivot
  98. CHƯƠNG VII: SẮP XẾP 7. Sắp xếp nhanh Phân đoạn Để phân đoạn ta thự hiện các bước sau: (i) Chọn một số hạng nào đó giả định là chốt, ví dụ số hạng đầu tiên ( bên trái nhất); (ii) Tạo hai chỉ số left và right có giá trị khởi tạo left=1 và right= N; (iii) Giảm lần lượt right mỗi lần xuống 1 đơn vị cho đến khi gặp số hạng nhỏ hơn chốt thì dừng lại.
  99. (iV) Tăng lần lượt left mỗi lần lên 1 đơn vi cho đến khi gặp số hạng lớn hơn chốt thì dừng lại. (V) Hoán vị hai số hạng xẩy ra dừng ở trên (Vi) Tiếp tục thực hiện các bước iii và iV cho đến khi các chỉ số giao nhau ( left>=right) thì dừng lại. (Vii) Hoán vị chốt với k[right] và kết thúc phân đoạn.
  100. 7. Sắp xếp nhanh ◼ Chia để trị và đệ quy Sau khi đã xác định được vị trí của chốt, dãy cho trước chia thành 02 đoạn, thỏa mãn tính chất phân đoạn. Với mỗi đoạn lại tiến hành phân đoạn đệ quy cho đến khi trong dãy con hiện thời chỉ còn lại không quá hai số hạng. Dãy thu được sẽ là dãy được sắp.
  101. Quicksort • Implementation quicksort( void *a, int low, int high ) { int pivot; /* Termination condition! */ if ( high > low ) { pivot = partition( a, low, high ); Divide quicksort( a, low, pivot-1 ); quicksort( a, pivot+1, high ); Conquer } }
  102. 7. Sắp xếp nhanh Quicksort - Partition This example int partition( int *a, int low, int high ) { uses int’s int left, right; int pivot_item; to keep things pivot_item = a[low]; simple! pivot = left = low; right = high; while ( left pivot */ while( a[right] >= pivot_item ) right ; if ( left < right ) SWAP(a,left,right); } /* right23 is12 final15 position38 42 for18 the36 pivot29 27*/ a[low] = a[right]; a[right] = pivot_item; return right; } low high
  103. 7. Sắp xếp nhanh Quicksort - Partition int partition( int *a, int low, int high ) { int left, right; int pivot_item; pivot_item = a[low]; pivot = left = low; Move the markers right = high; while ( left pivot */ while( a[right] >= pivot_item ) right ; if ( left < right ) SWAP(a,left,right); } left right /* right is final position for the pivot */ a[low] = a[right];23 12 15 38 42 18 36 29 27 a[right] = pivot_item; return right; } low pivot: 23 high
  104. Quicksort - Partition int partition( int *a, int low, int high ) { int left, right; int pivot_item; pivot_item = a[low]; pivot = left = low; Swap the two items right = high; while ( left pivot */ while( a[right] >= pivot_item ) right ; if ( left < right ) SWAP(a,left,right); } /* right is finalleft positionright for the pivot */ a[low] = a[right]; a[right] = pivot_item; 23return12 right;15 38 42 18 36 29 27 } pivot: 23 low high
  105. 7. Sắp xếp nhanh Quicksort - Partition int partition( int *a, int low, int high ) { int left, right; int pivot_item; pivot_item = a[low]; pivot = left = low; right = high; while (right left pivot36 */ 29 27 while( a[right] >= pivot_item ) right ; if ( left < right ) SWAP(a,left,right); low } pivot: 23 high /* right is final position for the pivot */ a[low] = a[right]; a[right] = pivot_item; Finally, swap the pivot return right; and right }
  106. 7. Sắp xếp nhanh Quicksort - Partition int partition( int *a, int low, int high ) { int left, right; int pivot_item; pivot_item = a[low]; pivot = left = low; right = high; while ( rightleft pivot36 */ 29 27 while( a[right] >= pivot_item ) right ; if ( left < right ) SWAP(a,left,right); low } high /* right is final position for the pivot */ a[low] = a[right]; a[right] = pivot_item;Return the position return right; of the pivot }
  107. CHƯƠNG VII: SẮP XẾP 7. Sắp xếp nhanh Quicksort - Conquer pivot pivot: 23 18 12 15 23 42 38 36 29 27 Recursively Recursively sort left half sort right half
  108. CHƯƠNG VII: SẮP XẾP 7. Sắp xếp nhanh Đánh giá và nhận xét ◼ Có hướng tổng quát tốt ◼ Sử dụng ít tài nguyên ◼ Phép toán tích cực cũng là phép toán so sánh, thỏa mãn công thức truy hồi sau: ◼ CN = 2CN/2 +N ◼ Dễ dàng nhận được: CN = NlgN ◼ Chỉ sử dụng trung bình NlgN thao tác để sắp xếp N phần tử
  109. ◼ Vấn đề chọn chốt. Quyết định tính hiệu quả Cần chọn điểm chốt tốt hơn Chọn ngẫu nhiên 03 phần tử trong dãy, sau đó chọn phần tử giữa của 03 phần tử này làm phân hoạch. Chẳng hạn số hạng trái , phải, giữa. Phương pháp này đảm bảo, trường hợp xấu nhất không thể xẩy ra.
  110. 8. Sắp xếp bằng cơ số ◼ Ý tưởng Áp dụng tư tưởng phân đoạn để sắp xếp dãy khóa là số tự nhiên theo thứ tự không giảm. ◼ Sắp xếp bằng cơ số theo kiểu hoán vị các khóa Ta có thể coi mỗi số nguyên là một dãy z bit đánh số từ 0 đến z-1.
  111. Để phân đoạn ta có thể đưa các khóa có bít cao nhất bằng 0 về đầu dãy, những khóa có bit cao nhất bàng 1 về cuối dãy (vì những khóa bắt đầu bằng 0 ở bít cao nhất sẽ nhỏ hơn những khóa có bít cao nhất bằng 1). Tiếp tục phân đoạn với hai đoạn dãy khóa, một đoạn có bít cao nhất bàng 1 và một đoạn có bít cao nhất bằng 0.
  112. ◼ Ví dụ, dãy xuất phát là 1,3,7,6,,5,2,3,4,4,5,6,7 tương ứng với dãy 03 bit: ◼ 001 011 111 110 101 010 011 100 100 101 110 111 ◼ Phân đoạn dựa vào bit cao nhất ( bên trái cùng) 001 011 011 010 101 110 111 100 100 101 110 111 ◼ Pân đoạn dựa vào bít thứ 2 từ trái sang ◼ 001 011 011 010 101 101 100 100 111 110 110 111 .
  113. Tiếp tục phân đoạn dựa vào bit ở hàng đơn vị 001 010 011 011 100 100 101 101 110 110 111 111
  114. Có thể thực hiện với hệ cơ số khác bất kì Độ phức tạp thuật toán: Để phân đoạn bằng 1 bít thì cần Cn thời gian, nên thời gian phân đoạn bằng z bit se là C.N.z ( C là hằng số), vậy trường hợp xấu thì độ phức tạp thuật toán là O(N.z) còn trường hợp trung bình là O(N. min (z,lgN)
  115. 8. Sắp xếp bằng cơ số ◼ Sắp xếp bằng cơ số Sử dụng một thuật toán nào đó để sắp xếp dãy khóa tăng dần theo giá trị chữ số hàng đơn vị. Sử dụng một thuật toán sắp xếp ổn định nào đó để sắp xếp dãy khóa tăng dần theo giá trị chữ số hàng chục. Tiếp tục thực hiện tương tự với chữ số hàng trăm, ngàn,
  116. ◼ Nhận xét và đánh giá Có thể coi số chữ số của mỗi khóa là bằng nhau ( bổ sung các chữ số 0 vào bên trái mỗi số hạng còn thiếu). Độ phức tạp phụ thuộc chủ yếu vào độ phức tạp các thuật toán sắp xếp khác đã được lựa chọn.
  117. 9. Tính ổn định của thuật toán sắp xếp ◼ Một phương pháp sắp xếp được gọi là ổn định nếu nó bảo toàn thứ tự bản ghi có khóa bằng nhau trong danh sách. ◼ Trong số các thuật toán đã xét: Các thuật toán sắp xếp nổi bọt, thuật toán sắp xếp chèn là những thuâth toán ổn định, các thuật toán còn lại là không ổn định.
  118. ◼ Nói chung mọi phương pháp sắp xếp không ổn định đều có thể biến đổi để nó trở thành ổn định. Phương pháp chung là thêm một trường khóa chỉ số là thứ tự ban đầu của đối tượng. Khi đối sánh, nếu gặp các đối tượng có cùng khóa sắp xếp như nhau thì ta dựa vào thứ tự chỉ số để xếp 02 đối tượng đó theo thứ tự ban đầu.
  119. CHƯƠNG VIII: TÌM KiẾM 1. Giới thiệu 2. Thuật toán tìm kiếm tuần tự 3. Thuật toán tìm kiếm nhị phân 4. Cây tìm kiếm số học 5. Cây tìm kiếm cơ số
  120. CHƯƠNG VIII: TÌM KiẾM 1. Giới thiệu ◼ Bài toán. Cho tập N đối tượng, hãy xác định xem có hay không trong tập đó một đối tượng cụ thể. ◼ Tập đối tượng cho trước có thể có nhiều thuộc tính có kiểu dữ liệu khác nhau. Thông thường tìm kiếm chỉ căn cứ một hoặc một vài thành phần ( trường). Các thành phần đó gọi là trường khóa tìm kiếm.
  121. Quá trình tìm kiếm thường gồm 02 pha: Pha 1: Dựa vào giá trị trường khóa và khóa để xác định đối tượng có giá trị trường khóa bằng với khóa tìm kiếm hặc khẳng định không tìm thấy đối tượng cần tìm; Pha 2: Kết xuất toàn bộ thông tin về đối tượng tìm được.
  122. CHƯƠNG VIII: TÌM KiẾM ◼ Ta chỉ xét pha 1 cho bài toán: Cho một dãy gồm n đối tượng, mỗi đối tượng i ( 1<=i<=n) tương ứng với một khóa ki. Hãy tìm đối tượng có giá trị khóa bằng x cho trước. Tìm đựợc đối tựợng i có ki = x; tìm kiếm thành công; Không có đối tượng nào có khóa bằng x; tìm kiếm thất bại.
  123. 2. Tìm kiếm tuần tự ◼ Input: Dãy khóa A gồm N số nguyên k1, k2, , kn đôi một khác nhau và số nguyên x; ◼ Output: Chỉ số i mà ki = x hoặc thông báo không có số hạng nào của dãy A
  124. 2. Tìm kiếm tuần tự Ý tưởng: Một cách tự nhiên. ◼ Lần lượt từ số hạng thứ nhất, so sánh với khoá tìm kiếm x cho đến khi có sự trùng nhau. Nếu đã xét tới kn mà không xảy ra sự trùng nhau thì dãy khóa không chứa giá trị x tìm kiếm.
  125. 2. Tìm kiếm tuần tự Thuật toán Bước 1. Nhập N, X và k1, k2, , kn ; Bước 2. i  1; Bước 3. Nếu ki = x thì thông báo I; Kết thúc. Bước 4. i  i + 1; Bước 5. Nếu i>N thì Thông báo không có số hạng nào có giá trị trùng với x, rồi kết thúc. Bước 6. Quay lại bước 3.
  126. Mô phỏng các bước thực hiện của thuật toán k = 2 và N = 10 k = 6 và N = 10 A 5 7 1 4 2 9 8 11 25 51 A 5 7 1 4 2 9 8 11 25 51 i 1 2 3 4 5 - - - - - i 1 2 3 4 5 6 7 8 9 10 11 Với i = 5 thì a5 = 2. Với mọi i từ 1 đến 10 không có ai có giá trị bằng 6.
  127. ◼ Nhận xét và đánh giá. Phép toán tích cực là phép so sánh: Trường hợp tốt nhất độ phức tạp là O(1) Trường hợp xấu nhất và trung bình độ phức tạp là O(N)
  128. CHƯƠNG VIII: TÌM KiẾM 3. Tìm kiếm nhị phân ◼ Input: Dãy gồm N số nguyên k1, k2, , kN đôi một khác nhau và là dãy tăng; số nguyên x. ◼ Output: Chỉ số i mà ki = x hoặc thông báo trong dãy không có giá trị trùng với x.
  129. ◼ Ý tưởng: Sử dụng dãy đã sắp xếp ta tìm cách thu hẹp phạm vi tìm kiếm sau mỗi lần so sánh khóa với số hạng được chọn. aGiua Giua=[ (N+1)/2].
  130. Nếu kGiua = x thì Giua là chỉ số cần tìm. Nếu kGiua > k thì việc tìm kiếm tiếp theo chỉ xét trên dãy k1, ka2, , kGiua–1 Nếu aGiua < k thì thực hiện tìm kiếm trên dãy kGiua+1, kGiua+2, , kN. Quá trình trên sẽ được lặp lại
  131. 3. Tìm kiếm nhị phân Thuật toán Bước 1. Nhập N, k1 k2, , kn và giá trị khóa x. Bước 2. Dau  1, Cuoi  N Giua  . Bước 4. Nếu kGiua = x thì thông báo chỉ số Giua, rồi kết thúc Bước 5. Nếu kGiua > x thì đặt Cuoi = Giua – 1 rồi chuyển đến bước 7. Bước 6. Dau  Giua + 1 Bước 7. Nếu Dau > Cuoi thì thông báo dãy không có số hạng có giá trị trùng với x, rồi kết thúc. Bước 8. Quay lại bước 3.
  132. k = 21, N =10 k = 25, N =10 i 1 2 3 4 5 6 7 8 9 10 i 1 2 3 4 5 6 7 8 9 10 A 2 4 5 6 9 21 22 30 31 33 A 2 4 5 6 9 21 22 30 31 33 Dau 1 6 6 Dau 1 6 6 7 8 Cuoi 10 10 7 Cuoi 10 10 7 7 7 Giua 5 8 6 Giua 5 8 6 7 aGiua 9 30 21 aGiua 9 30 21 22 Lượt 0 1 2 Lượt 0 1 2 3 4 Sau hai lượt thì aGiua = k. Vậy chỉ số cần tìm là i = Giua = 6. Tại lượt thứ tư Dau > Cuoi nên kết luận trong dãy A không có toán hạng nào có giá trị là 25 cả.
  133. ◼ Nhận xét và đánh giá Trường hợp tốt nhất, độ phức tạp tính toán là O(1), trong trường hợp xấu và trung bình là O(lgN) , Tuy nhiên với dãy chưa được sắp xếp thì cần có chi phí cho việc sắp xếp.
  134. 4. Cây tìm kiếm số học ◼ Định nghĩa Xét dãy khóa k1, k2, kn mỗi giá trị khóa khi đổi ra số nhị phân có z bit, đánh số từ 0 đến z-1 ( phải-trái)
  135. Cây tìm kiếm số học Cây số học chứa các giá trị khóa: Là cây nhị phân, mỗi nút chứa một giá trị khóa; Nút gốc có tối đa 02 cây con; tất cả các khóa có bít cao nhất là 0 nằm ở cây con trái, tất cả các khóa có bít cao nhất là 1 nằm ở cây con phải. Cây con trái và phải cũng có tính chất như vậy.
  136. 6 6 = 0110 5 = 0101 2 = 0010 0 1 7 = 0111 8 = 1000 10 = 1010 12 = 1100 11 = 1011 5 8 4 = 0100 0 1 0 1 2 7 10 12 0 1 4 11
  137. 4. Cây tìm kiếm số học ◼ Phép toán tìm kiếm Từ gốc, xét lần lượt các bit của x từ trái sang phải, nếu gặp bit 0 thì đi sang cây con trái, nếu gặp bit 1 thì sang cây con phải; Hoặc đi tới một nút rỗng, tìm kiếm thất bại (không có giá trị x trong dãy khóa); Hặc gặp nút có giá trị bằng x, tìm kiếm thành công.
  138. ◼ Phép chèn: Tìm xem khóa đã có trong cây hay chưa, nếu chưa có thì thêm nút mới chứa khóa cần chèn và nối nút đó vào cây tại nút rỗng vừa sẽ sang khiến tìm kiếm thất bại.
  139. ◼ Phép xóa Tìm kiếm để xác định nút cần xóa; Tìm trong cây con mà nút cần xóa là nút gốc một nút lá bất kì; Chuyển đổi giá trị của nút lá và nút cần xóa cho nhau; Xóa nút lá.
  140. ◼ Nhận xét và đánh giá Độ phức tạp trong các trường hợp là O(min(z,lgN)), trường hợp xấu nhất là O(z) vì chiều cao của cây tìm kiếm số học không quá z+1.
  141. 5. Cây tìm kiếm cơ số Cây tìm kiếm cơ số là: Là một cây nhị phân, chỉ có nút lá chứa giá trị khóa và các nút lá đều ở cùng mức z-1; Nút gốc có tối đa là 02 nhánh con Mọi nút lá của nhánh con trái đều có bít z-2 là 0 ( đều bắt đầu bằng 00);
  142. Mọi nút lá của nhánh con phải đều có bít z-2 là 1 ( đều bắt đầu bằng 01); Tổng quát, với nút mức d đều có tối đa hai nhánh con, mọi nút lá của nhánh con trái đều có bít z-d là 0 và mọi nút lá của nhánh con phải đều có bit z-d là 1 Cây tìm kiếm cơ số được khởi tạo gồm 01 nút gốc và nút đó tồn tại trong suốt cả quá trình.
  143. CHƯƠNG VIII: TÌM KiẾM 5. Cây tìm kiếm cơ số Thao tác tìm kiếm khóa X: Xuất phát từ nút gốc, duyệt dãy bít của x từ trái sang phải ( từ bít z-1 đến bit 0), gặp nút 0 thì rẽ sang trái, gặp nút 1 thì sang phải; Quá trình sẽ dừng lại khi: Hoặc đi tới một nút rỗng, tìm kiếm thất bại Nút ở lá có giá trị trùng nút x
  144. ◼ Thao tác chèn: Thực hiện các thao tác như tìm kiếm, khi gặp một liên kết null ( đi tới nút rỗng) thì tạo nút mới và nối vào theo liên kết đó để có đường đi tiếp. Sau khi duyệt hết các bit của x, dừng lại nút lá của cây và đưa giá trị của x vào nút lá đó.
  145. 5. Cây tìm kiếm cơ số ◼ Thao tác xóa Lặp lại quá trình tìm kiếm; Đánh dấu để biết nút có 02 con cuối cùng (từ nút đó chỉ có một con đường độc đạo đến nút lá); Xóa toàn bộ các nút của đường độc đạo.
  146. Giá trị chứa trong các nút cành là vô nghĩa nên sẽ có lãng phí bộ nhớ, Không nhất thiết phải chọn hệ cơ số 2, có thể chọn cơ số lớn hơn để đẩy nhanh tốc độ tìm kiếm nhưng sẽ tốn kém bộ nhớ hơn
  147. ◼ Nhận xét và đánh giá Việc xóa tất cả các nút trên đường độc đạo là để tiết kiệm bộ nhớ , Hình dáng của cây chỉ phụ thuộc vào các giá trị chứa trong cây, Độ phức tạp trong mọi trường hợp đều là O(z),
  148. ◼ Chú ý chung Hai bài toán sắp xếp và tìm kiếm rất đặc thù của Tin học. Không nên đánh giá các thuật toán sắp xếp cũng như các thuật toán tìm kiếm một cách tổng quát mà còn tùy thuộc vào yêu cầu cụ thể, tính chất dữ liệu cụ thể,