11) Trình bày giải thuật tìm kiếm nhị phân. Trình bày thời gian thực hiện giải thuật với cây có n nút.

Bài làm:

Function Binary_Search (k,r,a,X);

If k>r then

tg := 0 then //Không tìm thấy

Else

Begin

m := (k + r) div 2;

If a[m] = X then

tg := X; //Tìm thấy

Else

If X < a[m] then

Binary_Search (k, m – 1, a, X);

Else

Binary_Search (m+1, r, a, X);

End;

Return tg;

Thời gian thực hiện:

Thuận lợi nhất khi tìm thấy ngay ở giữa: O(1)

Không thuận lợi khi phải gọi đệ qui, gọi thời gian cần thực hiện trong trường hợp này là:

W(r – k + 1)

Với lần gọi ban đầu: k = 1, r = n

Có W(n – 1 + 1) = W(n) = 1 + W(n/2)

= 1 + 1 + W(n/4)… = 1 + 1 + … + W(n/2x)

Dừng khi (n/2x) = 1 vì W(1) = 1

Mà (n/2x) = 1 ó x = log2n

Tức là ta phải gọi đệ qui log2n lần

=> Độ phức tạp là O(log2n)

12) Trình bày giải thuật tìm kiếm có bổ sung trên cây nhị phân tìm kiếm. Dựng cây nhị phân tìm kiếm với dãy khóa nhập vào là: 10, 7, 19, 11, 3, 16, 13, 4, 22, 5.

Bài làm:

Function BST(T,X);

P := null; q = T;

While q <> null do

Case

X <Key(q): p := q; //Lưu cha của q

                  q := P_Trai(q);

X = Key(q) : Return(q);

X > Key(q) : p := q;

                    q := P_Phai(q);

End Case; //Không tìm thấy, cần bổ sung

New(q);

Key(q) := X;

P_Trai(q) := null;

P_Phai(q) := null;

Case

T = null : T := q;

X < Key(P) : P_Trai(P) := q;

X > Key(P) : P_Phai(P) := q;

End Case;

Write(“Khong tim thay, da bo sung”);

Return (q);

Dựng cây nhị phân:

10: Gốc

7: Con trái của 10, 19: Con phải của 10

3: Con trái của 7, 11: Con trái của 19, 22: Con phải của 19

4: Con phải của 3, 16: Con phải của 11

5: Con phải của 4, 13: Con trái của 16