Phân tích và thiết kế giải thuật: Phân tích độ phức tạp một số giải thuật trên cấu trúc dữ liệu - Chương 3

Chia sẻ: Nguyen Bac A. Châu | Ngày: | Loại File: PDF | Số trang:0

Thêm vào BST

Báo xấu

242
lượt xem 90
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài Giảng điện tử Phân tích và thiết kế giải thuật. Tiến sĩ Dương Tuấn Anh. Chương 3: Phân tích độ phức tạp của một số giải thuật trên cấu trúc dữ liệu. Tìm kiếm tuần tự có thể được thực hiện thông qua việc dùng danh sách liên kết biểu diễn các mẫu tin trong tập tin.

Chủ đề:

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

Lưu

Nội dung Text: Phân tích và thiết kế giải thuật: Phân tích độ phức tạp một số giải thuật trên cấu trúc dữ liệu - Chương 3

Ch ng 3 Phân tích ph c t p m t s gi i thu t trên c u trúc d li u 1
N i dung 1. Tìm ki m tu n t trên danh sách liên k t 2. Cây tìm ki m nh phân 3. Hàng i có u tiên và heapsort 4. K thu t b m 2
1.Tìm ki m tu n t trên danh sách liên k t  Tìm ki m tu n t (sequential search) có th c th c hi n thông qua vi c dùng danh sách liên k t (linked list) bi u di n các m u tin trong t p tin.  M t l i i m: d làm cho danh sách liên k t có th t mà giúp cho vi c tìm ki m nhanh chóng h n. 3
Tìm ki m tu n t trên m t danh sách liên k t có th t . Qui c: z là nút gi trong danh sách liên k t. 3 4 7 21 Z … type link =  node node = record key, info: integer; next: link end; var head, t, z: link; i: integer; 4
Gi i thu t tìm ki m tu n t trên danh sách liên k t procedure initialize; begin new(z); z.next: = z; new(head); head.next:= z end; function listsearch (v: integer; t: link): link; begin z.key: = v; repeat t:= t.next until v < = t.key; if v = t.key then listsearch:= t else listsearch: = z end; 5
Gi i thu t tìm ki m tu n t trên danh sách liên k t (tt.) function listinsert (v: integer; t: link): link; begin z.key: = v; while t.next.key < v do t: = t.next; new(x); x.next: = t.key; t.next: = x; x.key: = v; listinsert: = x; end; Tính ch t: Tìm ki m tu n t trên danh sách liên k t có th t dùng trung bình kho ng N/2 thao tác so sánh cho c s tìm ki m thành công hay không thành. 6
Ch ng minh: V i s tìm ki m thành công, n u gi s r ng m i m u tin trong danh sách liên k t có xác xu t b ng nhau (1/N) c tìm th y, s l n so sánh trung bình s là: (1 + 2+ …+ N)/N = N(N+1)/(2N) = (N+1)/2. V i s tìm ki m không thành công, n u gi s r ng m i m u tin trong danh sách liên k t hay nút k t thúc z có xác xu t b ng nhau (1/(N+1)) c tìm th y v trí sau cùng c a quá trình tìm ki m, s l n so sánh trung bình s là: (1 + 2+ …+ (N+1))/(N+1) = (N+2)(N+1)/(2(N+1)) = (N+2)/2. 7
2.Cây tìm ki m nh phân Trong m t cây tìm ki m nh phân (binary search tree), t t c các m u tin v i khóa nh h n khóa t i nút ang xét thì cây con bên trái c a nút và các m u tin v i khóa l n h n hay b ng khóa t i nút ang xét thì cây con bên ph i c a nút. 10 5 13 2 7 19 8
Kh i t o cây nh phân M t cây r ng c bi u di n b ng cây có con tr bên ph i ch n nút gi z. procedure tree_init; begin new(z); z.1: = z; z.r: = z; new(head); head.key: = 0; head.r: = z; end; 9
Tác v thêm vào Thêm m t nút vào trong cây, ta th c hi n m t s tìm ki m (không thành công) nút y trên cây, r i g n nút y vào v trí ng v i nút gi z t i i m mà quá trình tìm ki m k t thúc. A S E Hình v minh h a vi c thêm nút P vào A R cây nh phân. C H 10
Tác v thêm vào (tt.) procedure tree_insert (v: integer; x: link): link; var p: link; ; begin repeat p: = x; if v < x.key then x: = x.1 else x: = x.r until x = z; new(x); x.key: = v; x.1: = z; x.r: = z; /* create a new node */ if v < p. key then p.1: = x /* p denotes the parent of the new node */ else p.r: = x; tree p.r: = x end 11
In ra cây nh phân procedure treeprint(x: kink) begin if x z then begin treeprint (x.1); printnode (x); treeprint (x.r) end end; Vì m t cây nh phân di n t m t t p tin có th t , vi c in ra các tr khóa trong cây theo m t cách úng n s em l i m t danh sách các khóa có th t . 12
Tác v tìm ki m type link =  node; node = record key, info: integer; l, r: link end; var t, head, z: link; function treesearch (v: integer, x: link): link; /* search the node with the key v in the binary search tree x */ begin while v x. key and x z do begin if v < x.key then x: = x.1 else x: = x.r end; treesearch: = x end; 13
Tính ch t c a s tìm ki m trên cây nh phân Tính ch t: M t tác v thêm vào hay tìm ki m trên m t cây nh phân òi h i ch ng 2lnN so sánh trên m t cây c t o ra t N tr khóa ng u nhiên. Ch ng minh: Chi u dài l i i c a 1 nút: là s c nh c n duy t qua t nút y v nút r +1. i v i m i nút trên cây nh phân, s so sánh c dùng cho m t s tìm ki m nút y thành công chính là chi u dài l i i c a nút y. T ng t t c chi u dài l i i c a m i nút trên cây nh phân c g i là chi u dài l i i c a cây nh phân. 14
Ch ng minh (tt.) Khi chia chi u dài l i i toàn cây v i N, ta s c s so sánh trung bình i v i m t s tìm ki m thành công trên cây. Nh ng n u CN bi u th chi u dài l i i trung bình c a toàn cây, ta có m t h th c truy h i sau ây, v i C1 = 1 N CN = N +  1 (Ck-1 + CN-k) S h ng N là do s ki n nút r óng góp 1 vào chi u dài l i i c a m i nút. S h ng th hai là do s ki n khóa t i nút r có xác xu t b ng nhau tr thành ph n t l n th k trong cây, v i hai cây con l n l t ch a k-1 nút và N-k. 15
Ch ng minh (tt.) k k-1 N-k H th c truy h i này r t gi ng h th c truy h i khi phân tích Quicksort, và nó ã c gi i cùng m t cách a l i cùng m t k t qu . Do ó chi u dài trung bình c a cây N nút là CN 2N lnN. Suy ra chi u dài trung bình c a m t nút trong cây là 2lnN. M t tác v tìm ki m hay thêm vào òi h i trung bình 2lnN so sánh trên m t cây g m N nút. 16
ph c t p trong tr òng h p x u nh t Tính ch t: Trong tr ng h p x u nh t, m t tác v tìm ki m trên cây nh phân g m N khóa có th c n N so sánh. Tr ng h p x u nh t x y ra khi cây nh phân b suy bi n thành m t danh sách liên k t. Tác v xóa Vi c xoá m t nút r t d n u nút y không có nút con hay ch có m t nút con. xóa m t nút có hai con thì khá ph c t p: ta ph i thay th nó v i nút có tr khóa cao nh t k ti p (t c nút t n cùng trái c a cây con bên ph i). 17
E A R C H N M F L Thí d : Tác v H xoá A R C N M P L 18
The following procedure is to delete the node t from the binary tree x. procedure treedelete (t, x: link); var p, c: link; begin repeat /* search for the node t in the tree */ p: = x; if t.key < z. key then x: = x.1 else x: = x.r until x = t; if t.r = z then /* the node t has no right child */ x: = x.1 /* replace the deleted node with the left child of t */ else if t.r.1 = then /* the right chile of t has no left child */ begin x: = x.r; x.1: = t.1 end /* replace the deleted node with its right child */ 19
else begin e: = x.r; while c.1.1 z do c: = x.1; /* find the leftmost node of the right subtree */ x: = c.1; /* x denotes the node that will replace the deleted one */ c.1 = x.r; /* connect c, the parent of x to the right child of x */ x.1: = t.1; x.r: = t.r /* connect x: the children of the deleted node t */ end; if t.key < p.key then p.1: = x /* connect x to the parent of the deleted node */ else p.r: = x; end; 20