Chương VII : Tìm kiếm | Cấu trúc dữ liệu và giải thuật | Đại học Bách Khoa, Đại học Đà Nẵng

Chương VII : Tìm kiếm | Cấu trúc dữ liệu và giải thuật | Đại học Bách Khoa, Đại học Đà Nẵng giúp sinh viên tham khảo, ôn luyện và phục vụ nhu cầu học tập của mình cụ thể là có định hướng, ôn tập, nắm vững kiến thức môn học và làm bài tốt trong những bài kiểm tra, bài tiểu luận, bài tập kết thúc học phần, từ đó học tập tốt và có kết quả cao cũng như có thể vận dụng tốt những kiến thức mình đã học

 

Thông tin:
23 trang 7 tháng trước

Bình luận

Vui lòng đăng nhập hoặc đăng ký để gửi bình luận.

Chương VII : Tìm kiếm | Cấu trúc dữ liệu và giải thuật | Đại học Bách Khoa, Đại học Đà Nẵng

Chương VII : Tìm kiếm | Cấu trúc dữ liệu và giải thuật | Đại học Bách Khoa, Đại học Đà Nẵng giúp sinh viên tham khảo, ôn luyện và phục vụ nhu cầu học tập của mình cụ thể là có định hướng, ôn tập, nắm vững kiến thức môn học và làm bài tốt trong những bài kiểm tra, bài tiểu luận, bài tập kết thúc học phần, từ đó học tập tốt và có kết quả cao cũng như có thể vận dụng tốt những kiến thức mình đã học

 

64 32 lượt tải Tải xuống
Cu trúc d liu và gii thut
Đỗ Bích Dip - Khoa CNTT-ĐHBK HN 1
Chương VII : Tìm kiếm
Tìm kiếm Phn I
z Ni dung
1. Tìm kiếm tun t tìm kiếm nh 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 m ca 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 loi b trên cây nh phân tìm kiếm
2. Cây nh phân tìm kiếm cân bng (AVL)
1. Khôi phc tính cân bng khi thc hin b sung và loi b
Cu trúc d liu và gii thut
Đỗ Bích Dip - Khoa CNTT-ĐHBK HN 2
Bài toán Tìm ki mế
Tìm kiếm thut toán tìm 1 phn t giá tr cho trước
trong mt t p các ph n t
Khóa tìm kiếm: Mt b phn c a các ph n t trong tp
giá tr ca được s dng để so sánh tìm kiếm
23 78 45 8 32 56
23 78 45 8 32 56
78?
Tìm kiếm tun t
Tìm kiếm tun t
z Các phn t trong tp đầ đượu vào không c sp xếp
theo khóa tìm kiếm
z t
Duyt dãy (danh sách, hàng đợi , v…v ) cha các phn
t trong tp
So sánh vi khóa c n tìm t i khi tìm thy khóa ho c duy t
qua hết m ưng ch a tìm thy
Tr li ch s phn t trong dãy (nếu thy)
Cu trúc d liu và gii thut
Đỗ Bích Dip - Khoa CNTT-ĐHBK HN 3
Tìm kiếm tun t
Function SEQUENTIAL(A, n, key)
{tìm phn t khóa key trong mng A gm n phn t. Kết qu
tr ra: -1 nếu không tìm thy phn t khóa key, ch s ca
phn t nếu tìm thy}
1. i:= 1;
2. while (i <= n ) and (A[i] <> key) do
i:= i + 1;
3. if (i> n) then return -1 { không thy};
4. else
return i{tìm thy ti v trí i}
Tìm kiếm tun t
Độ phc tp :
z Trường hp tt nht: O(1)
z Trường hp ti nht: O(n)
z Trường hp trung bình : O(n)
Cu trúc d liu và gii thut
Đỗ Bích Dip - Khoa CNTT-ĐHBK HN 4
Tìm kiếm nh phân
z Tìm kiếm nh phân
S d ng cho vic tìm kiếm trên m đng ã được sp xếp
t
z Chn phn t gi a” dãy A[k] để th c hin so
sánh vi giá tr cn tìm
z Nếu key = A[k] thì tìm thy , kết thúc
z Nếu key < A[k] thì tìm trên na đầu ca mng đã cho
z Nếu key > A[k] thì tìm trên na sau ca m đng ã cho
Tìm kiếm nh 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);
Cu trúc d liu và gii thut
Đỗ Bích Dip - Khoa CNTT-ĐHBK HN 5
Tìm kiếm nh phân
Function BINARY-SEARCH(A,n,key)
1. l:=1 ; r := n ; { l, r ln lượt biến ch s s dng để ghi nhn ch s ca phn t
đầu phn t cui ca m ếng chúng ta đang tìm ki m trên đó}
2. while l <= r do begin
{Tìm ch s ca phn t gia} 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 thy } return -1;
Cây nh phân tìm kiếm
Binary Search Tree (BST)
z Cây tìm kiếm nh phân ng vi 1 dãy gm n khóa a
1 2
, a , …,
a
n
mt cây nh phân tha mãn tính cht sau
Mi giá tr thuc cây con trái ca mt nút đều nh hơn giá tr ti
nút đó
Mi giá tr thuc cây con phi ca mt nút đều ln hơn giá tr
ti nút đó
Mi cây con ca m ũt nút c ng đều cây nh phân tìm kiếm
z Vi mt tp khóa th xác đị đượnh c nhiu cây nh phân
tìm kiếm
Cu trúc d liu và gii thut
Đỗ Bích Dip - Khoa CNTT-ĐHBK HN 6
Cây nh phân tìm kiếm
33
29
64
19 4030
23 65
70
80
64
30
70
23 33 65
29
80
40
19
Cây nh phân tìm kiếm
Các thao tác trên cây nh phân tìm kiếm
z Duyt cây nh phân tìm kiếm
z Tìm kiếm nút giá tr x
z Thêm mt nút mi giá tr x
z Xóa mt nút giá tr x
Cu trúc d liu và gii thut
Đỗ Bích Dip - Khoa CNTT-ĐHBK HN 7
Tìm kiếm trên cây nh phân tìm kiếm
Cách thc hin
z Nếu cây rng: không tìm thy
z Nếu cây không rng:
So sánh giá tr c mn tìm kiế
vi các giá tr khóa tìm kiếm
nút gc
z Nếu = Æ Tìm thy
z Nếu < Æ Đi xung tìm
kiếm trong cây con trái
z Nếu > Æ Đi xung tìm
ki iếm trong cây con ph
6
92
4
1
8
<
>
=
Tìm kiếm trên cây nh phân tìm kiếm
z Gii thut đệ qui
Algorithm BST-Recursive(T, key)
{T là con tr tr ti gc c a cây; key là giá tr cn tìm, tr ra con tr tr t i nút
cha giá tr cn tìm }
1. If ( T = NULL) then return NULL;
2. If ( key < INFO(T) ) return BST-Recursive(LPTR(T), key);
3. Else if (key > INFO(T)) return BST-Recursive(RPTR(T), key);
4. Else return T;
Cu trúc d liu và gii thut
Đỗ Bích Dip - Khoa CNTT-ĐHBK HN 8
Tìm kiếm trên cây nh phân tìm kiếm
Algorithm BST(T, key)
1. q= T ; {Khi to biến con tr để duyt cây}
2. while q < > NULL do begin
if (INFO(q) = key then return q;
else begin
if (INFO(q) < key) then q = RPTR(q);
else q = LPTR(q);
end.
end.
3. Return NULL;
Gii thut không đệ qui
B sung trên cây nh phân tìm kiếm
Cách thc hin thêm mt nút giá tr x vào cây
nh phân tìm kiếm
z Tìm nút giá tr x
z Nếu tìm th y, không c n thêm
z Nếu không tìm thy
Gi s g i w là nút ta chm đến trong quá trình tìm
ki mế
To m t nút m i giá tr x và biến nút này thành nút con
ca w (con trái hay con phi ph thuc vào vic so sánh x
vi giá tr lưu trong w)
Cu trúc d liu và gii thut
Đỗ Bích Dip - Khoa CNTT-ĐHBK HN 9
B sung trên cây nh phân tìm kiếm
6
92
41 8
<
>
B 5 sung nút giá tr
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 hoc b sung nút giá tr x trên cây nh phân tìm kiếm.
Tr ra cây sau khi b sung hoc tr ra nút cha x }
1. If (T = null) then
1. Call New (p) ; {Xin b nh cho nút mi}
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;
Cu trúc d liu và gii thut
Đỗ Bích Dip - Khoa CNTT-ĐHBK HN 10
B sung trên cây nh phân tìm kiếm
Algorithm Insert_BST(T, x)
{B sung nút mi giá tr x vào cây, tr ra con tr tr ti nút mi, hoc tr ra con
tr tr ti m đ t nút trong cây nếu trong cây ã nút ch a khóa x }
1. q= T ; {Khi to biến con tr để duyt cây}
2. while q < > NULL do begin
if (INFO(q) = key) then return q; // Tìm thy, kết thúc gii thut
else begin
if (INFO(q) < key) then begin p= q; q = RPTR(q); end;
else begin p=q; q = LPTR(q);end;
end.
end.
3. Call New(q); INFO(q) = x; LPTR(q) = RPTR(q) = NULL;
if (T= null ) then T = q;
else if x < INFO(p) then LPTR(p) = q;
else RPTR(p) = q;
Dng cây nh phân tìm kiếm
d: Dng cây nh phân tìm kiếm s dng phép b sung
cho trên vi dãy s {8,3,14,6, 12, 28, 10,21,5}
8
T
3 14
6
12
28
10 215
Cu trúc d liu và gii thut
Đỗ Bích Dip - Khoa CNTT-ĐHBK HN 11
Xóa nút trên cây nh phân tìm kiếm
z Các trường hp :
Nút loi b nút lá: Xóa ngay lp tc
Nút loi b nút nhánh ch m ct cây con (trái ho
phi) : Thay nút cn xóa bng nút con
Nút loi b nút nhánh 2 cây con: Thay nút cn
xóa bng nút cc phi c a cây con trái ho c nút c c trái
c ia cây con ph
Xóa mt nút trên cây
Trường h p nút c n xóa nút
z Xóa nút này
z Gán liên kết t cha ca tr thành NULL
T
2
T
3
T
4
T
1
T
2
T
3
T
4
T
1
NULL
Nút cn xóa
Cu trúc d liu và gii thut
Đỗ Bích Dip - Khoa CNTT-ĐHBK HN 12
Xóa nút nhánh 1 con
Trường h p nút c n xóa nút nhánh 1 con
z Gn cây con ca nút cn xóa vào cha
T
2
T
3
T
4
T
1
T
2
T
3
T
4
T
1
Nút cn xóa
Xóa nút nhánh đầy đủ 2 con
Trường h p nút c n xóa nút 2 con
z Bước 1: Xác định nút thay thế
z Nút thay thế nút cc phi c a cây con trái ho c
nút cc trái ca cây con phi
T
3
T
4
T
5
T
1
Nút cn xóa
T
2
Nút thay thế
Cu trúc d liu và gii thut
Đỗ Bích Dip - Khoa CNTT-ĐHBK HN 13
Xóa nút nhánh đầy đủ 2 con
Trường h p nút c n xóa nút 2 con
z Bước 2: Có nút thay thế là y
G y ra khi cây
Gn con trái ca y vào cha ca y
T
3
T
4
T
5
T
1
Nút cn xóa
T
2
y
Xóa nút nhánh đầy đủ 2 con
Trường h p nút c n xóa nút 2 con
z Bước 3: Có nút thay thế là y
Gn y vào v trí c a nút c n xóa
T
3
T
4
T
5
T
1
T
2
Cu trúc d liu và gii thut
Đỗ Bích Dip - Khoa CNTT-ĐHBK HN 14
Xóa nút trên cây nh phân tìm kiếm
Algorithm BSTDEL(key, nut_xoa, nut_cha)
{Thc hin vi ếc xóa nút tr bi con tr nut_xoa , bi t con tr nut_cha tr ti nút cha
ca nút xóa, biết giá tr key ca nút cn xóa}
1. If (LPTR(nut_xoa) = null && RPTR(nut_xoa) = null) then begin
if ( key < INFO(nut_cha)) then LPTR(nut_cha): = null;
else RPTR(nut_cha) := null; call dispose(nut_xoa) ; end;
2. If (LPTR(nut_xoa) = null || RPTR(nut_xoa) = null) then begin
if LPTR(nut_xoa) = NULL then nut_thay := RPTR(P);
else if RPTR(nut_xoa) = NULL then nut_thay := LPTR(P);
if (key < INFO(nut_cha)) then LPTR(nut_cha) := nut_thay;
else RPTR(nut_cha) := nut_thay;
call dispose(nut_xoa); end;
Xóa nút trên cây nh phân tìm kiếm
3. If (LPTR(nut_xoa) != null && RPTR(nut_xoa) != null) then begin
nut_thay := LPTR(nut_xoa); {sang cây con trái}
while RPTR(nut_thay) <> null do begin
T := nut_thay; nut_thay := RPTR(nut_thay);
end;{Kết thúc vòng lp nut_thay tr đến nút cc phi ca cây con trái, T:nút cha
ca nút thay}
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.
Cu trúc d liu và gii thut
Đỗ Bích Dip - Khoa CNTT-ĐHBK HN 15
Cây nh phân tìm kiếm
z Đ ánh giá gi i thu ết : tìm ki m loi b
Thi gian thc hin trung bình T
tb
(n) = O(log
2
n)
z Nhược đim ca cây tìm kiếm nh phân:
Cây suy biến th được hình thành trong quá trình
b sung, nh hưởng đến hiu năng ca vic s
dng cây nh phân trong tìm kiếm
Cây nh phân cân đối AVL
z Cây nh phân cân đối AVL (AVL balanced binary search
tree)
Mt cây nh phân tìm kiếm được gi cây cân đối AVL nếu
vi m i nút trên cây, chi u cao c a 2 cây con tương ng ch
chênh nhau nhiu nht 1 đơn v
33
29
64
19 30 40
23 65
70
80
Cây nh phân tìm kiếm cân đối AVL
33
29
64
19 30
23 65
70
80
Cây nh phân tìm kiếm không cân đối
Cu trúc d liu và gii thut
Đỗ Bích Dip - Khoa CNTT-ĐHBK HN 16
Cây nh phân cân đối AVL
z B sung trên cây AVL
B sung theo nguyên tc gi ếng v i cây nh phân tìm ki m
Vic b sung có th làm vi ph m tính n bng c a cây
27
18
12 20
44
35 52
2219
27
18
12 20
44
35 52
2219
25
B
sung 25
27
20
18 22
44
35 52
251912
Khôi phc cân bng
Cây nh phân cân đối AVL
Khôi phc tính cân b ng c a cây
z Kim tra tính cân bng ca các nút nm trên đường đi
t nút gc đến nút mi được b sung
z Xác định nút vi phm gn nht v i nút m i
z Thc hi n các phép quay vi nút vi phm không c n
thc hi n phép quay nào khác t i t tiên c đa nút ó
Tùy vào v trí nút mi so v i nút vi ph m 4 loi phép
quay khác nhau
Cu trúc d liu và gii thut
Đỗ Bích Dip - Khoa CNTT-ĐHBK HN 17
Cây nh phân cân đối AVL
z Xác định các phép quay cn s dng
Bước 1: Xác định nút vi phm gn nht
Bước 2: Quan sát v trí ca nút con và nút cháu ca nút vi
phm trên đường đi xác định v trí b sung
z Trường hp 1: Quay đơn phi
Nút vi phm
(nút bt thường)
Nút con
Nút cháu
Cây nh phân cân đối AVL
z Trường hp 2: Quay đơn trái (single left rotation)
z Trường hp 3: Quay kép phi (double right rotation) :
quay trái vi cây con trái ri quay phi vi cây nút
vi phm con trái ca
Cu trúc d liu và gii thut
Đỗ Bích Dip - Khoa CNTT-ĐHBK HN 18
Cây nh phân cân đối AVL
z Trường hp 4: Quay kép trái (double left rotation) :
quay phi v i cây con phi, r i quay trái v i cây có
nút vi phm con phi ca
Cây nh phân cân đối AVL
Trường hp 1: Phép quay đơn phi
T
1
T
2
T
3
T
4
A
B
C
h
h-1
h-1 or h-2
h+1
Trước khi quay
Nút vi
phm
T
1
T
2
T
3
T
4
B
C
A
h
h-1 h-1 or h-2
h+1
Sau khi quay đơn phi
AVL tr li
trng thái
cân bng
Cu trúc d liu và gii thut
Đỗ Bích Dip - Khoa CNTT-ĐHBK HN 19
Cây nh phân cân đối AVL
Trường hp 3: Phép quay kép phi
T
1
T
2
T
3
T
4
A
B
C
h
h-1
h-1 or h-2
h
Tr
ước khi quay
Nút vi
phm
D
T"
2
Sau khi quay kép
phi
AVL tr l i
trng thái
cân bng
T
1
T
2
T
3
T
4
D
B
A
h
h-1
h-1 or h-2
h
T"
2
C
Cây nh phân cân đối AVL
B sung trên cây AVL – d: B sung 30 vào cây s
8
3 14
1 6
4
10
19
17
24
30
Nút
vi phm
Không vi
phm
Không vi
phm
Không vi
phm
Cu trúc d liu và gii thut
Đỗ Bích Dip - Khoa CNTT-ĐHBK HN 20
Cây nh phân cân đối AVL
Để sa đổi li cây, quay cây gc ti 14: Quay t phi
sang trái vi cây con phi (nút 14 và 19) – Phép quay này
gi phép quay đơn trái
8
3 19
1 6
4
14
24
17
30
10
Cây nh phân cân đối AVL
B sung trên cây AVL – d
Bổ sung 18 vào cây
8
3 14
1 6
4
10
19
17
24
18
Nút vi
phm
Không vi
phm
Không vi
phm
Không vi
phm
Cu trúc d liu và gii thut
Đỗ Bích Dip - Khoa CNTT-ĐHBK HN 21
Cây nh phân cân đối AVL
z Loi b trên cây AVL cũng th dn đến tình tr ng m t
cân đối ca cây, tương t như trong phép b sung, ta
cũng s thc hi n phép quay để tái cân b ng l i cây.
z d: Loi b m t nút không làm nh hưởng đến
tình trng cân bng ca cây
20
15 22
14
25
18
17 19
Loi b
Cây nh phân cân đối AVL
z d: Loi b m t nút nhánh không làm nh h ngưở
đến tính cân bng ca cây
20
15 22
14
25
18
17 19
Loi b
Cu trúc d liu và gii thut
Đỗ Bích Dip - Khoa CNTT-ĐHBK HN 22
Cây nh phân cân đối AVL
z d: Loi b m t nút d n đến phi thc hin phép
quay để tái cân bng cây
20
15
22
14
25
18
17 19
Loi b
Nút vi
phm
18
20
15
14 2517 19
Cây nh phân cân đối AVL
z Tái cân bng li cây sau khi loi b trên cây AVL
Gi z là nút đầu tiên không cân bng trên đường đi t v trí
ca nút b loi lên đến gc cây.
Gi y là nút con ca z, y nút con có chiu cao ln hơn
Gi x là nút con ca y, x nút con có chiu cao ln hơn
Ta s thc hin phép quay ti nút z khi xét thêm c y, x để
tái cân bng li cây
Phép quay có th nh hưởng đến tính cân bng ca c nút
chiu cao ln hơn z trong cây (các nút t tiên ca z trên
đường đi đến g c) vì v y cn phi ki m tra tính cân b ng
ca các nút đó cho đến khi chm ti gc.
Cu trúc d liu và gii thut
Đỗ Bích Dip - Khoa CNTT-ĐHBK HN 23
Cây nh phân cân đối AVL
44
17
7850
8848
62
54
Nút cn xóa
x
y
z
44
17
78
50 88
48
62
54
| 1/23

Preview text:

Cấu trúc dữ liệu và giải thuật
Chương VII : Tìm kiếm
Tìm kiếm – Phần I z Nội dung 1.
Tìm kiếm tuần tự và tìm kiếm nhị 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ểm củ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ại bỏ trên cây nhị phân tìm kiếm 2.
Cây nhị phân tìm kiếm cân bằng (AVL) 1.
Khôi phục tính cân bằng khi thực hiện bổ sung và loại bỏ
Đỗ Bích Diệp - Khoa CNTT-ĐHBK HN 1
Cấu trúc dữ liệu và giải thuật Bài toán Tìm kiếm
Tìm kiếm là thuật toán tìm 1 phần tử có giá trị cho trước
trong một tập các phần tử 23 78 45 8 32 56 78? 23 78 45 8 32 56 –
Khóa tìm kiếm: Một bộ phận của các p ầ h n tử trong tập mà
giá trị của nó được sử dụng để so sánh và tìm kiếm Tìm kiếm tuần tự – Tìm kiếm tuần tự
z Các phần tử trong tập đầu vào không được sắp xế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ới khóa cần tìm tới khi tìm thấy khóa hoặc duyệt
qua hết mảng mà chưa tìm thấy
– Trả lại chỉ số phần tử trong dãy (nếu thấy)
Đỗ Bích Diệp - Khoa CNTT-ĐHBK HN 2
Cấu trúc dữ liệu và giải thuật Tìm kiếm tuần tự
Function SEQUENTIAL(A, n, key) ≠
{tìm phần tử có khóa key trong mảng A gồm n phần tử. Kết quả
trả ra: -1 nếu không tìm thấy phần tử có khóa key, chỉ số của phần tử nếu tìm thấy} 1. i:= 1;
2. while (i <= n ) and (A[i] <> key) do i:= i + 1;
3. if (i> n) then return -1 { không thấy}; 4. else
return i{tìm thấy tại vị trí i} Tìm kiếm tuần tự – Độ phức tạp :
z Trường hợp tốt nhất: O(1)
z Trường hợp tồi nhất: O(n)
z Trường hợp trung bình : O(n)
Đỗ Bích Diệp - Khoa CNTT-ĐHBK HN 3
Cấu trúc dữ liệu và giải thuật Tìm kiếm nhị phân z Tìm kiếm nhị phân
– Sử dụng cho việc tìm kiếm trên mảng đã được sắp xếp – Mô tả
z Chọn phần tử “ở giữa” dãy – A[k] để thực hiện so
sánh với giá trị cần tìm
z Nếu key = A[k] thì tìm thấy , kết thúc
z Nếu key < A[k] thì tìm trên nửa đầu của mảng đã cho
z Nếu key > A[k] thì tìm trên nửa sau của mảng đã cho Tìm kiếm nhị 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);
Đỗ Bích Diệp - Khoa CNTT-ĐHBK HN 4
Cấu trúc dữ liệu và giải thuật Tìm kiếm nhị phân
Function BINARY-SEARCH(A,n,key)
1. l:=1 ; r := n ; { l, r lần lượt là biến chỉ số sử dụng để ghi nhận chỉ số của phần tử
đầu và phần tử cuối của mảng mà chúng ta đang tìm kiếm trên đó} 2. while l <= r do begin
{Tìm chỉ số của phần tử 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ếm nhị phân ứng với 1 dãy gồm n khóa a , a , …, 1 2
a là một cây nhị phân thỏa mãn tính chất sau n
– Mọi giá trị thuộc cây con trái của một nút đều nhỏ hơn giá trị tại nút đó
– Mọi giá trị thuộc cây con phải của một nút đều lớn hơn giá trị tại nút đó
– Mỗi cây con của một nút ũ
c ng đều là cây nhị phân tìm kiếm
z Với một tập khóa có thể xác định được nhiều cây nhị phân tìm kiếm
Đỗ Bích Diệp - Khoa CNTT-ĐHBK HN 5
Cấu trúc dữ liệu và giải thuật
Cây nhị phân tìm kiếm 33 64 29 64 30 70 19 30 40 70 23 33 65 80 23 65 80 29 40 19
Cây nhị phân tìm kiếm
– Các thao tác trên cây nhị phân tìm kiếm
z Duyệt cây nhị phân tìm kiếm
z Tìm kiếm nút có giá trị x
z Thêm một nút mới có giá trị x
z Xóa một nút có giá trị x
Đỗ Bích Diệp - Khoa CNTT-ĐHBK HN 6
Cấu trúc dữ liệu và giải thuật
Tìm kiếm trên cây nhị phân tìm kiếm – Cách thực hiện
z Nếu cây rỗ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 6 <
z Nếu < Æ Đi xuống tìm kiếm trong cây con trái 2 9 >
z Nếu > Æ Đi xuống tìm 1 4 8 = kiếm trong cây con phải
Tìm kiếm trên cây nhị phân tìm kiếm z Giải thuật đệ qui
Algorithm BST-Recursive(T, key)
{T là con trỏ trỏ tới gốc của cây; key là giá trị cần tìm, trả ra con trỏ trỏ tới nút
chứa giá trị cần tìm }
1. If ( T = NULL) then return NULL;
2. If ( key < INFO(T) ) return BST-Recursive(LPTR(T), key);
3. Else if (key > INFO(T)) return BST-Recursive(RPTR(T), key); 4. Else return T;
Đỗ Bích Diệp - Khoa CNTT-ĐHBK HN 7
Cấu trúc dữ liệu và giải thuật
Tìm kiếm trên cây nhị phân tìm kiếm
Giải thuật không đệ qui Algorithm BST(T, key)
1. q= T ; {Khởi tạo biến con trỏ để duyệt cây}
2. while q < > NULL do begin
if (INFO(q) = key then return q; else begin
if (INFO(q) < key) then q = RPTR(q); else q = LPTR(q); end. end. 3. Return NULL;
Bổ sung trên cây nhị phân tìm kiếm
– Cách thực hiện thêm một nút có giá trị x vào cây nhị phân tìm kiếm z Tìm nút có giá trị x
z Nếu tìm thấy, không ầ c n thêm z Nếu không tìm thấy
– Giả sử gọi w là nút lá mà ta chạm đến trong quá trình tìm kiếm – Tạo một nút ớ
m i có giá trị x và biến nút này thành nút con
của w (con trái hay con phải phụ thuộc vào việc so sánh x với giá trị lưu trong w)
Đỗ Bích Diệp - Khoa CNTT-ĐHBK HN 8
Cấu trúc dữ liệu và giải thuật
Bổ sung trên cây nhị phân tìm kiếm
Bổ sung nút có giá trị 5 6 < 6 2 9 > 2 9 w 1 4 8 1 4 8 5
Bổ sung trên cây nhị phân tìm kiếm
Algorithm Insert_BST_Recursive(T, x)
{Tìm hoặc bổ 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ặc trả ra nút có chứa x } 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;
Đỗ Bích Diệp - Khoa CNTT-ĐHBK HN 9
Cấu trúc dữ liệu và giải thuật
Bổ sung trên cây nhị phân tìm kiếm
Algorithm Insert_BST(T, x)
{Bổ sung nút mới có giá trị x vào cây, trả ra con trỏ trỏ tới nút mới, hoặc trả ra con
trỏ trỏ tới một nút trong cây nếu trong cây đã có nút chứa khóa x }
1. q= T ; {Khởi tạo biến con trỏ để duyệt cây}
2. while q < > NULL do begin
if (INFO(q) = key) then return q; // Tìm thấy, kết thúc giải thuật else begin
if (INFO(q) < key) then begin p= q; q = RPTR(q); end;
else begin p=q; q = LPTR(q);end; end. end.
3. Call New(q); INFO(q) = x; LPTR(q) = RPTR(q) = NULL; if (T= null ) then T = q;
else if x < INFO(p) then LPTR(p) = q; else RPTR(p) = q;
Dựng cây nhị phân tìm kiếm
– Ví dụ: Dựng cây nhị phân tìm kiếm sử dụng phép bổ sung
cho ở trên với dãy số {8,3,14,6, 12, 28, 10,21,5} T 8 3 14 6 12 28 5 10 21
Đỗ Bích Diệp - Khoa CNTT-ĐHBK HN 10
Cấu trúc dữ liệu và giải thuật
Xóa nút trên cây nhị phân tìm kiếm z Các trường hợp :
– Nút loại bỏ là nút lá: Xóa ngay lập tức
– Nút loại bỏ là nút nhánh và chỉ có một cây con (trái hoặc
phải) : Thay nút cần xóa bằng nút con
– Nút loại bỏ là nút nhánh và có 2 cây con: Thay nút cần
xóa bằng nút cực phải của cây con trái h ặ o c nút ự c c trá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ết từ cha của nó trở thành NULL NULL T T3 T T 2 4 T 3 T 2 4 T1 T1 Nút cần xóa
Đỗ Bích Diệp - Khoa CNTT-ĐHBK HN 11
Cấu trúc dữ liệu và giải thuật
Xóa nút nhánh có 1 con
– Trường hợp nút cần xóa là nút nhánh có 1 con
z Gắn cây con của nút cần xóa vào cha Nút cần xóa T T3 T T 2 4 T 3 T 2 4 T1 T1
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 1: Xác định nút thay thế
z Nút thay thế là nút cực phải của cây con trái h ặ o c
nút cực trái của cây con phải Nút cần xóa T T4 T 3 5 T1 Nút thay thế T2
Đỗ Bích Diệp - Khoa CNTT-ĐHBK HN 12
Cấu trúc dữ liệu và giải thuật
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ỏi cây
– Gắn con trái của y vào cha của y Nút cần xóa T T4 T 3 5 T T 1 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ắn y vào vị trí của nút cần xóa T T4 T 3 5 T T 1 2
Đỗ Bích Diệp - Khoa CNTT-ĐHBK HN 13
Cấu trúc dữ liệu và giải thuật
Xóa nút trên cây nhị phân tìm kiếm
Algorithm BSTDEL(key, nut_xoa, nut_cha)
{Thực hiện việc xóa nút trỏ bởi con trỏ nut_xoa , b ế
i t con trỏ nut_cha trỏ tới nút cha
của nút xóa, biết giá trị key của nút cần xóa}
1. If (LPTR(nut_xoa) = null && RPTR(nut_xoa) = null) then begin
if ( key < INFO(nut_cha)) then LPTR(nut_cha): = null;
else RPTR(nut_cha) := null; call dispose(nut_xoa) ; end;
2. If (LPTR(nut_xoa) = null || RPTR(nut_xoa) = null) then begin
if LPTR(nut_xoa) = NULL then nut_thay := RPTR(P);
else if RPTR(nut_xoa) = NULL then nut_thay := LPTR(P);
if (key < INFO(nut_cha)) then LPTR(nut_cha) := nut_thay;
else RPTR(nut_cha) := nut_thay; call dispose(nut_xoa); end;
Xóa nút trên cây nhị phân tìm kiếm
3. If (LPTR(nut_xoa) != null && RPTR(nut_xoa) != null) then begin
nut_thay := LPTR(nut_xoa); {sang cây con trái}
while RPTR(nut_thay) <> null do begin
T := nut_thay; nut_thay := RPTR(nut_thay);
end;{Kết thúc vòng lặp nut_thay trỏ đến nút cực phải của cây con trái, T:nút cha của nút thay}
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.
Đỗ Bích Diệp - Khoa CNTT-ĐHBK HN 14
Cấu trúc dữ liệu và giải thuật
Cây nhị phân tìm kiếm
z Đánh giá giải thuật : tìm k ế i m và loại bỏ
– Thời gian thực hiện trung bình T (n) = O(log n) tb 2
z Nhược điểm của cây tìm kiếm nhị phân:
– Cây suy biến có thể được hình thành trong quá trình
bổ sung, ảnh hưởng đến hiệu năng của việc sử
dụng cây nhị phân trong tìm kiếm
Cây nhị phân cân đối AVL
z Cây nhị phân cân đối AVL (AVL balanced binary search tree)
– Một cây nhị phân tìm kiếm được gọi là cây cân đối AVL nếu
với mọi nút trên cây, ch ề
i u cao của 2 cây con tương ứng c ỉ h
chênh nhau nhiều nhất là 1 đơn vị 33 33 29 64 29 64 70 19 30 40 70 19 30 23 65 23 65 80 80
Cây nhị phân tìm kiếm cân đối AVL
Cây nhị phân tìm kiếm không cân đối
Đỗ Bích Diệp - Khoa CNTT-ĐHBK HN 15
Cấu trúc dữ liệu và giải thuật
Cây nhị phân cân đối AVL z Bổ sung trên cây AVL
– Bổ sung theo nguyên tắc giống với cây nhị phân tìm k ế i m
– Việc bổ sung có thể làm vi phạm tính cân bằng ủ c a cây 27 27 27 Bổ sung 25 Khôi phục cân bằng 18 44 18 44 20 44 12 20 35 52 12 20 35 52 18 22 35 52 19 22 19 22 12 19 25 25
Cây nhị phân cân đối AVL
– Khôi phục tính cân bằng ủ c a cây
z Kiểm tra tính cân bằng của các nút nằm trên đường đi
từ nút gốc đến nút mới được bổ sung
z Xác định nút vi phạm gần nhất với nút mới
z Thực hiện các phép quay với nút vi phạm mà không cần
thực hiện phép quay nào khác tại tổ tiên của nút đó
– Tùy vào vị trí nút mới so với nút vi p ạ h m có 4 loại phép quay khác nhau
Đỗ Bích Diệp - Khoa CNTT-ĐHBK HN 16
Cấu trúc dữ liệu và giải thuật
Cây nhị phân cân đối AVL
z Xác định các phép quay cần sử dụng
– Bước 1: Xác định nút vi phạm gần nhấ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ạm trên đường đi xác định vị trí bổ sung
z Trường hợp 1: Quay đơn phải Nút vi phạm (nút bất thường) Nút con Nút cháu
Cây nhị phân cân đối AVL
z Trường hợp 2: Quay đơn trái (single left rotation)
z Trường hợp 3: Quay kép phải (double right rotation) :
quay trái với cây con trái rồi quay phải với cây có nút
vi phạm và con trái của nó
Đỗ Bích Diệp - Khoa CNTT-ĐHBK HN 17
Cấu trúc dữ liệu và giải thuật
Cây nhị phân cân đối AVL
z Trường hợp 4: Quay kép trái (double left rotation) :
quay phải với cây con phải, rồi quay trái ớ v i cây có
nút vi phạm và con phải của nó
Cây nhị phân cân đối AVL
– Trường hợp 1: Phép quay đơn phải
Sau khi quay đơn phi Nút vi B phạm
Trước khi quay A A B C C h+1 T1 h T2 h-1 h-1 or h-2 h h-1 h-1 or h-2 h+1 T T T T T T 3 4 1 3 4 2
AVL trli trng thái cân bng
Đỗ Bích Diệp - Khoa CNTT-ĐHBK HN 18
Cấu trúc dữ liệu và giải thuật
Cây nhị phân cân đối AVL
– Trường hợp 3: Phép quay kép phải Nút vi
Trước khi quay Sau khi quay kép phạm phi D A B C B A D C h h-1 h-1 or h-2 T T T h 1 3 4 T h T" 1 T2 2 Th T" 2 2 h-1 h-1 or h-2 T T 3 4 AVL trở lại trạng thái cân bằng
Cây nhị phân cân đối AVL
– Bổ sung trên cây AVL – Ví dụ: Bổ sung 30 vào cây s 8 Nút vi phạm 3 14 Không vi 1 6 10 19 phạm Không vi 4 phạm 17 24 Không vi 30 phạm
Đỗ Bích Diệp - Khoa CNTT-ĐHBK HN 19
Cấu trúc dữ liệu và giải thuật
Cây nhị phân cân đối AVL
– Để sửa đổi lại cây, quay cây có gốc tại 14: Quay từ phải
sang trái với cây con phải (nút 14 và 19) – Phép quay này
gọi là phép quay đơn trái 8 3 19 1 6 14 24 4 17 30 10
Cây nhị phân cân đối AVL
– Bổ sung trên cây AVL – Ví dụ 8 Nút vi 3 14 phạm 1 6 10 19 Không vi phạm 4 17 24 18 Bổ sung 18 vào cây Không vi Không vi phạm phạm
Đỗ Bích Diệp - Khoa CNTT-ĐHBK HN 20
Cấu trúc dữ liệu và giải thuật
Cây nhị phân cân đối AVL
z Loại bỏ trên cây AVL cũng có thể dẫn đến tình trạng mất
cân đối của cây, tương tự như trong phép bổ sung, ta
cũng sẽ thực hiện phép quay để tái cân bằng lại cây.
z Ví dụ: Loại bỏ một nút lá không làm ảnh hưởng đến
tình trạng cân bằng của cây 20 15 22 14 18 25 17 19 Loại bỏ
Cây nhị phân cân đối AVL
z Ví dụ: Loại bỏ một nút nhánh không làm ảnh hư n ở g
đến tính cân bằng của cây 20 15 22 14 18 25 17 19 Loại bỏ
Đỗ Bích Diệp - Khoa CNTT-ĐHBK HN 21
Cấu trúc dữ liệu và giải thuật
Cây nhị phân cân đối AVL
z Ví dụ: Loại bỏ một nút ẫ
d n đến phải thực hiện phép
quay để tái cân bằng cây Nút vi phạm 18 20 Loại bỏ 22 20 15 15 14 18 25 14 17 19 25 17 19
Cây nhị phân cân đối AVL
z Tái cân bằng lại cây sau khi loại bỏ trên cây AVL –
Gọi z là nút đầu tiên không cân bằng trên đường đi từ vị trí
của nút bị loại lên đến gốc cây. –
Gọi y là nút con của z, y là nút con có chiều cao lớn hơn –
Gọi x là nút con của y, x là nút con có chiều cao lớn hơn –
Ta sẽ thực hiện phép quay tại nút z khi xét thêm cả y, x để tái cân bằng lại cây –
Phép quay có thể ảnh hưởng đến tính cân bằng của các nút
có chiều cao lớn hơn z trong cây (các nút tổ tiên của z trên
đường đi đến gốc) vì ậ
v y cần phải kiểm tra tính cân ằ b ng
của các nút đó cho đến khi chạm tới gốc.
Đỗ Bích Diệp - Khoa CNTT-ĐHBK HN 22
Cấu trúc dữ liệu và giải thuật
Cây nhị phân cân đối AVL 62 z 44 44 78 Nút cn xóa 17 62 y 17 50 88 50 78 x 48 54 48 54 88
Đỗ Bích Diệp - Khoa CNTT-ĐHBK HN 23