Giáo trình Cấu trúc dữ liệu và giải thuật: Phần 2 - An Văn Minh, Trần Hùng Cường

Nối tiếp nội dung phần 1, phần 2 giáo trình "Cấu trúc dữ liệu và giải thuật" trình bày một dạng cấu trúc dữ liệu phi tuyến; mô tả, thiết kế và đánh giá các giải thuật sắp xếp và tìm kiếm thông dụng, cũng như vấn đề cài đặt các giải thuật này trong bài toán ứng dụng. Mời các bạn cùng tham khảo nội dung chi tiết.
Nội dung trích xuất từ tài liệu:
Giáo trình Cấu trúc dữ liệu và giải thuật: Phần 2 - An Văn Minh, Trần Hùng Cường 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 - B a c c m m p t nuf. la so con cua nut do. - B g c cu a m ot 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 cu a 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 cao cu a 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 cu a d uem 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 inh - 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 q u y nap: Gia su ket qua dung vai muc i, nghia la a muc nay cay nhi phan C toi da 2''' nut, ta chung minh menh de dung voi muc i + 1. O Theo djnh nghia cay nhj phan thi tai moi nut c6 toi da hai cay con nen moi nut a miic ic6 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 i r u t r i r k e tie 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 ...