intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE
 » 
 » 

Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 7 - Đỗ Bích Diệp

Chia sẻ: Nguyên Phương | Ngày: | Loại File: PDF | Số trang:23

Thêm vào BST
Báo xấu
77
lượt xem 4
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài giảng "Cấu trúc dữ liệu và giải thuật - Chương 7: Tìm kiếm" cung cấp cho sinh viên các kiến thức: Tìm kiếm tuần tự và tìm kiếm nhị phân, tìm kiếm trên cây nhị phân (cây nhị phân tìm kiếm, cây nhị phân tìm kiếm cân bằng (AVL)). Mời các bạn cùng tham khảo nội dung chi tiết.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 7 - Đỗ Bích Diệp

  1. Cấu trúc dữ liệu và giải thuật Chương VII : Tìm kiếm Tìm kiếm – Phần I z Nội dung 1. Tìm kiếm tuần tự và tìm kiếm nhị phân 2. Tìm kiếm trên cây nhị phân 1. Cây nhị phân tìm kiếm 1. Đặc điểm của cây nhị phân tìm kiếm 2. Thao tác bổ sung trên cây nhị phân tìm kiếm 3. Thao tác loại bỏ trên cây nhị phân tìm kiếm 2. Cây nhị phân tìm kiếm cân bằng (AVL) 1. Khôi phục tính cân bằng khi thực hiện bổ sung và loại bỏ Đỗ Bích Diệp - Khoa CNTT-ĐHBK HN 1
  2. Cấu trúc dữ liệu và giải thuật Bài toán Tìm kiếm – Tìm kiếm là thuật toán tìm 1 phần tử có giá trị cho trước trong một tập các phần tử 23 78 45 8 32 56 78? 23 78 45 8 32 56 – Khóa tìm kiếm: Một bộ phận của các phần tử trong tập mà giá trị của nó được sử dụng để so sánh và tìm kiếm Tìm kiếm tuần tự – Tìm kiếm tuần tự z Các phần tử trong tập đầu vào không được sắp xếp theo khóa tìm kiếm z Mô tả – Duyệt dãy (danh sách, hàng đợi , v…v ) chứa các phần tử trong tập – So sánh với khóa cần tìm tới khi tìm thấy khóa hoặc duyệt qua hết mảng mà chưa tìm thấy – Trả lại chỉ số phần tử trong dãy (nếu thấy) Đỗ Bích Diệp - Khoa CNTT-ĐHBK HN 2
  3. Cấu trúc dữ liệu và giải thuật Tìm kiếm tuần tự Function SEQUENTIAL(A, n, key) ≠ {tìm phần tử có khóa key trong mảng A gồm n phần tử. Kết quả trả ra: -1 nếu không tìm thấy phần tử có khóa key, chỉ số của phần tử nếu tìm thấy} 1. i:= 1; 2. while (i n) then return -1 { không thấy}; 4. else return i{tìm thấy tại vị trí i} Tìm kiếm tuần tự – Độ phức tạp : z Trường hợp tốt nhất: O(1) z Trường hợp tồi nhất: O(n) z Trường hợp trung bình : O(n) Đỗ Bích Diệp - Khoa CNTT-ĐHBK HN 3
  4. Cấu trúc dữ liệu và giải thuật Tìm kiếm nhị phân z Tìm kiếm nhị phân – Sử dụng cho việc tìm kiếm trên mảng đã được sắp xếp – Mô tả z Chọn phần tử “ở giữa” dãy – A[k] để thực hiện so sánh với giá trị cần tìm z Nếu key = A[k] thì tìm thấy , kết thúc z Nếu key < A[k] thì tìm trên nửa đầu của mảng đã cho z Nếu key > A[k] thì tìm trên nửa sau của mảng đã cho Tìm kiếm nhị phân Function BINARY-SEARCH(A,l, r, key) 1. If (l> r) return -1; 2. m = (l+r) /2 ; 3. If (A[m] = key ) return m ; 4. Else if (A[m] > key) return BINARY-SEARCH(A, l, m-1, key); 5. Else return BINARY-SEARCH(A, m+1, r, key); Đỗ Bích Diệp - Khoa CNTT-ĐHBK HN 4
  5. Cấu trúc dữ liệu và giải thuật Tìm kiếm nhị phân Function BINARY-SEARCH(A,n,key) 1. l:=1 ; r := n ; { l, r lần lượt là biến chỉ số sử dụng để ghi nhận chỉ số của phần tử đầu và phần tử cuối của mảng mà chúng ta đang tìm kiếm trên đó} 2. while l A[m] then l:= m+1 else return m; end; 3. { Không tìm thấy } return -1; Cây nhị phân tìm kiếm Binary Search Tree (BST) z Cây tìm kiếm nhị phân ứng với 1 dãy gồm n khóa a1, a2, …, an là một cây nhị phân thỏa mãn tính chất sau – Mọi giá trị thuộc cây con trái của một nút đều nhỏ hơn giá trị tại nút đó – Mọi giá trị thuộc cây con phải của một nút đều lớn hơn giá trị tại nút đó – Mỗi cây con của một nút cũng đều là cây nhị phân tìm kiếm z Với một tập khóa có thể xác định được nhiều cây nhị phân tìm kiếm Đỗ Bích Diệp - Khoa CNTT-ĐHBK HN 5
  6. Cấu trúc dữ liệu và giải thuật Cây nhị phân tìm kiếm 33 64 29 64 30 70 19 30 40 70 80 23 33 65 23 65 80 19 29 40 Cây nhị phân tìm kiếm – Các thao tác trên cây nhị phân tìm kiếm z Duyệt cây nhị phân tìm kiếm z Tìm kiếm nút có giá trị x z Thêm một nút mới có giá trị x z Xóa một nút có giá trị x Đỗ Bích Diệp - Khoa CNTT-ĐHBK HN 6
  7. Cấu trúc dữ liệu và giải thuật Tìm kiếm trên cây nhị phân tìm kiếm – Cách thực hiện z Nếu cây rỗng: không tìm thấy z Nếu cây không rỗng: – So sánh giá trị cần tìm kiếm với các giá trị khóa tìm kiếm ở nút gốc z Nếu = Æ Tìm thấy < 6 z Nếu < Æ Đi xuống tìm 2 9 kiếm trong cây con trái > z Nếu > Æ Đi xuống tìm 1 4 = 8 kiếm trong cây con phải Tìm kiếm trên cây nhị phân tìm kiếm z Giải thuật đệ qui Algorithm BST-Recursive(T, key) {T là con trỏ trỏ tới gốc của cây; key là giá trị cần tìm, trả ra con trỏ trỏ tới nút chứa giá trị cần tìm } 1. If ( T = NULL) then return NULL; 2. If ( key < INFO(T) ) return BST-Recursive(LPTR(T), key); 3. Else if (key > INFO(T)) return BST-Recursive(RPTR(T), key); 4. Else return T; Đỗ Bích Diệp - Khoa CNTT-ĐHBK HN 7
  8. Cấu trúc dữ liệu và giải thuật Tìm kiếm trên cây nhị phân tìm kiếm Giải thuật không đệ qui Algorithm BST(T, key) 1. q= T ; {Khởi tạo biến con trỏ để duyệt cây} 2. while q < > NULL do begin if (INFO(q) = key then return q; else begin if (INFO(q) < key) then q = RPTR(q); else q = LPTR(q); end. end. 3. Return NULL; Bổ sung trên cây nhị phân tìm kiếm – Cách thực hiện thêm một nút có giá trị x vào cây nhị phân tìm kiếm z Tìm nút có giá trị x z Nếu tìm thấy, không cần thêm z Nếu không tìm thấy – Giả sử gọi w là nút lá mà ta chạm đến trong quá trình tìm kiếm – Tạo một nút mới có giá trị x và biến nút này thành nút con của w (con trái hay con phải phụ thuộc vào việc so sánh x với giá trị lưu trong w) Đỗ Bích Diệp - Khoa CNTT-ĐHBK HN 8
  9. Cấu trúc dữ liệu và giải thuật Bổ sung trên cây nhị phân tìm kiếm Bổ sung nút có giá trị 5 < 6 6 2 9 2 9 > w 1 4 8 1 4 8 5 Bổ sung trên cây nhị phân tìm kiếm Algorithm Insert_BST_Recursive(T, x) {Tìm hoặc bổ sung nút có giá trị x trên cây nhị phân tìm kiếm. Trả ra cây sau khi bổ sung hoặc trả ra nút có chứa x } 1. If (T = null) then 1. Call New (p) ; {Xin bộ nhớ cho nút mới} 2. INFO(p) := x; LPTR(p): = RPTR(p) := NULL; 3. T = p ; 2. If ( key < INFO(T) ) then 1. LPRT(T) := Insert_BST(LPTR(T), x) ; 3. Else if ( key > INFO(T) ) then begin 1. RPTR(T) := Insert_BST(RPTR(T), x) ; 4. return T; Đỗ Bích Diệp - Khoa CNTT-ĐHBK HN 9
  10. Cấu trúc dữ liệu và giải thuật Bổ sung trên cây nhị phân tìm kiếm Algorithm Insert_BST(T, x) {Bổ sung nút mới có giá trị x vào cây, trả ra con trỏ trỏ tới nút mới, hoặc trả ra con trỏ trỏ tới một nút trong cây nếu trong cây đã có nút chứa khóa x } 1. q= T ; {Khởi tạo biến con trỏ để duyệt cây} 2. while q < > NULL do begin if (INFO(q) = key) then return q; // Tìm thấy, kết thúc giải thuật else begin if (INFO(q) < key) then begin p= q; q = RPTR(q); end; else begin p=q; q = LPTR(q);end; end. end. 3. Call New(q); INFO(q) = x; LPTR(q) = RPTR(q) = NULL; if (T= null ) then T = q; else if x < INFO(p) then LPTR(p) = q; else RPTR(p) = q; Dựng cây nhị phân tìm kiếm – Ví dụ: Dựng cây nhị phân tìm kiếm sử dụng phép bổ sung cho ở trên với dãy số {8,3,14,6, 12, 28, 10,21,5} T 8 3 14 6 12 28 5 10 21 Đỗ Bích Diệp - Khoa CNTT-ĐHBK HN 10
  11. Cấu trúc dữ liệu và giải thuật Xóa nút trên cây nhị phân tìm kiếm z Các trường hợp : – Nút loại bỏ là nút lá: Xóa ngay lập tức – Nút loại bỏ là nút nhánh và chỉ có một cây con (trái hoặc phải) : Thay nút cần xóa bằng nút con – Nút loại bỏ là nút nhánh và có 2 cây con: Thay nút cần xóa bằng nút cực phải của cây con trái hoặc nút cực trái của cây con phải Xóa một nút lá trên cây – Trường hợp nút cần xóa là nút lá z Xóa nút này z Gán liên kết từ cha của nó trở thành NULL NULL T2 T3 T4 T3 T2 T4 T1 T1 Nút cần xóa Đỗ Bích Diệp - Khoa CNTT-ĐHBK HN 11
  12. Cấu trúc dữ liệu và giải thuật Xóa nút nhánh có 1 con – Trường hợp nút cần xóa là nút nhánh có 1 con z Gắn cây con của nút cần xóa vào cha Nút cần xóa T2 T3 T4 T3 T1 T2 T4 T1 Xóa nút nhánh có đầy đủ 2 con – Trường hợp nút cần xóa là nút có 2 con z Bước 1: Xác định nút thay thế z Nút thay thế là nút cực phải của cây con trái hoặc nút cực trái của cây con phải Nút cần xóa T3 T4 T5 T1 Nút thay thế T2 Đỗ Bích Diệp - Khoa CNTT-ĐHBK HN 12
  13. Cấu trúc dữ liệu và giải thuật Xóa nút nhánh có đầy đủ 2 con – Trường hợp nút cần xóa là nút có 2 con z Bước 2: Có nút thay thế là y – Gỡ y ra khỏi cây – Gắn con trái của y vào cha của y Nút cần xóa T3 T4 T5 T1 T2 y Xóa nút nhánh có đầy đủ 2 con – Trường hợp nút cần xóa là nút có 2 con z Bước 3: Có nút thay thế là y – Gắn y vào vị trí của nút cần xóa T3 T4 T5 T1 T2 Đỗ Bích Diệp - Khoa CNTT-ĐHBK HN 13
  14. Cấu trúc dữ liệu và giải thuật Xóa nút trên cây nhị phân tìm kiếm Algorithm BSTDEL(key, nut_xoa, nut_cha) {Thực hiện việc xóa nút trỏ bởi con trỏ nut_xoa , biết con trỏ nut_cha trỏ tới nút cha của nút xóa, biết giá trị key của nút cần xóa} 1. If (LPTR(nut_xoa) = null && RPTR(nut_xoa) = null) then begin if ( key < INFO(nut_cha)) then LPTR(nut_cha): = null; else RPTR(nut_cha) := null; call dispose(nut_xoa) ; end; 2. If (LPTR(nut_xoa) = null || RPTR(nut_xoa) = null) then begin if LPTR(nut_xoa) = NULL then nut_thay := RPTR(P); else if RPTR(nut_xoa) = NULL then nut_thay := LPTR(P); if (key < INFO(nut_cha)) then LPTR(nut_cha) := nut_thay; else RPTR(nut_cha) := nut_thay; call dispose(nut_xoa); end; Xóa nút trên cây nhị phân tìm kiếm 3. If (LPTR(nut_xoa) != null && RPTR(nut_xoa) != null) then begin nut_thay := LPTR(nut_xoa); {sang cây con trái} while RPTR(nut_thay) null do begin T := nut_thay; nut_thay := RPTR(nut_thay); end;{Kết thúc vòng lặp nut_thay trỏ đến nút cực phải của cây con trái, T:nút cha của nút thay} RPTR(nut_thay) := RPTR(nut_xoa); RPTR(T) := LPTR(nut_thay); LPTR(nut_thay) := LPTR(nut_xoa); if (key < INFO(nut_cha)) then LPTR(nut_cha) := nut_thay; else RPTR(nut_cha) := nut_thay; call dispose(nut_xoa); End. Đỗ Bích Diệp - Khoa CNTT-ĐHBK HN 14
  15. Cấu trúc dữ liệu và giải thuật Cây nhị phân tìm kiếm z Đánh giá giải thuật : tìm kiếm và loại bỏ – Thời gian thực hiện trung bình Ttb(n) = O(log2n) z Nhược điểm của cây tìm kiếm nhị phân: – Cây suy biến có thể được hình thành trong quá trình bổ sung, ảnh hưởng đến hiệu năng của việc sử dụng cây nhị phân trong tìm kiếm Cây nhị phân cân đối AVL z Cây nhị phân cân đối AVL (AVL balanced binary search tree) – Một cây nhị phân tìm kiếm được gọi là cây cân đối AVL nếu với mọi nút trên cây, chiều cao của 2 cây con tương ứng chỉ chênh nhau nhiều nhất là 1 đơn vị 33 33 29 64 29 64 70 19 30 70 19 30 40 23 65 80 23 65 80 Cây nhị phân tìm kiếm cân đối AVL Cây nhị phân tìm kiếm không cân đối Đỗ Bích Diệp - Khoa CNTT-ĐHBK HN 15
  16. Cấu trúc dữ liệu và giải thuật Cây nhị phân cân đối AVL z Bổ sung trên cây AVL – Bổ sung theo nguyên tắc giống với cây nhị phân tìm kiếm – Việc bổ sung có thể làm vi phạm tính cân bằng của cây 27 27 27 Bổ sung 25 Khôi phục cân bằng 18 44 18 44 20 44 12 20 35 52 12 20 35 52 18 22 35 52 19 22 19 22 12 19 25 25 Cây nhị phân cân đối AVL – Khôi phục tính cân bằng của cây z Kiểm tra tính cân bằng của các nút nằm trên đường đi từ nút gốc đến nút mới được bổ sung z Xác định nút vi phạm gần nhất với nút mới z Thực hiện các phép quay với nút vi phạm mà không cần thực hiện phép quay nào khác tại tổ tiên của nút đó – Tùy vào vị trí nút mới so với nút vi phạm có 4 loại phép quay khác nhau Đỗ Bích Diệp - Khoa CNTT-ĐHBK HN 16
  17. Cấu trúc dữ liệu và giải thuật Cây nhị phân cân đối AVL z Xác định các phép quay cần sử dụng – Bước 1: Xác định nút vi phạm gần nhất – Bước 2: Quan sát vị trí của nút con và nút cháu của nút vi phạm trên đường đi xác định vị trí bổ sung z Trường hợp 1: Quay đơn phải Nút vi phạm (nút bất thường) Nút con Nút cháu Cây nhị phân cân đối AVL z Trường hợp 2: Quay đơn trái (single left rotation) z Trường hợp 3: Quay kép phải (double right rotation) : quay trái với cây con trái rồi quay phải với cây có nút vi phạm và con trái của nó Đỗ Bích Diệp - Khoa CNTT-ĐHBK HN 17
  18. Cấu trúc dữ liệu và giải thuật Cây nhị phân cân đối AVL z Trường hợp 4: Quay kép trái (double left rotation) : quay phải với cây con phải, rồi quay trái với cây có nút vi phạm và con phải của nó Cây nhị phân cân đối AVL – Trường hợp 1: Phép quay đơn phải Sau khi quay đơn phải Nút vi B phạm Trước khi quay A A B C h+1 C T1 h T2 h-1 h-1 or h-2 h-1 h-1 or h-2 h h+1 T3 T4 T3 T4 T1 T2 AVL trở lại trạng thái cân bằng Đỗ Bích Diệp - Khoa CNTT-ĐHBK HN 18
  19. Cấu trúc dữ liệu và giải thuật Cây nhị phân cân đối AVL – Trường hợp 3: Phép quay kép phải Trước khi quay Nút vi Sau khi quay kép phạm phải D A B C B A D C h h-1 h-1 or h-2 T1 T3 T4 h T1 T′2 h T"2 T′2 h T"2 h-1 or h-2 h-1 T3 T4 AVL trở lại trạng thái cân bằng Cây nhị phân cân đối AVL – Bổ sung trên cây AVL – Ví dụ: Bổ sung 30 vào cây s 8 Nút vi phạm 3 14 Không vi 1 6 10 19 phạm Không vi 4 17 24 phạm 30 Không vi phạm Đỗ Bích Diệp - Khoa CNTT-ĐHBK HN 19
  20. Cấu trúc dữ liệu và giải thuật Cây nhị phân cân đối AVL – Để sửa đổi lại cây, quay cây có gốc tại 14: Quay từ phải sang trái với cây con phải (nút 14 và 19) – Phép quay này gọi là phép quay đơn trái 8 3 19 1 6 14 24 4 10 17 30 Cây nhị phân cân đối AVL – Bổ sung trên cây AVL – Ví dụ 8 Nút vi 3 14 phạm 1 6 10 19 Không vi phạm 4 17 24 18 Bổ sung 18 vào cây Không vi Không vi phạm phạm Đỗ Bích Diệp - Khoa CNTT-ĐHBK HN 20
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN
TRỢ GIÚP
HỖ TRỢ KHÁCH HÀNG
Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.

 

Đồng bộ tài khoản
3=>0