YOMEDIA
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
Chia sẻ: Ba Xoáy
| Ngày:
| Loại File: PDF
| Số trang:0
95
lượt xem
13
download
Download
Vui lòng tải xuống để xem tài liệu đầy đủ
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. Một lợi điểm: Để làm cho danh sách liên kết mà giúp việc cho việc tìm kiếm nhanh chóng hơn.
AMBIENT/
Chủ đề:
Nội dung Text: 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
- 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
n nút gi z.
tr bên ph i ch
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
Hình v minh h a
E
vi c thêm nút P vào
cây nh phân.
A R
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
(Ck-1 + CN-k)
CN = N +
1
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
tr thành ph n t l n th k trong cây, v i hai cây con
nhau
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
Thêm tài liệu vào bộ sưu tập có sẵn:
Báo xấu
LAVA
ERROR:connection to 10.20.1.100:9315 failed (errno=111, msg=Connection refused)
ERROR:connection to 10.20.1.100:9315 failed (errno=111, msg=Connection refused)
Đang xử lý...
Thêm vào BST
Báo xấu
