1
Ch ng3
Phântích ph c t p m t s
gi ithu ttrên c utrúc d li u
2
N idung
1.Tìm ki m tu n t trên danhs chliên k t
2. Cây tìm ki
mnh phân
3. Hàng
icó u tiên và heapsort
4. K
thu t b m
3
1.Tìmki mtu nt trêndanhs chliênk t
 Tìmki m tu nt sequentialsearch)c th cth c
hi nth ngquavi cd ngdanhs chliênk t(linked
list)bi udi nc cm utin trongt ptin.
 M tl i i m: d làmchodanhs chliênk tcóth t
mà giúpchovi ctìmki mnhanhchóngh n.
4
3 4 7 21
Z
…
Tìmki mtu nt trênm tdanhs chliênk tcó
th
t .
Qui
c:zlànútgi trongdanhsáchliênk t.
type link=↑node
node=record key,info:integer;

listinsert:=x;
end;
Tínhch
t: Tìmki mtu nt trêndanhsáchliênk tcó
th
t dùngtrungbìnhkho ngN/2 thaotácsosánhchoc
s tìmki mthànhcônghay khôngthành.
7
Ch ngminh:
V is tìmki mthànhc ng, n ugi s r ngm im utin
trongdanhs
chliênk tcóxácxu t b ngnhau(1/N)
ctìmth y, s l nsosánhtrungbìnhs là:
(1+2+ …+N)/N=N(N+1)/(2N)=(N+1)/2.
V
is tìmki mkhôngthànhcông, n ugi s r ngm im u
tintrongdanhsáchliênk
thaynútk tthúc z có xácxu t
b ngnhau (1/(N+1)) ctìmth y v trí sauc ngc a
quá trìnhtìmki
m, s l nsosánhtrungbìnhs là:
(1+2+ …+(N+1))/(N+1)= (N+2)(N+1)/(2(N+1))= (N+2)/2.
8
2.Câytìmki mnh phân
10
13
7 192
Trongm tcâytìmki mnh phân binarysearchtree),
t
tc cácm utin v ikhóa nh h n khóat inút angxét

H
Hìnhv minhh a
vi
cthêmnútP vào
câynh
phân.
11
T cv thêmvào .)
;
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
12
Inracâynh phân
procedure treeprint(x: kink)
begin
if x<>zthen
begin
treeprint(x↑.1);

khóang unhiên.
Ch
ngminh:
Chi
udàil i ic a út:làs c nhc nduy tqua t nút
yv nútr
iv im inúttrêncâynh phân, s sosánh cd ng
chom
ts tìmki mnút ythànhcôngchínhlàchi udài
l
i ic anút y.
T ngt tc chi udàil i ic am inúttrêncâynh phân
cg ilàchi udàil i ic acâynh phân.
15
Ch ngminh tt.)
Khichiachi udàil i itoàncâyv iN,tas cs sosánh
trungbình
iv im ts tìmki mthànhcôngtrêncây.
Nh
ngn uC
N
bi uth chi udàil i itrungbìnhc atoàn
cây,tacóm
th th ctruyh isau ây, v i C
1
= 1
∑
N
1
(C

N
2N lnN.
Suyrachi
udàitrungbìnhc am tnúttrongcâylà
2lnN.
M ttácv tìmki mhaythêmvào òih itrungbình
2lnNsosánh
trênm tcâyg mN nút.
17
ph ct ptrongtr ngh px unh t
Tínhch t: Trongtr ngh px unh t, m tt cv tìm
ki
mtrêncâynh phâng mNkhóacóth c nNso
sánh
.
Tr
ngh px unh tx yrakhicâynh phânb suybi n
thànhm
tdanhsáchliênk t.
Tácv xóa
Vi cxoá m tnútr td n unút ykhôngcónútconhay ch
có m tnútcon.
xóam tnútcó haiconthì khá ph ct p:taph ithay
th
nó v inútcótr khóacaonh tk ti p cnútt nc ng
trái
c acâycon bênph i).
18
Thí d :T cv
xo

begin x:= x↑.r; x↑.1:= t↑.1 end /*replace thedeleted node
withitsright child */
20
else
begin
e:= x↑.r;
while c↑.1↑.1<>zdo c:= x↑.1;/*find theleftmost node
of therightsubtree*/
x:= c↑.1; /* xdenotesthenodethat willreplace the
deletedone */
c↑.1= x↑.r; /* connectc, the parentof xtotheright
child of x*/
x↑.1:= t↑.1; x↑.r:= t↑.r/*connectx:the childrenof the
deletednode t*/
end;
if t↑.key< p↑.key then p↑.1:= x /*connect xtotheparent
of the deleted node */
else p↑.r:= x;
end;
21
3.Hàng icó utiênvà gi ithu ts p
th
t HEAPSORT
M tc utrúcd li umàh tr ítnh thaitácv :
thêmm tph nt m ivàoc utrúc
óab ph nt l nnh t
cg ilàhàng icó utiên priority-queue).
Hàng
icó utiênkhácv ihàng ithôngth ng
i mkhil yph nt rakh ihàng ithì ó khôngph ilà

2. D ngc utrúcd li u heap.
24
C utrúcd li uheap
C utrúcd li umàcóth h tr chocáctácv làmvi cv i
hàng
ic utiên s ch acácm utintrongm tm ng
saocho:
m
ikh aph il nh nkh a haiv tr kháctrongm ng.
T
ngt m ikh atronghaikh anàyph il nh nhaitr
kh akhácvàc nh th
Th
t nàys d th yh nkhitadi nt m ngnh m tc u
trúccâyv
inh ng ngn im ikhóaxu nghaikhóa
nh
h n.
Cáctr
khóatrongc utrúccâyth a i uki n heap nh sau:
Khóat
im inútc nph il nh n hay b ng) cáckhóa
haicon c anó(n ucó). i unàyhàmý r ngtr khóal n
nh
t nútr .
25
Thí d : Heap d id ngcâynh phân
X
T O
G