Giáo trình Cấu trúc dữ liệu và giải thuật Phần 2 | Đại học Kỹ thuật - Công nghệ Cần Thơ

Giáo trình Cấu trúc dữ liệu và giải thuật Phần 2 | Đại học Kỹ thuật - Công nghệ Cần Thơ. Tài liệu được biên soạn dưới dạng file PDF gồm 29 trang, giúp bạn tham khảo, ôn tập và đạt kết quả cao trong kì thi sắp tới. Mời bạn đọc đón xem!

45 23 lượt tải Tải xuống
Chia sẻ Báo cáo tài liệu

Môn: Cấu trúc dữ liệu và giải thuật (CT)

Trường: Đại học Kỹ thuật - Công nghệ Cần Thơ

Thông tin:

20 trang 5 tháng trước

Tác giả:

Profile 48 Nguyễn Thị Anh Thơ
Chuong 4
CAY
Trong chuang nay chiing ta se nghien curu mo hinh du lieu cay (tree). Cay la
mot cau true phan cap tren mot tap hop nao do cac doi tugng. Mot vi du
quen thupc ve cay, do la cay thu muc hoac muc luc cua cuon sach cung la
mot cay. Cay dugc sir dung rong rai trong rat nhieu van de khac nhau.
Chang han no dugc ap dung de to chuc thong tin trong cac he co so du lieu,
de mo ta cau true cii phap ciia cac chuong trinh nguon khi xay dung cac
chuong trinh djeh. Rat nhieu bai toan ma ta gap trong cac Imh vuc khac
nhau dugc quy ve vice thuc hien cac phep toan tren cay. Trong chuong nay
chiing ta se trinh bay djnh nghTa, cac khai niem co ban ve cay. Chung ta
cung se xet cac phuong phap cai dat cay va thuc hien cac phep toan co ban
tren cay. Sau do ta nghien emr ky mot so dang cay dac biet do la cay nhj
phan tim kiem va cay can bang.
4.1. CAY VA CAC KHAI NIEM
C O
BAN
4.1.1. Djnh nghTa
D jn h nghTa I: Mot cay la tap hgp huu h ^ cac nut trong do co mgt niit dac
biet ggi la goc (root). Giua cac nut co moi quan hp phan cap ggi la quan he
cha-con.
D jn h nghTa 2: Cay dugc djnh nghTa de quy nhu sau:
- Mgt nut la mgt cay va nut nay cung la goc ciia cay.
- Gia sir T|, T2 , .... T„ (n > 1) la cac cay co goc tuong img ri, r2,..., r„. Khi
do cay T voi goc r dugc hinh thanh bang each cho r tro thanh nut cha cua
cac niit ri, r2,..., rn.
131
4.1.2. Mot so khai niem
cd
ban
- Ba c c m m p t nuf. la so con cua nut do.
- B g c cua m o t cay: la bac cua mit c6 bac Ion nhat tren cay do (so cay ccot
toi da cua mot nut thupc cay). Cay c6 bac n thi goi la cay n - phan.
- N u t gdc: la nut khong c6 nut cha.
- N iit Id: la nut c6 bac bang 0.
- N iit nhdnh: la nut c6 bac khac 0 va khong phai la niit goc.
- Mice cua m g t nut:
Muc (g6c (To)) =1
Goi T|. Ti
....
T„ la cac cay con cua To.
Khi do Muc ( T ,) = Muc (T2) = ... = Muc (T„) = Muc (To) +1
- C h ieu ca o cua cay: la muc ciia nut c6 muc Ion nhat c6 tren cay do.
- D u o n g di: Day cac nut ni, n2, ..., nk dupe goi la dubmg di neu ni la ( cl
cua ni+i (1 < i < k-1).
- D g d d i c u a duem g di: la so nut tren duong di trir 1.
- C a y d u g c s a p th u tu: Trong mpt cay, nSu cac cay con cua moi mit dduc
sip theo mpt thu tp nhat dinh, thi cay dupe gpi la cay dupe sap (cayy (
thu tu). Ching han, hinh minh hoa hai cay dupe sip khac nhau.
132
Hinh 4.2. Hai cay duffc s3p khae nhau
- Rung-, la tap hop him han cac cay phan biet.
H'mh 4.3. Ru ng gom ba cay
Sau day ta se tim hieu mot loai cay dac biet dugc gpi la cay nhi phan.
4.2. CAY NHI PHAN
4.2.1. Djnh nghia
Cay nhi phan la cay ma moi nut c6 toi da hai cay con. Doi voi cay con cua
mot nut ngudi ta cung phan biet cay con trai va cay con phai.
Nhu vay cay nhi phan la cay c6 thu tur.
4.2.2. Tinh chat
Doi voi cay nhi phan can chu y tai mot so tinh ch4t sau;
1. So lugng toi da cac nut c6 6 muc i tren cay nhj phan la 2 ' (i ^ 1).
2. So lugng niit t6i da tren mot cay nhi phan c6 chigu cao h la 2''-l(h > 1 ).
133
C h u n g m in h
- Ti'nh chat 1 sg dupe chirng minh bang quy nap.
B u o c c a s a : voi i = 1, cay nhi phan c6 1 = 2^* nut. Vay menh de dung voi i = 1.
B u a c qu y nap: Gia su ket qua dung vai muc i, nghia la a muc nay cay nhi
phan CO toi da 2''' nut, ta chung minh menh de dung voi muc i + 1.
Theo djnh nghia cay nhj phan thi tai moi nut c6 toi da hai cay con nen moi
nut a miic i c6 toi da hai con. Do do theo gia thiet quy nap ta suy ra tai muc
i + 1 ta CO 2'“'x2=2'mit.
- Tinh chat 2 dugre chung minh nhu sau;
Ta da biet rSng chieu cao ciia cay la so miic Ion nhat c6 tren cay do. Ta c6
so nut toi da c6 tren cay nhj phan voi chieu cao h la:
2®+2' + ... + 2''‘ ' = 2''-l.
Tir ket qua nay c6 the suy ra:
Neu cay nhi phan c6 n nut thi chieu cao ciia no la h = f log2(n + 1 )1
(Ta quy uoc : fx1 la so nguyen nho nhat > x
LxJ la so nguyen Ion nhat < x )
4.2.3. Bieu dien cay nhj phan
4 .2 .3 .1. L ir u t r i r k e t ie p
Phuong phap t\r nhien nhat de bieu dien cay nhj phan la chi ra niit con trai
va nut con phai ciia moi mit.
De thvrc hign vige nay ta c6 the su dqng mgt mteg de luu trii cac nut cua cay
nhi phan. Moi nut cua cay dugre bieu dien boi b ^ ghi gom ba th^h phan:
infor: mo ta thong tin gin voi moi niit.
Left: chi mit con trai.
Right: chi mit con phai.
Gia su cac nut cua cay dugre danh s6 tir 0 dgn m a x-1, du ligu cua cac mit
tren cay c6 kieu la Ite m . Khi do cau true du ligu bieu dien cay nhi phan
dugre khai bao nhu sau:
#define max N //so thii tg Ion nhat cua nut tren cay
134
//Khai bao kieu du li?u Item (neu can)
struct Node
{
Item infer;
int Letf;
int Right;
};
Node Tree[max];
Bang 4.1 minh hoa cau true du lieu bieu dien cay nhi phan trong hinh 4.5
Bang 4.L Cau true dir li|u bieu diln cay
infor Left Right
1
A 2 3
2
B
4
5
3
C 6 7
4
D 0
8
5
E 9
10
6
F
0
0
7
G 11
9
8
H
0
0
9
1
0
0
10
J
0
0
11
K
0
0
135
Neu CO mot cay nhi phan hoan chinh day dii, ta c6 the de dang danh so cho
cac nut tren cay do theo thu tir Ian lugt tir muc 0, 1, 2,... het muc nay den
muc khac va tu trai qua phai d6i vai cac nut a moi muc. Vi du voi hinh 4.6
CO the danh so nhu sau:
Hinli 4.6. Cay nhj phan dirp’c danh so
Ta c6 nhan xet sau: con cua nut i la cac nut 2i+l va 2i + 2 hoac cha cua nut j
laLj/2-lJ.
Nhu vay, ta c6 the luu tru cay nay bang mot mang T, theo nguyen tac: nut
thu i cua cay duqc luu tm a T[i]. Do chinh la each luu tru ke tiep doi vai
cay nhi phan. Vai each luu tru nay neu biet dugc dia chi ciia mit con se tinh
dugc dia chi nut cha va ngugc lai.
Vai cay day du neu tren thi hinh anh luu tru se nhu sau:
A B
C D
E F G
T[0] T[l]
T[2]
T[3]
T[4]
T[5]
T[6]
Nhdn xel:
Neu cay nhj phan khong d4y du thi each luu tru nay khong thich hop vi se
gay ra lang phi bo nha do c6 nhieu phan tir bo trong (ung vai cay con rong).
Ta hSy xet cay nhu hinh 4.7. De luu tru cay nay ta phai diing mang gom 15
phan tu ma chi c6 5 phan tir khac rong, hinh anh luu tru mi^n nha cua cay
nay nhu sau:
36
H'mh 4.7. Cay nhj phan dSc bift
B
0
C
0
0
0
D
0
0 0 0 0 0 0
E
0
( 0 : chi cho trong)
Neu cay nhj phan luon bien dong nghTa la c6 phep bo sung, loai bo cac nut
thircmg xuyen tac dong thi each luu tru nay gap phai nipt so nhuoc diem nhu
phai dich chuyen cac phan tu trong mang dan den ton thai gian khi phai
thirc hien cac thao tac nay, dp cao ciia cay phu thupc vao kich thuac cua
m ang,...
4.2.3.Z. Luu tru-moc noi
Cach lull tru nay khac phuc dupe nhung nhupc diem cua each luu tru ke
tiep dong thai phan anh dupe dang tu nhien cua cay.
I'rong each liru tru moc noi, moi nut tuang ung voi mot phan tu nho c6 quy
each nhu sau:
Letf
infer Right
- infer ung vai thong tin (du lieu) cua niit.
— T.pf t I'rng vai con trb. trb tai cay con trai ciia niit do.
- Right irng voi con tro, tro tai cay con phai cua nut do.
Ta CO the khai bao cau trite du lieu nhu sau:
struct Node
Item infor;
Node *Left, *Right;
};
typydef Node *TRO;
TRO Root; // Con tro Root tro vao nut goc cay
137
Vi du: Cay nhj phan hinh 4.6 c6 dang liru tru moc noi nhu a hinh 4.8
root
Hhili 4.8. Cay nhj phan liru trO' m6c noi
De liru tru va thao tac vai cay, can mot con tro r o o t , tro tai nut goc ciia
cay.
4.2.4. Phep duyet cay nhj phan
Vice truy xuat vao cac mit mot each c6 he thong, sao cho moi niit duoc truy
xuat dung mpt Ian theo mot thii tp xdc dinh, gpi la phep duypt cay. Co the
duyet cay nhj phan theo mpt trong ba thu tir: duyet truoc, duyet giua va
duypt sau, cac phep duypt nay dupe djnh nghTa de quy nhu sau;
4.2.4.1. Day f t theo thir t{r trir&c (Node-Left-Right, Node-Right-Left)
Neu cay khac rong
- Tham goc (truy xuat nut goc).
- Duyet cay con trai theo thu tu truoc.
- Duyet cay con phai theo thu tu truoc.
4.2.4.2. Day f t theo thirtugiita (Left-Node-Right, Right-Node-Left)
Neu cay khac rong
- Duyet cay con trai theo thu tu giua.
- ThSm goc.
- Duyet cay con phai theo thu tu giua.
138
4.2.4.3. Duyft theo th& tu sau (Left-Right-Node, Right-Left-Node)
Neu cay khac rong
- Duyet cay con trai theo thu tir sau.
- Duyet cay con phai theo thu tir sau.
- Thant goc.
Tuomg ling vai ba phep duyet ta c6 ba ham duyet cay nhj phan. Sau day la
ham de quy duyet cay theo thu tu trudc:
void NLR (TRO root)
{
if (root != NOLL)
{
visit(root);
NLR(root->Left);
NLR(root->Right);
}
}
Mot each tuomg tu, ta c6 the viet dugc cac ham de quy di qua cay theo thu
Vai cay nhi phan hinh 4.9, day cac niit dugc tham trong cac phep duyet la:
- Duyet theo thu tu truac: ABDGHECFIG
- Duyet theo thu giua: GDHBEAFICG
- Duyet theo thii tu sau: GFIDEBIFGCA
139
Cay bieu thuc la cay nhj phan ma nut goc va cac niit nhanh chira cac toan tir
(phep loan) con cac nut la thi chua cac toan h ^ g .
4.2.5. Cay nhj phan bieu dien bieu thu'c
4.2.5.1. Cach dung cay bieu thirc
Doi vai phep toan hai ngoi (chang han +, *, /) dugc bieu dien bai cay nhi
phan ma goc cua no chua toan tir (TT), cay con trai bieu dien toan hang
(TH) ben trai, con cay con ben phai bieu dien toan hang ben phai.
Doi vai phep toan mot ngoi nhu "phii dinh" hoac "phep toan doi dau", hoac
cac ham chuan nhu exp() hoac cos()... thi cay con ben trai rong. Con voi cac
phep toan mot toan hang nhu phep "lay dao ham" ()' hoac ham "giai thira"
()! thi cay con ben phai rong.
HUth 4.1 L Mpt so cay bieu thiic
140
Nhdn xet :
Neu ta duyet cay bieu thirc theo thir tir trudc thi ta dirge bieu thirc Ba Lan
dang tien to (pre-fix). Neu duyet cay nhi phan theo thu tu sau thi ta c6 bieu
thirc Ba Lan dang hau to (post-fix); con theo thir giira thi ta nhan dugc each
viet thong thuong ciia bieu thuc dang trung to.
4.2.5.2. Vi du ting dung
De minh hga cho nhan xet nay ta lay vf du sau;
Cho bieu thirc P = a*(b - c) + d/e
1. Hay dung cay bieu thuc bieu dien bieu thiic tren
2. Dua ra bieu thuc 6 dang tien to va hau to
Gicii:
1. Ta CO THI = a*(b - c ) ! suy ra cay bieu thuc c6
TH2 = d/e J
Xet THI = a*(b - c), toan hang chua a dang co ban
ta phai phan tich de dugc nhu a (1)
TH3 = a T cay bieu thirc ciia toan hang nay la
TH4 = b - c J
Toan hang TH4 da 6 dang co ban
nen ta co ngay cay bieu thuc
Cung tuoTig tu nhu vay doi voi
toan hang TH2, cay bieu thuc
tuomg ung veri toan hang nay la
H'mh 4.12. Xay dung cay bieu dien bieu thiic
141
l ong hop cay bieu thirc cua cac loan hang ta dirac cay bieu thuc sau:
///;;/; 4.13. Cay bieu thiic
B a y g id ta d u y e t c a y b ieu th iic d h in h 4 .1 3
- Duyet theo thi'c tu Iruac: +*a -b c/d e (b i e u thirc titn to)
- Duyet theo thu sau: abc-* d e/+ ( b ie u thurc h(u to)
4.3. CAY NHI PHAN TIM KIEM
C a y n h i p h a n d irge s ii d u n g v a o n h ie u m u c d ic h k h a c n h a u T u y n h i e n vie i
sir d u n g c a y nh i p han d e liru g iir v a tim k ie m t h o n g tin 'a n la m o t tron]
n h u n g lin g d u n g q u an trgn g n h at c iia c a y nhj ph a n . T r o n g p ia n n ay c h iin g t
se n g h ien c u u m o t Id p c a y nhj p h a n d ac b iet p h u c v u c b v ic e tim kiSn
th o n g tin , d o la c a y n h | p h a n tim k ie m .
T r o n g th u c te , m o t Idp d o i t u g n g n ao d o c 6 th e d u g c m o ta >di m p t k ie u ba
g h i, c a c t r u d n g c u a b a n g h i b ie u d ie n c a c th u g c tinh c u a i6i t u g n g . T ron
bai to a n tim k ie m th o n g tin , ta th u d n g q u a n tarn d e n m g tn h o m c a c th u g
tin h n ao d o c iia d o i t u g n g m a th u o c tin h n ay h o a n toa n x .c d in h d u g c d t
tu g n g . C h u n g ta g g i ca c th u g c tin h n a y la k h oa. N h u v a y , k ioa la m o t n hdr
c a c th u g c t in h c u a m o t la p d o i t u g n g sa o c h o h ai d o i tu g n ; kh a c n h au ph;
c 6 g ia tn k h a c nh a u tren n h o m th u g c tinh d o .
4.3.1. Djnh nghTa
C a y nh j p h a n tim k ie m ( C N P T K ) la c a y n hi p h an h o a c o n g h o a c k h on
ron g th i phai t h o a m a n d o n g thd i c a c d ie u k ie n sau:
142
- K h o a c iia c a c n iit th u o c c a y c o n trai n h o h o n k h o a nu t g o c .
- K h oa ciia n u t g o c n h o h o n k h o a c u a c a c n ut thu o c ca y c o n p h a i c u a nut g o c .
- C a y c o n trai v a c a y c o n p h a i c u a g o c c u n g la c a y n h i p h a n tim k ie m .
H in h 4 . 1 4 b i e u d ie n m o t c a y n h i p h an tim k ie m , tro n g d o k h o a c iia c a c d in h
la cac s o n g u y e n .
Hlnh 4. 14. C a y nhj phan tim kiem
4.3.2. Cai dat cay nhj phan tim kiem
M o i nu t tre n c a y nhj p h a n tim k ie m c 6 d an g;
Left infor
Right
T ro n g do : L ef t la c o n tro tro to i c a y c o n trai, R ig h t la c o n tro tro t o i c a y c o n
p h a i, c o n i n f o r c h u a th o n g tin c iia nu t.
G ia sir dir lie u tr en m o i n u t c iia e a y c 6 k ie u d u lie u la Item, k h i d o c a u true
d f i li? u c u a c a y tim k i e m n hj p h an d u g c d in h n g h ia n h u sau:
struct Node
Item infor;
Node *Left, *Right;
};
typedef Node *TRO;
TRO root;
T i e p t h e o ta n g h i e n ciru c a c p h e p to a n tr en c a y n h i p h a n tim k ie m .
143
4.3.3. Cac thao tac cd ban tren cay nhj phan tim kiem
4.3.3.1. Tim kiem
T im k ie m tren c a y l a m p t t r o n g c a c p h ep to a n q u an trp n g n h a t d o i v o i i c
n h i p h a n t im k ie m . T a x e t b a i to a n sa u:
B a i lo an: G ia sir m o i nut tre n c a y nh i p h an tim k i e m la m o t b a n g h i, Ibi
c o n tro r o o t c h i t a l g o c cu a c a y v a X la k h o a c h o tr u o c . V a n d e d at rra
tim x e m tre n c a y c 6 c h u a n u t v o i k h o a X h a y k h o n g .
• Giai thuat de quy
n a y tra v e c o n tro tro to i nut c 6 k h o a b S n g x , n g u p c lai tr a v e N U L IL
TRO Search(TRO root. Item x)
{
if (root == NULL)
return NULL;
else if (x < root->infor)
return Search(root->Left, x) ;
else if (x > root->infor)
return Search(root->Right, x) ;
else return root;
}
• Ciai thuat lap
H am n ay tra v e n u t c 6 k h o a b a n g x , n g u p c la i tr a v e g ia tri N U L L .
TRO Search (TRO root. Item X)
1
TRO p;
p = root;
while (p != NULL && p->infor != X)
{
if (X > p->infor)
p = p->Right;
else
if (X < p->infor)
p = p->Left;
}
return p;
}
144
4.3.3.2. Duyet cay nhi phan tim kiem
Nhu ta da biet cay nhi phan tim kiem cung la cay nhi phan nen cac phep
duyet tren cay nhj phan cung van dung tren cay nhi phan tim kiem.
4.3.3.3. Chen m ot nut vao cay nhj phan tim kiem
Vice them mot nut c6 truong khoa bang X vao cay phai dam bao dieu kien
rang bupc cua cay nhi phan tim kiem. Ta c6 the them vao nhieu cho khac
nhau tren cay, nhtmg neu them vao mot nut la se la tien Ipi nhat, do ta c6 the
thuc hien qua trinh tuomg tu nhu thao tac tim kiem. Khi ket thiic viec tim
kiem cung chinh la liic tim duoc cho can chen.
• Ciai thuat lap
Trong ham nay ta sir dung bien con tro dja phuang Q chay tren cac niit ctia
cay bat dau tir goc. Khi dang 6 mot niit nao do, Q se xuong niit con trai (hay
phai) tuy theo khoa 6 nut goc 1dm horn (hay nho han) khoa X.
O tai mot nut nao do khi P muon xuong nut con trai (phai) thi phai kiem tra
xem niit nay c6 niit con trai (phai) khong. Neu c6 thi tiep tuc xuong, ngupc
lai thi treo nut mcri vao ben trai (phai) nut do. Dieu kien Q = NULL se ket
thiic vdng I3p. Qua trinh nay dupe lai iSp khi c6 dinh mdri dupe chen vao.
/* H am in sertQ ho s u n g th em nut c6 k h o a X vao cay, h a m tra ve 1 n eu bo
su n g th a n h cong, ngicgc Igi ham tra ve 0 - trin'm g hg p nut c6 kh o a X d a c6
tren c a y * /
int Insert(TRO Sroot, Item X)
{
TRO P, Q;
P = new Node;
P->infor = X;
P->Left = NULL;
P->Right = NULL;
if (root == NULL)
{
root = P;
return I;
}
3-GIA] THUAT
145
42
Hinli 4.15. Mpt cay nhj phan tim kiem
4.3.3.4. Loai bo nut tren cay nhjphan tim kiem
06i lap voi phep toan chen vao la phep loan loai bo. Chung ta can phai loai
bo khoi CNPTK mot dinh c6 khoa X (ta goi tat la nut X) cho truoc, sao cho
vice buy mot nut ra khoi cay cung phai bao dam dieu kien rang buoc ctia
CNPTK.
Co ba truong hop khi huy mot nut X c6 the xay ra:
- X la nut la
- X la mit chi c6 mot con trai hoac con phai
- X CO dii hai con
• Truerng herp thi'i nhdl: Chi don gian huy nut X vi no khong lien quan den
phan tir nao khac.
Cay sau khi xoa
Hiitli 4.16. X6a nut Id tren cay
• Trm'mg h(rp ihu hai: Trude khi xoa nut X can moc noi cha ciia X vdi nut
con (nut con trai hoac nut con phai) ciia no.
147
a. Cay trirdc khi xo4 niit 25
b. Cay sau khi xo4 nut 25
H'mh 4 .1 7 . X6a niit c6 niQt con
• T ruo n g h^xp lo n g qudi: Khi nut bi loai bo c6 ca cay con trai va cay con
phai, ta tim nut thay the cho mit bj xoa. Nut thay the la nut c6 gia tri Ion
nhat tren cay con trai hoac nut c6 gia trj nho nhat tren cay c6 nut goc bj
xoa. Do vay ta se phai thay doi mot so lien ket 6 cac nut:
- Nut cha ciia nut bi loai bo
- Nut duQtc chpn 1 ^ nut thay the
- Niit cha cua nut duoc chon 1 ^ nut thay the
b. Cay sau khi xoa niit 20
a. Cay trade khi xo^ nut 20
H in li 4 .18 . Xda nut day dii
d day ta chon nut thay the niit bi xoa la nut c6 gia trj Ion nhat tren cay cor
trai cua cay c6 nut goc 20.
148
}
else // Xu ly truong hpp tong quat
{
T = P->Left;
if (T->Right == NULL)
{
T->Right = P->Right;
Q = T;
delete P;
}
else
{
S = T->Right; //Tim nut thay the
while (S->Right != NULL)
{
T = S;
S = T->Right;
}
S->Right = P->Right;
T->Right = S->Left;
S->Left = P->Left;
Q = S;
free(P);
}
}
}
H to xoa trudng dir lieu bang X
- Tim den nut c6 trudmg du li?u bang X
- Ap dyng ham Del de xoa
Sau day chiing ta se viet ham loai khoi cay goc Root dinh c6 khoa X cho
truoc. Do la ham de quy, no tim ra dinh c6 khoa X, sau do ap dung ham Del
de loai dinh do ra khoi cay.
void Delete (Item X)
{
if (root != NULL)
if (x < root->infor) Delete (root->Left, X)
else if (X > root->infor) Delete (root->Right, X)
else Del(root);
}
150
| 1/20
| | Tải xuống

Có thể bạn quan tâm:

Preview text:

Chuong 4 CAY
Trong chuang nay chiing ta se nghien curu mo hinh du lieu cay (tree). Cay la
mot cau true phan cap tren mot tap hop nao do cac doi tugng. Mot vi du
quen thupc ve cay, do la cay thu muc hoac muc luc cua cuon sach cung la
mot cay. Cay dugc sir dung rong rai trong rat nhieu van de khac nhau.
Chang han no dugc ap dung de to chuc thong tin trong cac he co so du lieu,
de mo ta cau true cii phap ci a cac chuong trinh nguon khi xay dung cac
chuong trinh djeh. Rat nhieu bai toan ma ta gap trong cac Imh vuc khac
nhau dugc quy ve vice thuc hien cac phep toan tren cay. Trong chuong nay
chiing ta se trinh bay djnh nghTa, cac khai niem co ban ve cay. Chung ta
cung se xet cac phuong phap cai dat cay va thuc hien cac phep toan co ban
tren cay. Sau do ta nghien emr ky mot so dang cay dac biet do la cay nhj
phan tim kiem va cay can bang.
4.1. CAY VA CAC KHAI NIEM CO BAN 4.1.1. Djnh nghTa
D jn h nghTa I: Mot cay la tap hgp huu h ^ cac nut trong do co mgt ni t dac
biet ggi la goc (root). Giua cac nut co moi quan hp phan cap ggi la quan he cha-con.
D jn h nghTa 2: Cay dugc djnh nghTa de quy nhu sau:
- Mgt nut la mgt cay va nut nay cung la goc ciia cay.
- Gia sir T|, T2, .... T„ (n > 1) la cac cay co goc tuong img ri, r2,..., r„. Khi
do cay T voi goc r dugc hinh thanh bang each cho r tro thanh nut cha cua
cac ni t ri, r2,..., rn. 131
4.1.2. Mot so khai niem cd ban
- Bac c m mpt nuf. la so con cua nut do.
- Bgc cua mot cay: la bac cua mit c6 bac Ion nhat tren cay do (so cay ccot
toi da cua mot nut thupc cay). Cay c6 bac n thi goi la cay n - phan.
- N ut gdc: la nut khong c6 nut cha.
- Niit Id: la nut c6 bac bang 0.
- Niit nhdnh: la nut c6 bac khac 0 va khong phai la ni t goc. - Mice cua mgt nut: Muc (g6c (To)) =1
Goi T|. Ti. . T„ la cac cay con cua To.
Khi do Muc (T ,) = Muc (T2) = . . = Muc (T„) = Muc (To) +1
- Chieu cao cua cay: la muc ci a nut c6 muc Ion nhat c6 tren cay do.
- D uong di: Day cac nut ni, n2, . ., nk dupe goi la dubmg di neu ni la ( cl
cua ni+i (1 < i < k-1).
- D g ddi cua duemg di: la so nut tren duong di trir 1.
- Cay dugc sap thu tu: Trong mpt cay, nSu cac cay con cua moi mit dduc
sip theo mpt thu tp nhat dinh, thi cay dupe gpi la cay dupe sap (cayy (
thu tu). Ching han, hinh minh hoa hai cay dupe sip khac nhau. 132
Hinh 4.2. Hai cay duffc s3p khae nhau
- Rung-, la tap hop him han cac cay phan biet.
H'mh 4.3. Ru ng gom ba cay
Sau day ta se tim hieu mot loai cay dac biet dugc gpi la cay nhi phan. 4.2. CAY NHI PHAN 4.2.1. Djnh nghia
Cay nhi phan la cay ma moi nut c6 toi da hai cay con. Doi voi cay con cua
mot nut ngudi ta cung phan biet cay con trai va cay con phai.
Nhu vay cay nhi phan la cay c6 thu tur. 4.2.2. Tinh chat
Doi voi cay nhi phan can chu y tai mot so tinh ch4t sau;
1. So lugng toi da cac nut c6 6 muc i tren cay nhj phan la 2 ' (i ^ 1).
2. So lugng ni t t6i da tren mot cay nhi phan c6 chigu cao h la 2''-l(h > 1 ). 133 C hung m inh
- Ti'nh chat 1 sg dupe chirng minh bang quy nap.
B uoc c a sa : voi i = 1, cay nhi phan c6 1 = 2^* nut. Vay menh de dung voi i = 1.
B u a c quy nap: Gia su ket qua dung vai muc i, nghia la a muc nay cay nhi
phan CO toi da 2''' nut, ta chung minh menh de dung voi muc i + 1.
Theo djnh nghia cay nhj phan thi tai moi nut c6 toi da hai cay con nen moi
nut a miic i c6 toi da hai con. Do do theo gia thiet quy nap ta suy ra tai muc i + 1 ta CO 2'“'x2=2'mit.
- Tinh chat 2 dugre chung minh nhu sau;
Ta da biet rSng chieu cao ci a cay la so miic Ion nhat c6 tren cay do. Ta c6
so nut toi da c6 tren cay nhj phan voi chieu cao h la:
2®+2' + ... + 2''‘ ' = 2 ''-l. Tir ket qua nay c6 the suy ra:
Neu cay nhi phan c6 n nut thi chieu cao ci a no la h = f log2(n + 1 )1
(Ta quy uoc : fx1 la so nguyen nho nhat > x
LxJ la so nguyen Ion nhat < x )
4.2.3. Bieu dien cay nhj phan
4 .2.3.1. L ir u t r i r k e tie p
Phuong phap t\r nhien nhat de bieu dien cay nhj phan la chi ra ni t con trai
va nut con phai ciia moi mit.
De thvrc hign vige nay ta c6 the su dqng mgt mteg de luu tri cac nut cua cay
nhi phan. Moi nut cua cay dugre bieu dien boi b ^ ghi gom ba th^h phan:
infor: mo ta thong tin gin voi moi ni t. Left: chi mit con trai. Right: chi mit con phai.
Gia su cac nut cua cay dugre danh s6 tir 0 dgn max-1, du ligu cua cac mit
tren cay c6 kieu la Item . Khi do cau true du ligu bieu dien cay nhi phan dugre khai bao nhu sau:
#define max N //so thii tg Ion nhat cua nut tren cay 134
//Khai bao kieu du li?u Item (neu can) struct Node { Item infer; int Letf; int Right; }; Node Tree[max];
Bang 4.1 minh hoa cau true du lieu bieu dien cay nhi phan trong hinh 4.5
Bang 4.L Cau true dir li|u bieu diln cay infor Left Right 1 A 2 3 2 B 4 5 3 C 6 7 4 D 0 8 5 E 9 10 6 F 0 0 7 G 11 9 8 H 0 0 9 1 0 0 10 J 0 0 11 K 0 0 135
Neu CO mot cay nhi phan hoan chinh day di , ta c6 the de dang danh so cho
cac nut tren cay do theo thu tir Ian lugt tir muc 0, 1, 2,... het muc nay den
muc khac va tu trai qua phai d6i vai cac nut a moi muc. Vi du voi hinh 4.6 CO the danh so nhu sau:
Hinli 4.6. Cay nhj phan dirp’c danh so
Ta c6 nhan xet sau: con cua nut i la cac nut 2i+l va 2i + 2 hoac cha cua nut j laLj/2-lJ.
Nhu vay, ta c6 the luu tru cay nay bang mot mang T, theo nguyen tac: nut
thu i cua cay duqc luu tm a T[i]. Do chinh la each luu tru ke tiep doi vai
cay nhi phan. Vai each luu tru nay neu biet dugc dia chi ciia mit con se tinh
dugc dia chi nut cha va ngugc lai.
Vai cay day du neu tren thi hinh anh luu tru se nhu sau: A B C D E F G T[0] T[l] T[2] T[3] T[4] T[5] T[6] Nhdn xel:
Neu cay nhj phan khong d4y du thi each luu tru nay khong thich hop vi se
gay ra lang phi bo nha do c6 nhieu phan tir bo trong (ung vai cay con rong).
Ta hSy xet cay nhu hinh 4.7. De luu tru cay nay ta phai diing mang gom 15
phan tu ma chi c6 5 phan tir khac rong, hinh anh luu tru mi^n nha cua cay nay nhu sau: 36
H'mh 4.7. Cay nhj phan dSc bift B 0 C 0 0 0 D 0 0 0 0 0 0 0 E 0 ( 0 : chi cho trong)
Neu cay nhj phan luon bien dong nghTa la c6 phep bo sung, loai bo cac nut
thircmg xuyen tac dong thi each luu tru nay gap phai nipt so nhuoc diem nhu
phai dich chuyen cac phan tu trong mang dan den ton thai gian khi phai
thirc hien cac thao tac nay, dp cao ciia cay phu thupc vao kich thuac cua mang,. .
4.2.3.Z. Luu tru-moc noi
Cach lull tru nay khac phuc dupe nhung nhupc diem cua each luu tru ke
tiep dong thai phan anh dupe dang tu nhien cua cay.
I'rong each liru tru moc noi, moi nut tuang ung voi mot phan tu nho c6 quy each nhu sau: Letf infer Right
- infer ung vai thong tin (du lieu) cua ni t.
— T.pf t I'rng vai con trb. trb tai cay con trai ciia niit do.
- Right irng voi con tro, tro tai cay con phai cua nut do.
Ta CO the khai bao cau trite du lieu nhu sau: struct Node Item infor; Node *Left, *Right; }; typydef Node *TRO;
TRO Root; // Con tro Root tro vao nut goc cay 137
Vi du: Cay nhj phan hinh 4.6 c6 dang liru tru moc noi nhu a hinh 4.8 root
Hhili 4.8. Cay nhj phan liru trO' m6c noi
De liru tru va thao tac vai cay, can mot con tro r o o t, tro tai nut goc ciia cay.
4.2.4. Phep duyet cay nhj phan
Vice truy xuat vao cac mit mot each c6 he thong, sao cho moi ni t duoc truy
xuat dung mpt Ian theo mot thii tp xdc dinh, gpi la phep duypt cay. Co the
duyet cay nhj phan theo mpt trong ba thu tir: duyet truoc, duyet giua va
duypt sau, cac phep duypt nay dupe djnh nghTa de quy nhu sau;
4.2.4.1. Day ft theo thir t{r trir&c (Node-Left-Right, Node-Right-Left) Neu cay khac rong
- Tham goc (truy xuat nut goc).
- Duyet cay con trai theo thu tu truoc.
- Duyet cay con phai theo thu tu truoc.
4.2.4.2. Day ft theo thirtugiita (Left-Node-Right, Right-Node-Left) Neu cay khac rong
- Duyet cay con trai theo thu tu giua. - ThSm goc.
- Duyet cay con phai theo thu tu giua. 138
4.2.4.3. Duyft theo th& tu sau (Left-Right-Node, Right-Left-Node) Neu cay khac rong
- Duyet cay con trai theo thu tir sau.
- Duyet cay con phai theo thu tir sau. - Thant goc.
Tuomg ling vai ba phep duyet ta c6 ba ham duyet cay nhj phan. Sau day la
ham de quy duyet cay theo thu tu trudc: void NLR (TRO root) { if (root != NOLL) { visit(root); NLR(root->Left); NLR(root->Right); } }
Mot each tuomg tu, ta c6 the viet dugc cac ham de quy di qua cay theo thu
Vai cay nhi phan hinh 4.9, day cac ni t dugc tham trong cac phep duyet la:
- Duyet theo thu tu truac: A B D G H E C F I G - Duyet theo thu giua: G D H B E A F I C G
- Duyet theo thii tu sau: G F I D E B I F G C A 139
4.2.5. Cay nhj phan bieu dien bieu thu'c
Cay bieu thuc la cay nhj phan ma nut goc va cac ni t nhanh chira cac toan tir
(phep loan) con cac nut la thi chua cac toan h^ g.
4 .2.5.1. Cach dung cay bieu thirc
Doi vai phep toan hai ngoi (chang han +, *, /) dugc bieu dien bai cay nhi
phan ma goc cua no chua toan tir (TT), cay con trai bieu dien toan hang
(TH) ben trai, con cay con ben phai bieu dien toan hang ben phai.
Doi vai phep toan mot ngoi nhu "phi dinh" hoac "phep toan doi dau", hoac
cac ham chuan nhu exp() hoac cos()... thi cay con ben trai rong. Con voi cac
phep toan mot toan hang nhu phep "lay dao ham" ()' hoac ham "giai thira"
()! thi cay con ben phai rong.
HUth 4.1 L Mpt so cay bieu thiic 140 Nhdn xet :
Neu ta duyet cay bieu thirc theo thir tir trudc thi ta dirge bieu thirc Ba Lan
dang tien to (pre-fix). Neu duyet cay nhi phan theo thu tu sau thi ta c6 bieu
thirc Ba Lan dang hau to (post-fix); con theo thir gi ra thi ta nhan dugc each
viet thong thuong ciia bieu thuc dang trung to.
4.2.5.2. Vi du ting dung
De minh hga cho nhan xet nay ta lay vf du sau;
Cho bieu thirc P = a*(b - c) + d/e
1. Hay dung cay bieu thuc bieu dien bieu thiic tren
2. Dua ra bieu thuc 6 dang tien to va hau to Gicii:
1. Ta CO THI = a*(b - c )!
suy ra cay bieu thuc c6 TH2 = d/e J
Xet THI = a*(b - c), toan hang chua a dang co ban
ta phai phan tich de dugc nhu a (1) TH3 = a
T cay bieu thirc ciia toan hang nay la TH4 = b - c J
Toan hang TH4 da 6 dang co ban
nen ta co ngay cay bieu thuc
Cung tuoTig tu nhu vay doi voi
toan hang TH2, cay bieu thuc
tuomg ung veri toan hang nay la
H'mh 4.12. Xay dung cay bieu dien bieu thiic 141
l ong hop cay bieu thirc cua cac loan hang ta dirac cay bieu thuc sau:
///;;/; 4.13. Cay bieu thiic
B ay g id ta d u yet c a y b ieu th iic d hinh 4 .1 3
- Duyet theo thi'c tu Iruac:
+ * a - b c / d e (b ieu thirc titn to)
- Duyet theo thu sau:
a b c - * d e / + (b ieu thurc h(u to)
4.3. CAY NHI PHAN TIM KIEM
C ay nhi phan dirge sii d u n g v a o n h ieu m uc d ich khac nhau T uy nh ien viei
sir d u n g c a y nhi phan d e liru giir va tim k iem th o n g tin 'an la m ot tron]
n h u n g lin g d u n g quan trgng nhat ciia ca y nhj phan. T ron g pian n ay ch iin g t
se n g h ien cu u m o t Idp ca y nhj phan dac biet ph uc v u c b v ic e tim kiSn
th on g tin, d o la c a y n h | phan tim k iem .
T ron g th u c te, m ot Idp d oi tu g n g nao d o c 6 the d u g c m o ta >di m pt k ieu ba
gh i, ca c trudn g cu a ban ghi b ieu d ien ca c thu gc tinh cu a i6i tu g n g . T ron
bai toan tim k iem th on g tin, ta th u d n g quan tarn den m g tn h o m ca c thug
tinh nao do ciia d o i tu g n g m a thu oc tinh nay h oan toan x.c din h d u g c dt
tu g n g . C h u n g ta g g i ca c th u gc tinh nay la khoa. N h u v a y , kioa la m ot nhdr
cac th u g c tinh cu a m ot la p d o i tu g n g sao ch o hai doi tugn ; kh ac nhau ph;
c 6 g ia tn khac nhau tren n h om th u gc tinh do. 4.3.1. Djnh nghTa
C ay nhj phan tim k iem (C N P T K ) la ca y nhi phan h o a c o n g hoac khon
rong thi phai th o a m an d o n g thdi ca c d ieu kien sau: 142
- K h oa ciia c a c niit th u o c c a y co n trai nh o h o n k h o a nut g o c .
- K hoa ciia nut g o c nh o h on kh oa cua cac nut thu oc ca y c o n phai cu a nut goc.
- C ay c o n trai v a c a y c o n phai cu a g o c c u n g la c a y n h i phan tim k iem .
H in h 4 .1 4 b ie u d ien m o t c a y nhi phan tim k ie m , tron g d o k h o a c iia ca c dinh la cac s o n g u y en .
Hlnh 4.14. Cay nhj phan tim kiem
4.3.2. Cai dat cay nhj phan tim kiem
M o i nut tren c a y nhj ph an tim k iem c 6 dang; Left infor Right
T rong do: L eft la c o n tro tro toi c a y co n trai, R igh t la c o n tro tro to i c a y c o n
p h ai, c o n in fo r c h u a th o n g tin ciia nut.
G ia sir dir lieu tren m o i nut ciia e a y c 6 k ieu d u lie u la Item, khi d o cau true
d fi li?u cu a c a y tim k ie m nhj phan d u g c din h n g h ia n h u sau: struct Node Item infor; Node *Left, *Right; }; typedef Node *TRO; TRO root;
T iep th e o ta n g h ie n ciru c a c p h ep toan tren c a y nhi phan tim k iem . 143
4.3.3. Cac thao tac cd ban tren cay nhj phan tim kiem 4.3.3.1. Tim kiem
T im k ie m tren c a y la m pt trong c a c p h ep toan qu an trpng nhat d o i v o i i c
nhi ph an tim k iem . T a x et bai toan sau: B a i loan:
G ia sir m o i nut tren c a y nhi phan tim k ie m la m o t b an g h i, Ibi
c o n tro r o o t ch i ta l g o c cu a c a y v a X la k h oa c h o tru o c. V a n d e dat rra
tim x e m tren c a y c 6 c h u a nut v o i k h oa X h ay k h on g. • Giai thuat de quy
n a y tra v e c o n tro tro to i nut c 6 k h oa bSng x , n g u p c lai tra v e N U L IL
TRO Search(TRO root. Item x) { if (root == NULL) return NULL;
else if (x < root->infor)
return Search(root->Left, x) ;
else if (x > root->infor)
return Search(root->Right, x) ; else return root; } • Ciai thuat lap
H am nay tra v e nut c 6 k h o a b an g x , n g u p c lai tra v e g ia tri N U L L .
TRO Search (TRO root. Item X) 1 TRO p; p = root;
while (p != NULL && p->infor != X) {
if (X > p->infor) p = p->Right; else
if (X < p->infor) p = p->Left; }return p; } 144
4.3.3.2. Duyet cay nhi phan tim kiem
Nhu ta da biet cay nhi phan tim kiem cung la cay nhi phan nen cac phep
duyet tren cay nhj phan cung van dung tren cay nhi phan tim kiem.
4.3.3.3. Chen mot nut vao cay nhj phan tim kiem
Vice them mot nut c6 truong khoa bang X vao cay phai dam bao dieu kien
rang bupc cua cay nhi phan tim kiem. Ta c6 the them vao nhieu cho khac
nhau tren cay, nhtmg neu them vao mot nut la se la tien Ipi nhat, do ta c6 the
thuc hien qua trinh tuomg tu nhu thao tac tim kiem. Khi ket thiic viec tim
kiem cung chinh la liic tim duoc cho can chen. • Ciai thuat lap
Trong ham nay ta sir dung bien con tro dja phuang Q chay tren cac niit ctia
cay bat dau tir goc. Khi dang 6 mot ni t nao do, Q se xuong niit con trai (hay
phai) tuy theo khoa 6 nut goc 1dm horn (hay nho han) khoa X.
O tai mot nut nao do khi P muon xuong nut con trai (phai) thi phai kiem tra
xem ni t nay c6 niit con trai (phai) khong. Neu c6 thi tiep tuc xuong, ngupc
lai thi treo nut mcri vao ben trai (phai) nut do. Dieu kien Q = NULL se ket
thiic vdng I3p. Qua trinh nay dupe lai iSp khi c6 dinh mdri dupe chen vao.
/* Ham insertQ ho sung them nut c6 khoa X vao cay, ham tra ve 1 neu bo
su n g thanh cong, ngicgc Igi ham tra ve 0 - trin'mg hgp nut c6 khoa X da c6 tren ca y* /
int Insert(TRO Sroot, Item X) { TRO P, Q; P = new Node; P->infor = X; P->Left = NULL; P->Right = NULL; if (root == NULL) { root = P; return I; } 3-GIA] THUAT 145 else { Q = root; while (Q != NULL) if (X < Q->infor) { if (Q->Left != NULL) Q = Q->Left; else { Q->Left = P; return 1; }
}elseif (X > Q->infor) {
if (Q->Right != NULL) Q = Q->Right; else { Q->Right = P; return 1; } }else return 0; } } N hdn xet:
De d^mg dugc cay nhj phan tim kiem ung vai rngt day khoa dua vao ban
each lien tgc bo sung cac nut umg vdi timg khoa, hat dau tu cay rong. Ba
dau phai dimg len cay vai niit goc la khoa dau tien sau do doi vai cac khc
tiep theo, tim tren cay khong c6 thi bo sung vao.
Vi du vai day khoa: 42 23 74 11 65 58 94 36 99 87
thi cay nhj phan tim kiem dung dugc se c6 d ^ g a hinh 4.15 146 42
Hinli 4.15. Mpt cay nhj phan tim kiem
4.3.3.4. Loai bo nut tren cay nhjphan tim kiem
06i lap voi phep toan chen vao la phep loan loai bo. Chung ta can phai loai
bo khoi CNPTK mot dinh c6 khoa X (ta goi tat la nut X) cho truoc, sao cho
vice buy mot nut ra khoi cay cung phai bao dam dieu kien rang buoc ctia CNPTK.
Co ba truong hop khi huy mot nut X c6 the xay ra: - X la nut la
- X la mit chi c6 mot con trai hoac con phai - X CO dii hai con
• Truerng herp thi'i nhdl: Chi don gian huy nut X vi no khong lien quan den phan tir nao khac. Cay sau khi xoa
Hiitli 4.16. X6a nut Id tren cay
• Trm'mg h(rp ihu hai: Trude khi xoa nut X can moc noi cha ciia X vdi nut
con (nut con trai hoac nut con phai) ciia no. 147 a. Cay trirdc khi xo4 niit 25 b. Cay sau khi xo4 nut 25
H'mh 4.17. X6a niit c6 niQt con
• Truong h^xp long qudi: Khi nut bi loai bo c6 ca cay con trai va cay con
phai, ta tim nut thay the cho mit bj xoa. Nut thay the la nut c6 gia tri Ion
nhat tren cay con trai hoac nut c6 gia trj nho nhat tren cay c6 nut goc bj
xoa. Do vay ta se phai thay doi mot so lien ket 6 cac nut: - Nut cha ciia nut bi loai bo
- Nut duQtc chpn 1 ^ nut thay the
- Niit cha cua nut duoc chon 1 ^ nut thay the
b. Cay sau khi xoa ni t 20
a. Cay trade khi xo^ nut 20
H inli 4.18. Xda nut day dii
d day ta chon nut thay the ni t bi xoa la nut c6 gia trj Ion nhat tren cay cor
trai cua cay c6 nut goc 20. 148
Sau day la giai thuat thuc hien viec loai bo mot nut tro boi Q. Ban dau Q
chi'nh la con trai hoac con phai ciia mot nut R (nut cha ciia Q) tren cay nhj
phan tim kiem, ma ta gia su da biet roi. R R
a. Cay Iruac khi xoa nut tro bai Q
t>. Cay sau khi xoa nut tro bbi Q
Hinh 4.19. Xoa nut trb bbi con trb Q
void Del(TRO Q) //xoa nut tro bdi Q { TRO T, S, P;
P = 0; //Xir ly truona hop nut la va nut ro mot non if (P->Left == NULL) { Q = P->Right; free{P); }else
if (P->Right == NULL) { Q = P->Left; free{P); 149 }
else // Xu ly truong hpp tong quat { T = P->Left;
if (T->Right == NULL) {
T->Right = P->Right; Q = T; delete P; }else {
S = T->Right; //Tim nut thay the
while (S->Right != NULL) { T = S; S = T->Right;
}S->Right = P->Right;
T->Right = S->Left;
S->Left = P->Left; Q = S; free(P); } }
}Hto xoa trudng dir lieu bang X
- Tim den nut c6 trudmg du li?u bang X - Ap dyng ham Del de xoa
Sau day chiing ta se viet ham loai khoi cay goc Root dinh c6 khoa X cho
truoc. Do la ham de quy, no tim ra dinh c6 khoa X, sau do ap dung ham Del
de loai dinh do ra khoi cay. void Delete (Item X) { if (root != NULL)
if (x < root->infor) Delete (root->Left, X)
else if (X > root->infor) Delete (root->Right, X) else Del(root); } 150