›

Bài giảng Cấu trúc dữ liệu và giải thuật - Bài 9: Cây - Hoàng Thị Điệp

pdf 44 trang huongle 4260
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 - Bài 9: Cây - Hoàng Thị Điệp", để 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:

  • pdfbai_giang_cau_truc_du_lieu_va_giai_thuat_bai_9_cay_hoang_thi.pdf

Nội dung text: Bài giảng Cấu trúc dữ liệu và giải thuật - Bài 9: Cây - Hoàng Thị Điệp

  1. Bài 9: Cây Giảng viên: Hoàng Thị Điệp Khoa Công nghệ Thông tin – Đại học Công Nghệ Cấu trúc dữ liệu và giải thuật HKI, 2013-2014
  2. Nội dung chính 1. Các khái niệm cơ bản 2. Duyệt cây 3. Cây nhị phân 4. Cây tìm kiếm nhị phân
  3. Giới thiệu  Ví dụ: tập hợp các thành viên trong một dòng họ Computers”R”Us với quan hệ cha – con  Trong ngành công nghệ thông tin, cây là mô hình Sales Manufacturing R&D trừu tượng của một cấu trúc phân cấp  Một cây bao gồm các đỉnh với quan hệ cha – US International Laptops Desktops con  Ứng dụng  Sơ đồ tổ chức Europe Asia Canada  Hệ thống file  Các môi trường lập trình 3 diepht@vnu
  4. Định nghĩa cây 1. Toán học: thông qua đồ thị định hướng 2. Đệ quy 4 diepht@vnu
  5. Đồ thị định hướng  Đồ thị  là một mô hình toán học  biểu diễn một tập đối tượng có quan hệ với nhau theo một cách nào đó  Một đồ thị định hướng G = (V,E)  Gồm một tập hữu hạn V các đỉnh và một tập E các cung  Mỗi cung là một cặp có thứ tự các đỉnh khác nhau (u,v)  (u,v) và (v,u) là hai cung khác nhau. 5 diepht@vnu
  6. Cây & Đồ thị định hướng  Cây là một đồ thị định hướng thỏa mãn các tính chất sau  Có một đỉnh đặc biệt được gọi là gốc cây  Mỗi đỉnh C bất kỳ không phải là gốc, tồn tại duy nhất một đỉnh P có cung đi từ P đến C. Đỉnh P được gọi là cha của đỉnh C, và C là con của P  Có đường đi duy nhất từ gốc tới mỗi đỉnh của cây. A mức 0 gốc B C D mức 1 đỉnh trong lá mức 2 E F G 6 diepht@vnu
  7. Các thuật ngữ (1/2)  Trong cây nếu có đường đi từ đỉnh A tới đỉnh B thì A được gọi là tổ tiên của B, hay B là con cháu của A  Các đỉnh cùng cha được xem là anh em A  Các đỉnh không có con được gọi là lá  Một đỉnh bất kỳ A cùng với tất cả các con cháu của nó lập thành một cây gốc là A. Cây này được B C D gọi là cây con của cây đã cho.  Độ cao của một đỉnh là độ dài đường đi dài nhất từ đỉnh đó tới một lá.  Độ cao của lá bằng 0. E F G  Độ cao của cây là độ cao của gốc  Độ sâu của một đỉnh là độ dài đường đi từ gốc tới đỉnh đó  Độ sâu của gốc bằng 0. 7 diepht@vnu
  8. Các thuật ngữ (2/2)  Cây là một CTDL phân cấp: Các đỉnh của cây được phân thành các mức. A  Gốc ở mức 0 B C D  Mức của một đỉnh = mức của đỉnh cha + 1  Cây được sắp: các đỉnh con của E F G mỗi đỉnh được sắp sếp theo một thứ thứ tự xác định 8 diepht@vnu
  9. Ví dụ: Cây biểu thức * + - / 3 7 4 6 2 9 diepht@vnu
  10. KDLTT cây Tree  Sử dụng position để trừu  Phương thức truy vấn: tượng hóa các đỉnh  bool isInternal(p) // đỉnh trong?  Phương thức chung:  bool isExternal(p) // lá?  int size()  bool isRoot(p) // gốc?  bool isEmpty()  Phương thức cập nhật:  objectIterator elements()  swapElements(p, q)  positionIterator positions()  object replaceElement(p, o)  Phương thức truy cập:  Có thể định nghĩa thêm  position root() phương thức cập nhật  position parent(p)  tùy theo CTDL được sử dụng  positionIterator children(p) để cài đặt KDLTT cây 10 diepht@vnu
  11. Cài đặt bằng cách chỉ ra danh sách các đỉnh con template class Node{ T data; root list *> children; }; A Node * root; B C D E F G 11 diepht@vnu
  12. Cài đặt bằng cách chỉ ra con cả và em liền kề root template class Node{ T data; A Node * firstChild; Node * nextSibling; }; Node * root; B C D E F G 12 diepht@vnu
  13. Bài tập: Điền vào chỗ trống trong bảng root = 300 A Địa chỉ Data FirstChild NextSibling B C D 100 C 200 B 250 D 300 A E F G 400 F 500 G 600 E 13 diepht@vnu
  14. Bài tập: Vẽ cây cha-con Định dạng input.txt  Dòng đầu chứa tên ở Robert gốc Robert: Bo  Mỗi dòng tiếp theo Bo: Ron chứa tên cha: tên con Bo: Ali Robert: Jill Robert: Kath 14 diepht@vnu
  15. Nội dung chính 1. Các khái niệm cơ bản  2. Duyệt cây 3. Cây nhị phân 4. Cây tìm kiếm nhị phân
  16. Duyệt cây  Thứ tự trước (preorder)  Thứ tự trong (inorder)  Thứ tự sau (postorder) r r1 r2 rk T1 T2 Tk 16 diepht@vnu
  17. Duyệt theo thứ tự trước  Thăm gốc r. A  Duyệt lần lượt các cây B C D con T1, , Tk theo thứ tự trước  Còn được gọi là kỹ E F G thuật tìm kiếm theo độ sâu A-B-E-F-C-D-G 17 diepht@vnu
  18. Preorder  Thuật toán Algorithm preOrder(r) visit(r) for each child s of r  Ứng dụng preOrder (s)  In một văn bản có cấu trúc 1 Make Money Fast! 2 5 9 1. Motivations 2. Methods References 6 7 8 3 4 2.1 Stock 2.2 Ponzi 2.3 Bank 1.1 Greed 1.2 Avidity Fraud Scheme Robbery 18 diepht@vnu
  19. Duyệt theo thứ tự trong  Duyệt cây con trái T1 A theo thứ tự trong B C  Thăm gốc r  Duyệt lần lượt các cây con T , , T theo 2 k D E F thứ tự trong D-B-E-A-F-C 19 diepht@vnu
  20. Inorder Algorithm inOrder(r) if isInternal (r) then inOrder (leftChild (r)) visit(r) if isInternal (r) then sleftChild(r) while hasNextSibling(s) do snextSibling(s) inOrder(s) 20 diepht@vnu
  21. Duyệt theo thứ tự sau  Duyệt lần lượt các cây A con T1, Tk theo thứ tự B C D sau  Thăm gốc r. E F G E-F-B-C-G-D-A 21 diepht@vnu
  22. Postorder  Thuật toán Algorithm postOrder(r) for each child s of r postOrder (s)  Ứng dụng visit(r)  Tính toán dung lượng file và các thư mục con của một thư mục 9 cs16/ 8 3 7 todo.txt homeworks/ programs/ 1K 1 2 4 5 6 h1c.doc h1nc.doc DDR.java Stocks.java Robot.java 3K 2K 10K 25K 20K 22 diepht@vnu
  23. Nội dung chính 1. Các khái niệm cơ bản  2. Duyệt cây  3. Cây nhị phân 4. Cây tìm kiếm nhị phân
  24. Cây nhị phân  Cây nhị phân là cây được sắp  Ứng dụng: với các tính chất sau:  biểu thức số học  Mỗi đỉnh có nhiều nhất 2 con  xử lý quyết định  Đỉnh con của một đỉnh được  tìm kiếm gọi là con trái hoặc con phải  Đỉnh con trái đứng trước đỉnh con phải A  Cây nhị phân được gọi là chuẩn (proper) nếu mỗi đỉnh có 2 con hoặc không có con B C nào  tức là mỗi đỉnh trong có chính xác 2 con D E F G  cây nhị phân không có tính chất này thì gọi là không chuẩn (improper) H I 24 diepht@vnu
  25. Cây biểu thức số học  Cây nhị phân biểu diễn một biểu thức số học  đỉnh trong: toán tử  lá: toán hạng  Ví dụ: cây cho biểu thức (2 × (a − 1) + (3 × b)) + × × 2 − 3 b a 1 25 diepht@vnu
  26. Cây quyết định  Cây nhị phân biểu diễn quy trình ra một quyết định  đỉnh trong: câu hỏi với câu trả lời yes/no  lá: quyết định  Ví dụ: quyết định chọn cửa hàng ăn Want a fast meal? Yes No How about coffee? On expense account? Yes No Yes No Starbucks Spike’s Al Forno Café Paragon 26 diepht@vnu
  27. Tính chất của cây nhị phân chuẩn  Kí hiệu • Tính chất: n số lượng đỉnh  e = i + 1 e số lượng lá  n = 2e - 1 i số lượng đỉnh trong  h ≤ i h độ cao (đếm số cạnh  h ≤ (n - 1)/2 trên đường đi dài nhất  e ≤ 2h từ gốc đến lá)  h ≥ log2 e  h ≥ log2 (n + 1) - 1 n=7, e=4, i=3, h=3 n=7, e=4, i=3, h=2 27 diepht@vnu
  28. KDLTT cây nhị phân BinaryTree  KDLTT cây nhị phân BinaryTree thừa kế KDLTT cây Tree  Bổ sung các phương thức:  position leftChild(p)  position rightChild(p)  position sibling(p)  Các phương thức cập nhật có thể được định nghĩa theo CTDL cài đặt KDLTT cây nhị phân 28 diepht@vnu
  29. Cài đặt cây nhị phân template A class Node{ T data; Node * left; B C Node * right; root }; D E F Node * root; A B C G D E F G 29 diepht@vnu
  30. Bài tập: Vẽ cây có root = 60 Địa chỉ đỉnh data left right 10 8 70 30 20 3 80 0 30 10 100 0 40 1 50 90 50 6 0 0 60 14 10 40 70 4 0 0 80 7 60 20 90 13 0 0 100 5 0 0 30 diepht@vnu
  31. Duyệt cây nhị phân theo thứ tự giữa  Mô tả thủ tục Algorithm inOrder(v)  duyệt cây con trái của r theo if isInternal (v) thứ tự giữa inOrder (leftChild (v))  thăm đỉnh r visit(v)  duyệt cây con phải của r theo thứ tự giữa if isInternal (v)  Ứng dụng: vẽ một cây nhị inOrder (rightChild (v)) phân  x(v) = số thứ tự của v trong kết 6 quả duyệt inorder  y(v) = độ sâu của v 2 8 1 4 7 9 3 5 31 diepht@vnu
  32. Nội dung chính 1. Các khái niệm cơ bản  2. Duyệt cây  3. Cây nhị phân  4. Cây tìm kiếm nhị phân
  33. KDLTT tập động: các phép toán chính S ký hiệu một tập, k là một giá trị khoá và x là một phần tử dữ liệu.  insert(S, x). Thêm phần tử x vào tập S.  erase(S, k). Loại khỏi tập S phần tử có khoá k.  find(S, k). Tìm phần tử có khoá k trong tập S.  max(S). Trả về phần tử có khoá lớn nhất trong tập S.  min(S). Trả về phần tử có khoá nhỏ nhất trong tập S. insert + erase + find => KDLTT từ điển (dictionary ADT) 33 diepht@vnu
  34. Cài đặt KDLTT tập động insert erase find Bằng mảng ? ? ? Bằng mảng được sắp ? ? ? Bằng DSLK đơn ? ? ? Bằng cây tìm kiếm nhị phân ? ? ? 34 diepht@vnu
  35. Cài đặt KDLTT tập động insert erase find Bằng mảng ? ? ? Bằng mảng được sắp O(N) O(N) O(logN) Bằng DSLK đơn O(N) O(N) O(N) Bằng cây tìm kiếm nhị phân ? ? ? 35 diepht@vnu
  36. Cài đặt cây nhị phân  Biểu diễn đỉnh bởi một đối tượng bao gồm:  Phần tử dữ liệu ∅  Địa chỉ đỉnh cha  Địa chỉ đỉnh con trái  Địa chỉ đỉnh con phải B ∅ ∅ B A D A D ∅ ∅ ∅ ∅ C E C E 36 diepht@vnu
  37. Cây tìm kiếm nhị phân  Cây tìm kiếm nhị phân là cây  Duyệt cây tìm kiếm nhị phân nhị phân lưu khóa (hoặc cặp theo thứ tự trong sẽ thăm các khóa - dữ liệu) ở các đỉnh khóa theo thứ tự tăng dần trong của nó và thỏa mãn tính chất sau:  Gọi u, v, w là 3 đỉnh sao cho u nằm trong cây con trái của v và w nằm trong cây con phải của v. Ta có 6 key(u) ≤ key(v) ≤ key(w)  Các lá tạm thời không lưu dữ 2 9 liệu 1 4 8 37 diepht@vnu
  38. Tìm kiếm đỉnh có khóa k  Để tìm khóa k, ta lần theo Algorithm TreeSearch(k, v) đường đi xuất phát từ gốc if T.isExternal (v)  Xác định đỉnh cần thăm tiếp return v theo dựa trên so sánh k với if k key(v) }  Ví dụ: find(4): return TreeSearch(k, T.right(v))  gọi tới TreeSearch(4,root) 9 1 4 = 8 38 diepht@vnu
  39. Thêm đỉnh có khóa k 6  Để thực hiện insert(k, o), ta  Giả sử k không có trong cây, 1 4 8 gọi w là lá trả về bởi phép tìm > kiếm  Ta thêm k vào đỉnh w và phát w triển w thành đỉnh trong 6  Ví dụ: insert 5 2 9 1 4 8 w 5 39 diepht@vnu
  40. Loại bỏ đỉnh có khóa k (1/2)  Để thực hiện erase(k), ta tìm 6 khóa k là đỉnh chứa k 1 4 v 8  Nếu đỉnh v có 1 lá w, ta loại bỏ w v và w khỏi cây bằng phép 5 toán eraseExternal(w). Phép toán này loại w và cha của nó  Ví dụ: erase 4 6 2 9 1 5 8 40 diepht@vnu
  41. Loại bỏ đỉnh có khóa k (2/2)  Trường hợp k được lưu ở đỉnh 1 v có cả 2 con là đỉnh trong v 3  ta tìm đỉnh trong w đứng sau v trong phép duyệt theo thứ tự 2 8 giữa 6 9  sao key(w) vào đỉnh v w  ta loại đỉnh w và con trái z của 5 nó (z phải là một lá) bằng z phép toán eraseExternal(z)  Ví dụ: erase 3 1 v  Phương án khác? 5 2 8 6 9 41 diepht@vnu
  42. Phân tích độ phức tạp  Xét tập hợp có n phần tử cài đặt bởi cây tìm kiếm nhị phân độ cao h  không gian sử dụng là O(n)  các hàm find, insert và erase thực hiện trong thời gian O(h)  Độ cao h bằng O(n) trong trường hợp xấu nhất và O(log n) trong trường hợp tốt nhất 42 diepht@vnu
  43. Nội dung chính 1. Các khái niệm cơ bản  2. Duyệt cây  3. Cây nhị phân  4. Cây tìm kiếm nhị phân 
  44. Chuẩn bị 2 tuần tới  Tuần 8  Giờ thực hành: Cây  Giờ lý thuyết: Kiểm tra giữa kì  viết 90 phút  không sử dụng tài liệu  Tuần 9  Thực hành: Cây TKNP  Lý thuyết: Đọc chương 9 giáo trình (Bảng băm) 44 diepht@vnu