Cấu trúc dữ liệu và giải thuật
Đỗ Bích Diệp - Khoa CNTT-ĐHBK HN 1
Chương VII : Tìm kiếm
Tìm kiếm–PhầnI
z Nội dung
1. Tìm kiếmtuầntự và tìm kiếmnhị phân
2. Tìm kiếm trên cây nhị phân
1. Cây nhị phân tìm kiếm
1. Đặc điểmcủa cây nhị phân tìm kiếm
2. Thao tác bổ sung trên cây nhị phân tìm kiếm
3. Thao tác loạibỏ trên cây nhị phân tìm kiếm
2. Cây nhị phân tìm kiếmcânbằng (AVL)
1. Khôi phục tính cân bằng khi thựchiệnbổ sung và loạibỏ
Cấu trúc dữ liệu và giải thuật
Đỗ Bích Diệp - Khoa CNTT-ĐHBK HN 2
Bài toán Tìm kiếm
– Tìm kiếmlàthuật toán tìm 1 phầntử có giá trị cho trước
trong mộttập các phầntử
– Khóa tìm kiếm: Mộtbộ phậncủa các phầntử trong tậpmà
giá trị củanóđượcsử dụng để so sánh và tìm kiếm
23 78 45 8 32 56
23 78 45 8 32 56
78?
Tìm kiếmtuầntự
– Tìm kiếmtuầntự
z Các phầntử trong tập đầu vào không đượcsắpxếp
theo khóa tìm kiếm
z Mô tả
– Duyệt dãy (danh sách, hàng đợi , v…v ) chứa các phần
tử trong tập
– So sánh vớikhóacần tìm tới khi tìm thấykhóahoặc duyệt

z Nếu key < A[k] thì tìm trên nửa đầucủamảng đãcho
z Nếu key > A[k] thì tìm trên nửasaucủamảng đãcho
Tìm kiếmnhị phân
Function BINARY-SEARCH(A,l, r, key)
1. If (l> r) return -1;
2. m = (l+r) /2 ;
3. If (A[m] = key ) return m ;
4. Else if (A[m] > key) return BINARY-SEARCH(A, l, m-1, key);
5. Else return BINARY-SEARCH(A, m+1, r, key);
Cấu trúc dữ liệu và giải thuật
Đỗ Bích Diệp - Khoa CNTT-ĐHBK HN 5
Tìm kiếmnhị phân
Function BINARY-SEARCH(A,n,key)
1. l:=1 ; r := n ; { l, r lầnlượtlàbiếnchỉ số sử dụng để ghi nhậnchỉ số củaphầntử
đầuvàphầntử cuốicủamảng mà chúng ta đang tìm kiếmtrênđó}
2. while l <= r do begin
{Tìm chỉ số củaphầntử giữa} m:= (l+r) / 2;
if key < A[m] then r:= m-1;
else
if key > A[m] then l:= m+1
else return m;
end;
3. { Không tìm thấy } return -1;
Cây nhị phân tìm kiếm
Binary Search Tree (BST)
z Cây tìm kiếmnhị phân ứng với 1 dãy gồmn khóaa
1
, a
2
, …,

z Duyệt cây nhị phân tìm kiếm
z Tìm kiếmnútcógiátrị x
z Thêm mộtnútmớicógiátrị x
z Xóa một nút có giá trị x
Cấu trúc dữ liệu và giải thuật
Đỗ Bích Diệp - Khoa CNTT-ĐHBK HN 7
Tìm kiếm trên cây nhị phân tìm kiếm
– Cách thựchiện
z Nếucâyrỗng: không tìm thấy
z Nếu cây không rỗng:
– So sánh giá trị cần tìm kiếm
với các giá trị khóa tìm kiếm ở
nút gốc
z Nếu= Æ Tìm thấy
z Nếu< Æ Đixuống tìm
kiếm trong cây con trái
z Nếu> Æ Đixuống tìm
kiếm trong cây con phải
6
9
2
4
1
8
<
>
=
Tìm kiếm trên cây nhị phân tìm kiếm
z Giảithuật đệ qui
Algorithm BST-Recursive(T, key)

vớigiátrị lưu trong w)
Cấu trúc dữ liệu và giải thuật
Đỗ Bích Diệp - Khoa CNTT-ĐHBK HN 9
Bổ sung trên cây nhị phân tìm kiếm
6
92
41 8
<
>
Bổ sung nút có giá trị 5
6
92
41 8
5
w
Bổ sung trên cây nhị phân tìm kiếm
Algorithm Insert_BST_Recursive(T, x)
{Tìm hoặcbổ sung nút có giá trị x trên cây nhị phân tìm kiếm.
Trả ra cây sau khi bổ sung hoặctrả ra nút có chứax }
1. If (T = null) then
1. Call New (p) ; {Xin bộ nhớ cho nút mới}
2. INFO(p) := x; LPTR(p): = RPTR(p) := NULL;
3. T = p ;
2. If ( key < INFO(T) ) then
1. LPRT(T) := Insert_BST(LPTR(T), x) ;
3. Else if ( key > INFO(T) ) then begin
1. RPTR(T) := Insert_BST(RPTR(T), x) ;
4. return T;
Cấu trúc dữ liệu và giải thuật
Đỗ Bích Diệp - Khoa CNTT-ĐHBK HN 10

– Nút loạibỏ là nút lá: Xóa ngay lậptức
– Nút loạibỏ là nút nhánh và chỉ có một cây con (trái hoặc
phải) : Thay nút cầnxóabằng nút con
– Nút loạibỏ là nút nhánh và có 2 cây con: Thay nút cần
xóa bằng nút cựcphảicủa cây con trái hoặc nút cựctrái
của cây con phải
Xóa một nút lá trên cây
– Trường hợp nút cần xóa là nút lá
z Xóa nút này
z Gán liên kếttừ cha củanótrở thành NULL
T
2
T
3
T
4
T
1
T
2
T
3
T
4
T
1
NULL
Nút cầnxóa
Cấu trúc dữ liệu và giải thuật
Đỗ Bích Diệp - Khoa CNTT-ĐHBK HN 12

5
T
1
Nút cầnxóa
T
2
Nút thay thế
Cấu trúc dữ liệu và giải thuật
Đỗ Bích Diệp - Khoa CNTT-ĐHBK HN 13
Xóa nút nhánh có đầy đủ 2 con
– Trường hợp nút cần xóa là nút có 2 con
z Bước 2: Có nút thay thế là y
– Gỡ y ra khỏicây
– Gắn con trái của y vào cha củay
T
3
T
4
T
5
T
1
Nút cầnxóa
T
2
y
Xóa nút nhánh có đầy đủ 2 con
– Trường hợp nút cần xóa là nút có 2 con
z Bước 3: Có nút thay thế là y
– Gắny vàovị trí của nút cầnxóa

end;{Kết thúc vòng lặp nut_thay trỏđến nút cựcphảicủa cây con trái, T:nút cha
củanútthay}
RPTR(nut_thay) := RPTR(nut_xoa); RPTR(T) := LPTR(nut_thay);
LPTR(nut_thay) := LPTR(nut_xoa);
if (key < INFO(nut_cha)) then LPTR(nut_cha) := nut_thay;
else RPTR(nut_cha) := nut_thay;
call dispose(nut_xoa);
End.
Cấu trúc dữ liệu và giải thuật
Đỗ Bích Diệp - Khoa CNTT-ĐHBK HN 15
Cây nhị phân tìm kiếm
z Đánh giá giảithuật : tìm kiếmvàloạibỏ
– Thờigianthựchiện trung bình T
tb
(n) = O(log
2
n)
z Nhược điểmcủacâytìmkiếmnhị phân:
– Cây suy biếncóthểđược hình thành trong quá trình
bổ sung, ảnh hưởng đếnhiệunăng củaviệcsử
dụng cây nhị phân trong tìm kiếm
Cây nhị phân cân đốiAVL
z Cây nhị phân cân đối AVL (AVL balanced binary search
tree)
– Mộtcâynhị phân tìm kiếm đượcgọilàcâycânđối AVL nếu
vớimọi nút trên cây, chiềucaocủa 2 cây con tương ứng chỉ
chênh nhau nhiềunhấtlà1 đơnvị
33
29
64

2219
25
Bổ sung 25
27
20
18 22
44
35 52
251912
Khôi phụccânbằng
Cây nhị phân cân đốiAVL
– Khôi phụctínhcânbằng củacây
z Kiểm tra tính cân bằng của các nút nằmtrênđường đi
từ nút gốc đến nút mới đượcbổ sung
z Xác định nút vi phạmgầnnhấtvới nút mới
z Thựchiện các phép quay với nút vi phạm mà không cần
thựchiện phép quay nào khác tạitổ tiên của nút đó
– Tùy vào vị trí nút mớiso với nút vi phạmcó4 loạiphép
quay khác nhau
Cấu trúc dữ liệu và giải thuật
Đỗ Bích Diệp - Khoa CNTT-ĐHBK HN 17
Cây nhị phân cân đốiAVL
z Xác định các phép quay cầnsử dụng
– Bước1: Xácđịnh nút vi phạmgầnnhất
– Bước 2: Quan sát vị trí của nút con và nút cháu của nút vi
phạmtrênđường đixácđịnh vị trí bổ sung
z Trường hợp 1: Quay đơnphải
Nút vi phạm
(nút bấtthường)
Nút con

Nút vi
phạm
T
1
T
2
T
3
T
4
B
C
A
h
h-1
h-1 or h-2
h+1
Sau khi quay đơnphải
AVL trở lại
trạng thái
cân bằng
Cấu trúc dữ liệu và giải thuật
Đỗ Bích Diệp - Khoa CNTT-ĐHBK HN 19
Cây nhị phân cân đốiAVL
– Trường hợp 3: Phép quay kép phải
T
1
T′
2
T

B
A
h
h-1
h-1 or h-2
h
T"
2
C
Cây nhị phân cân đốiAVL
– Bổ sung trên cây AVL – Ví dụ: Bổ sung 30 vào cây s
8
3 14
1 6
4
10
19
17
24
30
Nút
vi phạm
Không vi
phạm
Không vi
phạm
Không vi
phạm
Cấu trúc dữ liệu và giải thuật
Đỗ Bích Diệp - Khoa CNTT-ĐHBK HN 20

phạm
Không vi
phạm
Cấu trúc dữ liệu và giải thuật
Đỗ Bích Diệp - Khoa CNTT-ĐHBK HN 21
Cây nhị phân cân đốiAVL
z Loạibỏ trên cây AVL cũng có thể dẫn đến tình trạng mất
cân đốicủacây, tương tự như trong phép bổ sung, ta
cũng sẽ thựchiện phép quay để tái cân bằng lạicây.
z Ví dụ: Loạibỏ một nút lá không làm ảnh hưởng đến
tình trạng cân bằng củacây
20
15 22
14
25
18
17 19
Loạibỏ
Cây nhị phân cân đốiAVL
z Ví dụ: Loạibỏ một nút nhánh không làm ảnh hưởng
đến tính cân bằng củacây
20
15 22
14
25
18
17 19
Loạibỏ
Cấu trúc dữ liệu và giải thuật
Đỗ Bích Diệp - Khoa CNTT-ĐHBK HN 22

Đỗ Bích Diệp - Khoa CNTT-ĐHBK HN 23
Cây nhị phân cân đốiAVL
44
17
7850
88
48
62
54
Nút cần xóa
x
y
z
44
17
78
50 88
48
62
54