Bài giảng Cấu trúc dữ liệu - Chương 4: Tìm kiếm

̀

NG 4 TI M

ƯƠ CH KIÊ Ḿ

́

ƯƠ

CH

̀ NG 4. TI M KIÊ M

́ ́ ̀ ươ ́ 4.1 Ca c ph ́ ng pha p ti m kiê m trong danh sa ch

̀ ́ ́ ́ 4.1.1 Ti m kiê m tuyê n ti nh

̀ ́ ̣ 4.1.2 Ti m kiê m nhi phân

̀ ́ ̣ 4.1.1 Ti m kiê m nôi suy

̀ ́ ̣ 4.2 Cây nhi phân ti m kiê m

̣ 4.2.1 Đinh nghi ã

́ ́ ́ 4.2.2 Ca c phe p toa n

́

ươ

̀ ng pha p ti m kiê m

̀ ́ ̉ :

́ ́ ̀ ượ ̣ ̣ ́ Mô hi nh chung cua ba i toa n ti m kiê m ́ ́ ng co

́ ̀ ̣ ̉ ̣ ̣ ̉

́ ́ ̀ ̉

ư ̣ ̉ ̣

́ ̀ ̀ ̣ ng,

́ ́ ́ ̣ ̣

́ ́ ̣ ng ̀ xx. Câ n ti m

̣ ̣

́ 4.1 Ca c ph trong danh sa ch́ ̀ ̃ ượ ng. Mô i đô i t Co môt tâp n đô i t ̀ ượ c thê hiên bă ng môt kiêu nhiê u thuôc ti nh, đ ̀ ̀ ươ ng. Trong đo co 1 ban ghi gô m nhiê u tr ́ ̀ ́ ́ ̀ ươ ng ma gia tri cua no đăc tr ng cho đô i tr ́ ́ ượ ượ ng, cho phe p xa c đinh hoa n toa n đô i t t ́ ̀ ̀ ươ ng goi la kho a. th ́ ̀ ̀ Ba i toa n ti m kiê m: Co môt tâp ca c đô i ̀ ́ ̀ ượ ượ ươ t c môt đô i t ng va cho tr ̃ ́ ợ xem xx co măt trong tâp h p đa cho hay không?

́

ươ

̀ ng pha p ti m kiê m

̀ ́ ̀ ́ ̀ ́ ̣ ̉

́ ́ ợ ̣ ̣

̀ ́ ̣ ̣

̀ ̀ ̀ ́ ̃ ̣

́ 4.1 Ca c ph trong danh sa ch́ : Mô hi nh toa n hoc cua ba i toa n ti m kiê m ́ ́ Co tâp h p n gia tri kho a k1, k2, ..kn. Cho gia ́ tri kho a x. Ti m xem x co tô n tai ki=x? Công viêc ti m kiê m se hoa n tha nh khi:

̀ – Ti m đ

́ c 1 ban ghi co gia tri kho a =x, lu c đo

ượ

̉ ̣

c tha nh công successful. ́

̀ ượ ̀ phe p ti m kiê m đ ̀ ̉ ̣

̀ ̀ ̀

̀ ́

ợ

̉ ̣ ̉ ̣

– Không ti m thâ y ban ghi na o co kho a bă ng x, goi ̀ la ti m kiê m không tha nh công unsuccessful. Lu c ́ na y co thê xuâ t hiên yêu câ u bô sung gia tri x ̀ va o tâp h p, goi la ti m kiê m co bô sung.

̣ ̣ ̉

̀

́

̀ ự

ng pha p ti m kiê m đ n gian

̉ ̉

́ ng: Bă t đâ u t

́ ban ghi th ́ ̀

̀ ́

ưở ̀ ́

́ t so sa nh kho a ti m kiê m ng ng cua ban ghi trong

ượ

̉ ̉

c ban ghi mong

̉ ̉

̣ ̉

4.1.1 Ti m kiê m tuâ n t (sequential searching)  La ph ̀ ươ ̀ va cô điên. Y t ́ ́ ượ nhâ t, lâ n l ́ ươ ư ơ v i kho a t ̀ ́ ơ i khi ti m đ bang, cho t ́ ́ muô n hoăc đa hê t bang ma ch a ti m thâ y.́

̀ ự

(sequential

4.1.1 Ti m kiê m tuâ n t searching)  Giai thuât 1:

̉ ̣

SEQUENSEARCH(k,n,x) 1. //Kh i đâ ù ở i=1; k[i+1]=x ̃ ́ ̀ 2. // Ti m kho a trong da y while (k[i] !=x) do i++; ́ 3. // Ti m thâ y hay không ́ If (i==n+1) return 0 //không ti m thâ y else return i;

̀ ự

(sequential

4.1.1 Ti m kiê m tuâ n t searching)  Giai thuât 2 (giai thuât đê quyti m trong ́

danh sa ch liên kê t):

Node *timdequy(struct node *first, element_type e) { if (first == NULL) return NULL; else if (first>element == e) return first; else

return timdequy(first>next, e);

}

̉ ̣ ̉ ̣ ̣

̀ ự

(sequential

ươ ươ

min = 1; max = O(n);

4.1.1 Ti m kiê m tuâ n t searching)  Đa nh gia giai thuât: ́ ̀ ợ ng h p tô t nhâ t: T Tr ́ ̀ ợ ng h p xâ u nhâ t: T Tr Trung bi nh T

tb= O(n)

̉ ̣

́ ư ự

c să p xê p theo th t

(tăng

ượ ̀

́ ́ ̀ ̣ ng pha p ti m kiê m thông dung.

̀ 4.1.2. Ti m kiê m nhi phân (Binary Serching)  La ph ̀ ươ  Y t ́ ưở ng: ́ ̃ – Da y kho a đa đ ̀ dâ n hoăc giam dâ n). ̃

́ ̃

̀ – Gia s da y kho a đang xe t la kl va kr thi kho a ơ a da y se la ki v i i = (l+r)/2. ́

–

̣ ̉

̃ ́

ượ c lai, ự c th c hiên

̃ ượ ́ ́ ơ

́ ự ̀

̀ ̃

̃ ́

̀ ư ở

̉ ử ̃ ̀ ở ư gi ́ ̀ Ti m kiê m se kê t thu c nê u x=ki. Ng ́ ̀ ́ nê u xki, phe p ti m kiê m se ơ ượ đ c th c hiên tiê p v i ki+1 v i kr. ́ ̀ ́ – Qua tri nh ti m kiê m se d ng khi ti m thâ y ́ kho a hoăc da y đang xe t tr nên rô ng.

̀ 4.1.2. Ti m kiê m nhi phân (Binary Serching)  Giai thuât 1:

̉ ̣

ở

́ ́ ̃ ư ̉ BINARYSEARCH(k,n,x) b1. l=1; r=n;//kh i đâ ù b2. while (l<=r) do //ti m̀ a

{m = (l+r)/2; //ti nh chi sô gi if x k[m] then l = m+1;

else return m;

}

́ ̀ b3. return 0; // ti m không thâ y.

̀ 4.1.2. Ti m kiê m nhi phân (Binary Serching)  Giai thuât 2(giai thuât đê quy):

̉ ̣ ̉ ̣ ̣

RBINARYSEARCH(l,r,k,x) b1. if l

̉ ̉

́ ươ ư ng ng cua ̀ ́ ́ ́ ư then loc=0// loc ch a chi sô t ̀ //kho a câ n ti m

else m = (l+r)/2;

if x

then loc = RBINARYSEARCH(l,m1,k,x) else if x>k[m] then loc = RBINARYSEARCH(m+1,r,k,x) else loc=m;

B2: Return loc;

̉ ̣

́ – Tr

̀ 4.1.2. Ti m kiê m nhi phân (Binary Serching)  Đa nh gia giai thuât: ́ ̀ ng h p tô t nhâ t Tmin =1, ti m đ ̀

̀ ́ ươ ợ ượ c

̀ ngay lâ n đâ u tiên.

́ ợ

ươ ́ư c Ttb = O(log2n).

̉ ̉ ̣

́ ̃

̀ c điêm la da y phai

́ ́

̉ ̉

́ c să p xê p.

́ ̀ – Tr ng h p xâ u nhâ t Tmax = k+w[n/2k) – Ch ng minh đ ượ ́ ́ ́ Trong tâ t ca ca c giai thuât ti m kiê m, ́ ti m kiê m nhi phân la nhanh nhâ t, ượ ư nh ng no co nh ́ ượ đ

̀

̀ Ba i tâp vê nha

ươ

ự

ng tri nh th c hiên ca c viêc

̣ ̣

́ ươ ̣ ̣

B1. Viê t ch sau: ́ a. Nhâp ca c gia tri nguyên d ́ ̉ ư

ư ng t ́ ̉

̃ ̀ ̃ ́ ̣

̀ ́ ̀ ̀ ba n ́ phi m (tô ch c theo kiêu danh sa ch liên kê t).́ In ra ma n hi nh da y sô đa nhâp ́ ̀ ̣ ̣ ̣ ̉

b. c. Nhâp môt gia tri X t ́ ́ ́

̀ ́ ́ ̉ ̣ ̉

̀ ̀ ̀ ́ ̣ ̉ ̉

̀ ̀ ̀ ́ ̀ ́ ự ̉ ̣ ́ va ti m kiê m

̣ ̀ ư ba n phi m, kiêm tra ́ X co trong danh sa ch hay không. Nê u co thi tra vê vi tri cua X, nê u không che n X ́ va o vi tri cuô i cua danh sa ch.(Viê t ca 2 ́ giai thuât Ti m kiê m tuâ n t 13 nhi phân).

4.2. Cây nhi phân ti m kiê m

̉ ư

́ ̀

́ ́ ̃

̣ ̣

̀ ̉ ơ ́ ơ

̣ ̣

 Viêc tô ch c tâp h p kho a theo câ u ợ ̀ tru c danh sa ch thi phe p ti m kiê m ́ ́ no i chung la chi phi cao, nê u kho a ́ đa să p xê p thi phe p ti m kiê m nhi ư phân hiêu qua h n nh ng bâ t tiên trong ̀ ử viêc thêm, b t phâ n t

ượ

̉ ̣

 Câ u tru c cây nhi phân ti m kiê m đ ́ ́ ượ ự xây d ng đê khă c phuc ca c nh c điêm trên.

4.2.1 Đinh nghi ã

Đinh nghi ã

̀ : Cây nhi phân ti m kiê m la

̀ ́

̣ ̣

̣ ̣ ̣

́ ư ự ̀

̣ ̣

̉ ̣

́ cây nhi phân ma tai mô i nu t co môt gia ̉ ữ ệ tri kho a thuôc kiêu d li u co th t ̀ ̀ ơ na o đo , đô ng th i thoa ma n điê u kiên sau: – Moi kho a thuôc cây con tra i đê u nho h n

̀ ́ ̉ ơ ̣ ̣

ở ́ kho a

̀ ́ ơ ơ ̣ ̣ ̉ – Moi kho a thuôc cây con phai đê u l n h n

ở ́ kho a

́ ́ nu t cha. ́ ́ nu t cha. ̃ ̣ ̉

́ Theo đinh nghi a, bâ t ky cây con na o cua ́ cây nhi phân ti m kiê m đê u la cây ti m ́ 15 kiê m.

4.2.1 Đinh nghi ã

Vi dú

̣:

34

66

17

25

50

71

75

68

4.2.1 Đinh nghi ã

̣ ơ

Ba i tâp tai l p

̃ ́ ́ ̣ – Ve 4 cây nhi phân ti m kiê m v i ca c gia ́ ̀

̣ ́ ơ tri sau: 3, 4, 6, 8, 9, 10, 14, 15, 17.

́ ́ ̣

́ ̀ ́ ̃ ́ ̀ ́ ́ ̃ ́ ơ ̣ – Ve cây nhi phân ti m kiê m cân đô i cho ca c ́ gia tri trên v i sô nu t rô ng la i t nhâ t.

́

́ 4.2.2 Ca c phe p toa n

̀ ̃

ơ

Phe p ti m kiê m ̀ ́ Phe p che n thêm môt nu t ́ ́ Phe p g ́ ́ loai bo môt nu t

̣ ̉ ̣

̀

́

́ 4.2.2.1 Phe p ti m kiê m

́ ̉

̀ ́ ́ ́ ̉ ̣ Mô ta ca c b Bă t đâ u t ́ ́ ươ c: ̀ ̀ ư gô c cua cây, goi nu t đang xe t la

̃ ̀ ̀ ́

́ ́ ́ ́ ̣ ̉ ̣

̣ ươ

́ ́ c ti m kiê m v i

̣ ươ

̉ ̣

́ ́ c ti m kiê m v i

̉ ̣

́ – Nê u x = kho a cua V, kê t thu c va ti m thâ y

Nê u V rô ng, kê t thu c va ti m không thâ y. ́ ́ Ng ́ ơ ượ c lai, so sa nh x v i kho a cua nu t hiên tai V: ́ ́ – Nê u x< kho a cua V, lăp lai b cây con tra i;́ ́ – Nê u x> kho a cua V, lăp lai b cây con phai;̉ ́ ̉

̀

́

́ 4.2.2.1 Phe p ti m kiê m

int timdequy(int x,NODE *root) { int timthay =0; if ((root ==NULL) || (timthay)) return timthay; else { if (x < root>element) timdequy(x,root>left); else if (x>root>element) timdequy (x,root>right); else timthay =1; }

Thủ tục đệ quy:

̀

́

́ 4.2.2.1 Phe p ti m kiê m

int tim(int x,NODE *root) { int timthay =0; while ((root !=NULL) && (!timthay)) if (root >element==x) timthay=1; else if (x < root>element) root= root>left; else root= root>right; return timthay; }

Thủ tục không đệ quy

́

́ 4.2.2.2 Phe p thêm môt nu t

̀ ́ ́ ́ ̣ ̣ : Tiê n ha nh thêm môt nu t

́ ́ ̀ ́ ̃ ư ̀ m i va o cây nhi phân ti m kiê m sao cho ́ ̃ ư ự . ca c kho a trên cây vâ n gi đu ng th t

́ ̉ ̣ ̣

̀ ́ ́ ́ ̀ ́ ̣

̀ ̀ ́ ́ ̀ ở

́ ̣ ̉ ̉ ̉

̀ ́ ́ ́ ̉ ̉ ̣ Đăt vâ n đê ̀ ́ ơ ́ Y t ́ ưở : Thu tuc thêm môt nu t bă t đâ u ng ̀ ́ ̀ ̀ ư viêc ti m kiê m, nê u ti m thâ y thi kê t t ́ ́ thu c, nê u không ti m thâ y thi tiê n ha nh ́ nha nh con bên tra i hoăc bên phai đê đam bao ti nh châ t cua cây nhi phân ti m kiê m

́

́ 4.2.2.2 Phe p thêm môt nu t

5

2

6

́ư ự .

7

1

4

Vi du: ́ ̣ Thêm ́ ́ ca c nu t 5, 2, 4, 6, 1, 7, 3 ̀ va o môt cây ̃ rô ng theo ́ đu ng th t Qua t ng ̀ư ́ươ b c thêm, ta ́ co cây sau:

3

́

́ 4.2.2.2 Phe p thêm môt nu t

void chen(int e, NODE **root) { NODE *tam; tam = new NODE; tam>element = e; tam>left = NULL; tam>right = NULL; if (*root == NULL) *root = tam; else

́

́ 4.2.2.2 Phe p thêm môt nu t

if (tam>element < (*root)>element) if ((*root)>left) chen(e, &(*root)>left); else (*root)>left = tam; else if(tam>element > (*root)>element) if ((*root)>right) chen(e, &(*root)>right); else (*root)>right = tam; else cout <<"trung";}

́

́ 4.2.2.3 Phe p xo a môt nu t

̣ ̣

̉ ̣ ̉ ̉

Đăt vâ n đê : Sau khi xo a xong môt nu t, thay đôi cây co n lai vâ n đam bao la cây ̀ nhi phân ti m kiê m.

́

́ 4.2.2.3 Phe p xo a môt nu t

Y t

́ ưở ̀

ng: ́

́ ́ ̀ ́ ̣

̉ ̉

̀ ́

̀ – Ti m đê n nu t co kho a bă ng x, goi V la ́ ̀ ́ con tro đê n nu t na y V>element = X ̀ – Xay ra 2 tr ợ ươ ng h p: ́ ̀ ́ ́ ̣ ̉ ̉

́ ́

̣ ̉ ̣

ử nu t cha cua V tro ̀

̣ ̉ ̉

̃ • V la nu t la : chi câ n g bo V bă ng ca ch thay ơ nu t bên tra i hoăc bên phai cua nu t cha V = Null ̃ • V la nu t môt ca nh: g bo V bă ng ca ch s a lai ơ ́ ở mô i nô i (left hoăc right) ̀ ́ ́ xuô ng nu t cha u, cây co n lai vâ n la nhi phân ti m kiê m ́

ươ

ợ

̣ ̣

• Nu t V co đu ca hai cây con: tr

̀ ng h p na y

́ ́

́ư

̉ ̉

kha ph c tap

́

́ 4.2.2.3 Phe p xo a môt nu t

ợ

ự

́ ng h p na y kho a cua nu t V chen ́ a ca c kho a cua nu t c c phai cua cây

ự

̉ ̉ ̉

̉ ̉

́ ̃

̉ ̣ ̉ ̉

̣ ̉

́ ̀ ́

̉ ̉ ̣ ̉

ợ

̉ ̣

ự

Tr ươ ̃ ư gi con tra i va kho a cua nu t c c tra i cua ̃ ơ cây con phai, vây g bo nu t V phai thay ̀ thê môt nu t kha c va o chô trô ng đo đê ́ đam bao điê u kiên cây ti m kiê m, chi co ̀ thê thay thê bă ng môt trong hai nu t con ̀ ́ ́ ươ ng h p thay bă ng trên. Co thê xe t tr nu t c c phai cua cây con tra i.

̉ ̉

́

́ 4.2.2.3 Phe p xo a môt nu t

̉ ̣

́ ́ ̀ ̣ ̣ Giai thuât chi tiê t:́ V i T : cây nhi phân ti m kiê m; X la gia tri câ n

̀ ́ ̉

́ ̀ ́ ́ ́

̉ ̣ ̉

́ ̀ ự ̣ ̣ ̉

̀ ̣ ̣ ̣ ̉ ̣ ̉ ̀ ́ ơ ̀ ́ ́ xo a; V la con tro đê n nu t đang xe t. ́ ̀ ́ ́ ư ư cây gô c V, ti m nu t ch a kho a x Xuâ t pha t t ̀ ́ ợ ươ ng h p sau: đê loai bo, co ca c tr ́ V=Null, không ti m thâ y X< V.element th c hiên loai bo cây bên tra í X> V.element lăp lai viêc ti m đê loai bo cây bên

phai,̉

́ ̀ ̃ ơ ̉ ́ X = V.element, tiê n ha nh g bo nu t V

́

́ 4.2.2.3 Phe p xo a môt nu t

̉ ̣

ơ Nê u V.right = Null, nô i cây con tra i cua V

́ ́ ̉

́ va o nu t cha

Giai thuât chi tiê t:́ G bo nu t V: ́ ̀ ́ ̀

́ ̉ ̉ Nê u V.left = Null, nô i cây con phai cua V

́ ̀ ́ ự ̉ ̉ ̉

va o nu t cha ̀ ̀ ̀ ́ ̉ ̉ ̉ ̣

̀ ́ ̉ ̣ ́ V co đu thi do xuô ng nu t c c phai cua cây ử con tra i va s a cây đê đam bao điê u kiên cua cây nhi phân ti m kiê m.

́

́ 4.2.2.3 Phe p xo a môt nu t

Vi du trong t/h đu ca 2 cây con:

Nút E là nút cực phải của cây con trái, xóa nút V bằng cách:

-Thay nội dung V = E

-Sửa F thành cây con của D

-Hủy nút E

̣ ̉ ̉

́

́ 4.2.2.3 Phe p xo a môt nu t

int xoacuctrai (tree *root ) { int k; if ((*root)>left == NULL) { k=(*root)>element; (*root) = (*root)>right; return k; } else return xoacuctrai(&(*root)>left); }

Hàm xóa phần tử

́

́ 4.2.2.3 Phe p xo a môt nu t

void xoa(int x,tree *root) { if ((*root)!=NULL)

if (x < (*root)>element) xoa(x,&(*root)>left) ; else if (x > (*root)>element) xoa(x,&(*root)>right); else if (((*root)>left==NULL)&&((*root)>right==NULL)) (*root)=NULL; else

Thủ tục xóa

́

́ 4.2.2.3 Phe p xo a môt nu t

Thủ tục xóa

if ((*root)>left == NULL) (*root) = (*root)>right;

else

if ((*root)>right==NULL) (*root) = (*root)>left;

else (*root)>element = xoacuctrai(&(*root)>right);

}

ố

ị

4.3 Cây nh phân cân đ i (AVL)

ế

Đ nh nghĩa: Cây nh phân tìm ki m đ

ư ố ớ

ố ế

ề

ộ ơ

ỉ ệ

ượ ị ị ọ ọ g i là cân đ i n u nh đ i v i m i nút ươ ủ ủ c a nó chi u cao c a hai cây con t ng ị ứ ng ch l nh nhau m t đ n v .

ố

ị

4.3 Cây nh phân cân đ i (AVL)

ỗ

Khai báo: V i cây cân đ i AVL, t

i m i nút ta ghi thêm

ố

ạ ố ớ m t h s cân đ i bal

ộ ệ ố ế

bal = 1 n u cây con trái cao h n cây con

ph iả

ằ ơ

0 cao b ng 1

ấ th p h n

ố

ị

4.3 Cây nh phân cân đ i (AVL)

ấ

ẽ ư

C u trúc c a m t nút s nh sau: ộ ủ typedef int element_type; struct node { element_type element; struct node *left, *right; int bal[1,0,1] }

ố

ị

4.3 Cây nh phân cân đ i (AVL)

ị

ự

Các phép toán trên cây nh phân (sinh viên t

ứ nghiên c u thêm)

̀ Ba i tâp

Bài 1.Ve cây nhi phân ti m kiê m bă ng ́

ca ch thêm dâ n ca c kho a : 10, 7, 19, 11, 3, 16, 13, 4, 22, 1. ươ

ng tri nh th c hiên:

̀ Bài 2: Ca i đăt ch

̣ ̣

̀ ̀

́ ơ ̣ ̣ ̣

ự ́ ́

̀ ̣ ượ ́ ư ̣

́ ́ ̣ ̣ ̉

̀ ́ ̣ ̣ ̉ – Nhâp môt cây nhi phân ti m kiê m v i ca c ̀ ́ gia tri đ c nhâp va o ba n phi m nh trên, ́ ự th c hiên ca c phe p duyêt cây đê in ra ca c ́ gia tri trên. – Nhâp gia tri x t ́ ̀ ba n phi m, kiêm tra x co

́ ư trong cây không?

̀ Ba i tâp

ế ộ Bài 3: Vi t các th t c thêm, xoá m t nút có khoá

ằ ủ ụ ế

ị x trên cây tìm ki m nh phân b ng cách không ệ đ qui.

ị ạ ẽ Bài 4: a V hình cây tìm ki m nh phân t o ra t

ỗ

ố

ế ở ị i hình cây tìm ki m nh phân câu a/ sau b V l

ầ ượ t xen thêm các nút 15, 45, 55.

ế ở ị i hình cây tìm ki m nh phân câu a/ sau c V l

ầ ượ ừ ế ầ ượ ằ cây r ng b ng cách l n l t thêm vào các khoá là các s nguyên: 54, 31, 43, 29, 65, 10, 20, 36, 78, 59. ẽ ạ khi l n l ẽ ạ khi l n l t xoá các nút 10, 20, 43, 65, 54.