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
