›
›

Bài giảng Thiết kế và đánh giá thuật toán - Chương 6: Cấu trúc cây - Lê Nguyên Khôi

pdf 35 trang ngocly 70
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Thiết kế và đánh giá thuật toán - Chương 6: Cấu trúc cây - Lê Nguyên Khôi", để 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_thiet_ke_va_danh_gia_thuat_toan_chuong_6_cau_truc.pdf

Nội dung text: Bài giảng Thiết kế và đánh giá thuật toán - Chương 6: Cấu trúc cây - Lê Nguyên Khôi

  1. ế ế ậ ấ ườ ạ ọ ệ
  2. ộ  Khái ni m c b n  Duy t cây  Cây nh phân  Cây tìm ki m nh phân  Cây tìm ki m nh phân cân bng  Cây th t b ph n 1
  3. ạ  Cây t do ( th )  th – mng  Vô h ư ng, có hư ng  Tr ng s  Liên thông  Chu trình, phi chu trình  Cây có gc  Có 1 nh ư c coi là g c  Quan h cha - con 2
  4. ự ồ ị vô hư ng nh h ư ng Cu Gi y Cu Gi y HQG BX Kim Mã HQG BX Kim Mã Ngã tư S Ngã tư S 3
  5. ự ồ ị tr ng s không tr ng s Cu Gi y Cu Gi y 5 7 HQG BX Kim Mã HQG BX Kim Mã 11 15 Ngã tư S Ngã tư S 4
  6. ự ồ ị liênthông khôngliênthông 5
  7. ự ồ ị chutrình phi chutrình 6
  8. ự ồ ị  Mng vn ti  Mng liên lc  Mng thông tin  Mng xã hi  Mng ph thu c 7
  9. ố ị a  S dng khái ni m th có hư ng  Có m t nh c bi t ư c g i là g c cây  Mi nh C b t k không ph i là g c, t n ti duy nh t m t nh P có ư ng i t P n C. nh Parent ư c g i là cha c a nh Child , và Child là con c a Parent .  Có ư ng i duy nh t t g c t i m i nh ca cây. 8
  10. ố ụ A mc 0 gc B C D mc 1 nh trong lá E F G mc 2 9
  11. ố ậ ữ  cao (height)  ca mt nh là dài ư ng i dài nh t t nh ó t i m t lá.  cao c a lá b ng 0.  cao c a cây là cao c a g c  sâu (depth)  ca mt nh là dài ư ng i t g c t i nh ó  sâu c a g c b ng 0. 10
  12. ố ộ a  cao ca mt nh là dài ư ng i dài nh t t nh ó ti m t lá. A  Xác inh cao ca mi nh B C D ℎ = max ℎ() + 1 ∀ E F G 11
  13. ể ứ +++ /// 333 777 444 666 222 12
  14. ệ  Th t tr ư c (preorder)  Th t trong (inorder)  Th t sau (postorder) r r r 1 2 rk T1 T2 Tk 13
  15. ệ ứ ự ướ  Th m gc r r  Duy t ln lư t các cây r r 1 rk con T1, , Tk theo th 2 t tr ư c  Còn ư c bi t n là T1 T2 Tk k thu t tìm ki m theo sâu A B C D A-B-E-F-C-D-G E F G 14
  16. ệ ứ ự ướ ả Algorithm preOrder(p) visit(p) for each child ci of p preOrder(c i) 15
  17. ệ ứ ự r  Duy t cây con trái T1 theo th t trong r r 1 rk  Th m gc r 2  Duy t ln lư t các cây T T T con T2, , Tk theo th 1 2 k t trong A B C D E-B-F-A-C-G-D E F G 16
  18. ệ ứ ự ả Algorithm inOrder(p) inOrder(c 1) visit(p) for each child ci of p inOrder(c i) 17
  19. ệ ứ ự a  Duy t ln lư t các cây r con T1, , Tk theo th r r r t sau 1 k 2  Th m gc r T1 T2 Tk A B C D E-F-B-C-G-D-A E F G 18
  20. ệ ứ ự a ả Algorithm postOrder(p) for each child c i of p postOrder(c i) visit(p) 19
  21. ị  Mi nh có nhi u nh t 2 nh con  Nh phân chu n (full/proper binary tree)  Mi nh có 0 ho c 2 nh con  Nh phân y (complete binary tree)  Các lá cùng m c  Nh phân g n y (almost complete binary tree)  Có con ph i thì có con trái 20
  22. ị ầ ủ  cao ℎ có 2 − 1 lá  lá có cao log + 1 21
  23. ế ị  Cây tìm ki m nh phân là cây nh phân lưu khóa các nh trong c a nó và th a mãn tính ch t sau:  Gi , , là 3 nh sao cho nm trong cây con trái c a và nm trong cây con ph i ca , th a mãn () ≤ () ≤ ()  Duy t cây tìm ki m nh phân theo th t trong s th m các khóa theo th t t ng dn 22
  24. ế ị  Mt s thao tác chính:  Tìm ki m:  nh có khóa  nh tr ư c/sau nh có khóa  nh có khóa min/max  Sa i:  thêm nh có khóa 6  xóa nh có khóa  Mã gi 2 9 1 4 8  ph c tp 23
  25. ế ị ằ  Cây tìm ki m nh phân cân bng có cu trúc ca cây tìm ki m nh phân nh ưng m bo cao ca cây là (log )  Ví d:  Cây AVL  Tìm ki m nhanh  Cây -en  Sa i nhanh 24
  26. ứ ự ộ ậ a  Cây nh phân gn y :  Có tt c các mc ca cây u không thi u nh nào, tr mc th p nh t ư c lp y k t bên trái  cao là log 0 2 1 5 2 3 5 39 4 7 8 25
  27. ứ ự ộ ậ a  Min heap là cây nh phân gn y vi tính ch t:  Khóa ca mt nh bt k NH Ỏ hn ho c bng khóa ca các nh con ca nó.  Max heap là cây nh phân gn y vi tính ch t:  Khóa ca mt nh bt k LỚN hn ho c bng khóa ca các nh con ca nó. 26
  28. ứ ự ộ ậ a  Mt s thao tác chính:  Tìm nh nh t  Xóa nh nh t  Chèn 0 2 1 5 2 3 5 39 4 7 8 27
  29. a a ỏ ấ  Thay th gc bng nh cu i cùng  Gi i phóng nh cu i cùng  Khôi ph c tính ch t th t b ph n ca heap  Downheap khôi ph c li tính ch t bng cách o ch nh có khóa dc theo ư ng i t gc xu ng  Downheap dng khi ti n ti mt lá hay mt nh có khóa con ln hn 0 2  ph c tp: (log ) 1 5 2 3 5 39 4 7 8 28
  30. a a ỏ ấ  Thay th gc bng nh cu i 0 2 0 8 1 5 2 3 1 5 2 3 5 5 39 4 7 8 39 4 7  Downheap 0 0 8 3 1 5 2 8 1 5 2 3 3 4 39 4 7 9 7 29
  31. a  Tìm ti v trí ư a ph n t mi vào  Lưu ph n t có khóa vào nh ó  Khôi ph c tính ch t th t b ph n ca heap  Upheap khôi ph c li tính ch t bng cách o ch nh có khóa dc theo ư ng i t nh ti gc  Upheap dng khi ti n ti gc hay mt nh có khóa cha nh hn 0 2  ph c tp: (log ) 1 5 2 3 5 39 4 7 1 30
  32. a  Thêm nh cu i mi 0 2 0 2 1 5 2 3 1 5 2 3 5 5 39 4 7 39 4 7 1  Upheap 0 2 0 2 1 1 5 2 3 5 2 1 5 5 39 4 7 1 39 4 7 3 31
  33. ắ ế ứ ự ộ ậ  Liên tc xóa nh nh t ca Min heap s ư c mt dãy tng dn  ph c tp: ( log )  Xây dng Min heap  Ln lư t chèn các khóa vào cây Min heap, bt u t cây Min heap rng  ph c tp: ( log ) 0 2 1 5 2 3 5 39 4 7 8 32
  34. ự a  Chèn liên tc vào Min Heap, nh ưng không khôi ph c tính ch t th t b ph n.  Khôi ph c tính ch t th t b ph n (s dng downheap) bt u t nh chính gi a  Xem tr.158 33
  35. ắ ế ứ ự ộ ậ  Gi ng sp xp gp (merge sort)  ph c tp log  Gi ng sp xp chèn (insertion sort)  In-place algortihm 34