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

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:103

Thêm vào BST

Báo xấu

34
lượt xem 14
download

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

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.

Chủ đề:

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

Lưu

Nội dung Text: 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 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 C mot cay nhi phan hoan chinh day dii, ta c6 the de dang danh so cho O 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 C the danh so nhu sau: O 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 C the khai bao cau trite du lieu nhu sau: O 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. D ay 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. D uyft 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: A B D G H E C F I G - Duyet theo thu giua: GDHBEAFICG - 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 niit 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 "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 C THI = a*(b - c ) ! O 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 i d ta d u y e t c a y b ie u th iic d h in h 4 .1 3 - Duyet theo thi'c tu Iruac: + * a - b c / d e (b ie u thirc titn to) - Duyet theo thu sau: a b c - * 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 ir g e s i i d u n g v a o n h ie u m u c d ic h k h a c n h au T u y n h ie n viei sir d u n g c a y n h i p h a n d e liru giir v a tim k ie m th o n g tin 'a n la m o t tron] n h u n g lin g d u n g q u a n tr g n g n h at c iia c a y nhj p h a n . T r o n g p ia n n a y c h iin g t s e n g h ie n c u u m o t Idp c a y nhj p h an d a c b ie t p h u c v u c b v i c 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 a o 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 tr 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 tin h c u a i6 i 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 t n h o m c a c th u g tin h n a o d o c iia d o i t u g n g m a th u o c tin h n a y h o a n to a 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 c a c th u g c tin h n a y la k h o a . N h u v a y , k io a la m o t nh dr c a c th u g c tin h c u a m o t la p d o i t u g n g s a o c h o hai d o i tu g n ; k h a c n h a u ph; c 6 g ia tn k h a c n h a u tren n h o m th u g c tin h d o . 4.3.1. Djnh nghTa C a y nhj p h a n tim k ie m ( C N P T K ) la c a y n h i p h a n h o a c o n g h o a c k h o n ro n g thi p h a i t h o a m a n d o n g th d i c a c d ie u k ie n sau : 142
- K h o a c iia c a c n iit t h u o c c a y c o n trai n h o h o n k h o a n u t g o c . - K h o a ciia n u t g o c n h o h o n k h o a c u a c a c nut th u o c c a y c o n p h ai 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 ie u d ie n m o t c a y n h i p h a n tim k ie m , tr o n g d o k h o a c iia c a c d in h la c a c s o n g u y e n . Hlnh 4. 14. C ay nhj phan tim kiem 4.3.2. Cai dat cay nhj phan tim kiem M o i n u t tren c a y nhj p h a n tim k ie m c 6 d an g; Left infor Right T r o n g d o : L e ft 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 to i c a y c o n p h a i, c o n in fo r c h u a t h o n g tin c iia nut. G ia sir d ir lie u tren 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 fi li? u c u a c a y tim k ie m nhj 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 ie p t h e o ta n g h ie n c ir u c a c p h e p to a n tren 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 la m p t tr o n g c a c p h e p to a n q u a n trp n g n h a t d o i v o i i c n h i p h a n tim k ie m . T a x e t b a i to a n sau : B a i lo a n : G ia sir m o i n u t tren c a y n h i p h a n tim k ie m la m o t b a n g h i, Ib i c o n tro r o o t c h i t a l g o c c u 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 tren 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 n u t c 6 k h o a b S n g x , n g u p c la i tra v e N U L I L 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 a m n a y tra v e n u t c 6 k h o a b a n g x , n g u p c la i tra v e g i a 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 insertQ ho su n g them nu t c6 kh o a X vao cay, h a m tra ve 1 n e u bo su n g thanh cong, ngicgc Igi ham tra ve 0 - trin'm g h g p n u t c6 kh o a X d a c6 tre n 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
else { Q = root; while (Q != NULL) if (X < Q->infor) { if (Q->Left != NULL) Q = Q->Left; else { Q->Left = P; return 1; } } else if (X > Q->infor) { if (Q->Right != NULL) Q = Q->Right; else { Q->Right = P; return 1; } } else return 0; } } N h d n 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 C dii hai con O • 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 ru o 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 .1 8 . 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
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); } } } 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