›

Bài giảng Thiết Kế và Đánh Giá Thuật Toán - Cây Tìm Kiếm Nhị Phân - Lê Nguyên Khôi

pdf 22 trang huongle 4080
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 - Cây Tìm Kiếm Nhị Phân - 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_cay_tim_kiem_nhi_p.pdf

Nội dung text: Bài giảng Thiết Kế và Đánh Giá Thuật Toán - Cây Tìm Kiếm Nhị Phân - Lê Nguyên Khôi

  1. ế ế ậ ế ị ườ ạ ọ ệ
  2. ộ  Cây tìm ki m nh phân (TKNP)  Dng cây TKNP  Cây TKNP cân bng  Cây - en  Cây AVL  Cây Treap 1
  3. ị a  Cây TKNP:  cây nh phân  lưu khóa nh trong  lá rng  th a mãn tính ch t: ≤ ≤  trong cây con trái c a  trong cây con ph i c a 6 2 9 1 4 8 2
  4. a  Cây TKNP th c hi n các tao thác chính  Truy vn: không thay i cu trúc cây TKNP  Tìm ki m (SEARCH )  Nh nh t (MINIMUM )  Ln nh t (MAXIMUM )  Tr ư c (PREDECESSOR )  Sau (SUCCESSOR )  Sa i: thay i cu trúc cây TKNP  Chèn (INSERT )  Xóa (DELETE ) 3
  5. ấ  trong cây con trái c a , trong cây con ph i c a ≤ ≤  Duy t cây TKNP theo th t trong, th m các khóa theo th t tng dn  S dng cây TKNP cho  cài t t in  Cây th t b ph n (heap)  là cây tìm ki m  là cây nh phân  không ph i cây TKNP  dùng qu n lý hàng i ưu tiên 4
  6. ộ ứ ạ ờ a  ℎ ô cao ca cây  ln ca cây (s nh trong)  Th i gian (ℎ), vi các thao tác chính  Cây TKNP y ℎ = log  Cây TKNP là mt xích nút ℎ = 6 6 2 9 9 1 4 8 10 8 5
  7. ấ ế Tree-Search (,) 1 if = NIL or = . 2 return 3 if < . 4 return Tree-Search (. ,) 5 else return Tree-Search (. ℎ ,) 6 = 4: 6 2 9 = 4: 6 → 2 → 4 1 4 8 = 7: 6→ 9 → 8 → NIL 6
  8. ấ ế Iterative-Tree-Search (,) 1 while ≠ NIL and ≠ . 2 if < . 3 ← . 4 else ← . ℎ 5 return 6 Tìm = 4: 6 2 9 Tìm = 4: 6 → 2 → 4 1 4 8 Tìm = 7: 6→ 9→ 8 → NIL 7
  9. ấ ỏớ ấ Tree-Minimum () 1 while . ≠ NIL 2 ← . 3 return 6 Nh nh t: 6 → 2 → 1 2 9 1 4 8 Tree-Maximum () 1 while . ℎ ≠ NIL 2 ← . ℎ 3 return Ln nh t: 6 → 9 8
  10. ấ ướ Tree-Predecessor () 1 if . ≠ NIL 2 return Tree-Maximum (. ) 3 = . 4 while ≠ NIL and = . 5 = 6 = . 7 return 6 2 9 Tr ư c: = 6: 6 → 2 → 4 1 4 8 Tr ư c: = 8: 8 → 9 → 6 9
  11. ấ a Tree-Succesor () 1 if . ℎ ≠ NIL 2 return Tree-Minimum (. ℎ ) 3 = . 4 while ≠ NIL and = . ℎ 5 = 6 = . 7 return 6 2 9 Sau: = 6: 6 → 9 → 8 1 4 8 Sau: = 4: 4 → 2 → 6 10
  12. ửa ổ Tree-Insert (,) 1 = NIL 2 = . 6 3 while ≠ NIL 4 = 2 9 5 if . < . 1 4 8 6 = . 7 else = .ℎ 7 8 . = 9 if = NIL 10 . = 11 elseif . < . 12 . = 13 else . ℎ = 11
  13. ửa ổ a  Xóa nút kh i cây cây, 3 tr ư ng hp  không có con  xóa  ch có 1 con trái ho c ph i  chuy n con ó lên thay  có c con trái và ph i  chuy n ln nh t cây con trái ho c nh nh t cây con ph i (′) lên thay  xóa ′  Lưu ý: khi xóa nên gi m cao ca cây nu có th 12
  14. ự  Các thao tác chính trong th i gian (ℎ)  Dng cây TKNP có cao (ℎ) càng nh càng tt  Dng cây TKNP:  Chèn liên tc khóa vào cây, bt u t cây rng  Ti mi nút, cây con trái và ph i cân bng  Ch n khóa nào cho nút  Vn tư ng t nh ư ch n ph n t ch t trong phân ho ch ca thu t toán Sp Xp Nhanh  Ch n ng u nhiên khóa chèn vào cây  cao trung bình ℎ = (log ) 13
  15. ấ ề  Cn sa Tree-Insert Tree-Insert (,) x lý khóa trùng nhau trong 1 = NIL 2 cây TKNP = . 3 while ≠ NIL  Cách 1: ch n ng u nhiên cây 4 = con trái/ph i 5 if . < . 6 = .  Cách 2: da vào 7 else = .ℎ ch n cây con trái/ph i 8 . =  Cách 3: s dng danh sách 9 if = NIL lưu khóa trùng 10 . = 11 elseif . < . 12 . = 13 else . ℎ = 14
  16. ằ  cao ca cây TKNP cn nh các thao tác chính th c hi n nhanh  Nu cây TKNP “cân bng” th c hi n các thao tác trong (log )  Tính ch t “cân bng” có th b phá v vi thao tác sa i (Chèn/Xóa)  Sa li cu trúc cây thông qua phép xoay  Hai lo i cây TKNP “cân bng”  Cây - en  Cây AVL 15
  17. ỏ  Mi nút cn thêm 1-bit màu  Tính ch t  1. Mi nút là ho c en  2. Gc và lá (NIL ) en  3. Nu mt nút , thì con ca nó en  4. Mi ư ng i t mt nút n các lá con có cùng s lư ng nút en  5. Không ư ng i nào dài hn gp ôi ư ng i nào  cao ca cây - en vi nút ℎ ≤ 2 log ( + 1) 16
  18. ỏ ụ 17
  19. ỏ a  Các thao tác chèn và xóa có th làm thay i tính ch t ca cây  Do chính các thao tác này  i màu các nút  Cu trúc li các kt ni nút  Phép xoay: m bo th t trong ca khóa  Phép th c hi n trong th i gian (1) 18
  20.  Georgy Adelson-Velsky & Evgenil Landis xu t nm 1962  cao 2 cây ca ca mt nút khác nhau nhi u nh t 1  Th i gian (log ) cho các thao tác trong c 2 tr ư ng hp trung bình & xu nh t  Cân bng xây bng phép xoay 19
  21. a  Dng cây TKNP ng u nhiên (slide 13) s ư c cây tư ng i cân bng  Tuy nhiên nu d li u ư c cung cp ln lư t, khóa s không la ch n ng u nhiên  Cây Treap cung cp gi i pháp  Là s kt hp ca cây TKNP và cây th t b ph n (min-heap)  Khóa th a mãn cây TKNP  u tiên th a mãn cây min-heap 20
  22. ằ a  Xem Mc 13.2 tr.312 21