Chương 5. Cây nhị phân tìm kiếm
ầ
Tr n Minh Thái Email: minhthai@huflit.edu.vn Website: www.minhthai.edu.vn
1
Nội dung
1.
Khái niệm
2.
Đặc điểm
3.
Định nghĩa cấu trúc dữ liệu
4.
Các lưu ý khi cài đặt
5.
Các thao tác xử lý
2
Khái niệm
• Bậc của một nút: là số cây
con của nút đó
2
2
2
• Bậc của cây: là bậc lớn nhất của các nút trong cây. Cây có bậc n thì gọi là cây n- phân
1
0
1
0
• Nút gốc: là nút không có nút
cha
0
0
• Nút lá: là nút có bậc bằng 0
• Nút nhánh: là nút có bậc khác 0 và không phải là gốc
3
Khái niệm
• Chiều dài đường đi đến nút x: là số nhánh cần đi qua kể từ gốc đến x
M c 1ứ
• Chiều cao h của cây: Mức lớn nhất của các nút lá
M c 2ứ
M c 3ứ
M c 4ứ
x
4
Đặc điểm của cây nhị phân
2I-1
2h-1, với h là chiều cao của cây
• Số nút ở mức I (cid:0) • Số nút ở mức lá (cid:0) • Chiều cao của cây h (cid:0)
log2N, với N là số nút trong cây
5
Biểu diễn cây nhị phân
• Cây nhị phân là một cấu trúc bao gồm các phần tử (node) được kết nối với nhau theo quan hệ “cha-con” với mỗi cha có tối đa 2 con.
• Mỗi nút gồm các thông tin:
• Dữ liệu lưu trữ: data
• Liên kết tới cây con trái của nút: pLeft
• Liên kết tới cây con phải của nút: pRight
6
Định nghĩa kiểu dữ liệu dùng C
data Giá trị
ỏ
pLeft
pRight
ỏ Tr trái
ả Tr ph i
typedef struct TNode {
DataType data; TNode *pLeft, *pRight;
} *Tree;
7
TNODE Nút
Ví dụ khai báo node chứa giá trị nguyên
typedef struct TNode
{
int data;
TNode *pLeft, *pRight;
} *Tree;
8
Cây nhị phân tìm kiếm
• Là 1 cây nhị phân
• Giá trị của một node luôn
7
lớn hơn giá trị của các
node nhánh trái và nhỏ
3 36
1 6 15 40
hơn giá trị các node nhánh
phải
Nút có giá trị nhỏ nhất nằm
ở nút trái nhất của cây 9
Nút có giá trị lớn nhất nằm
ở nút phải nhất của cây
4 23
Các lưu ý khi cài đặt
ướ
ể ữ ệ
ể
ễ
B c 1:
Khai báo ki u d li u bi u di n cây
ự
ậ
ướ B c 2:
ư ữ ệ Xây d ng hàm đ a d li u (nh p) vào cây
ướ
ự
ế
ệ
ỷ
B c 3:
Xây d ng các thao tác duy t, tìm ki m, hu , …
10
Cấu trúc chương trình
Khai báo cấu trúc cây
Khởi tạo cây rỗng
Xây dựng cây
Các thao tác
Hủy cây
11
Các thao tác cơ bản
1. Tạo cây
2. Duyệt cây
3. Cho biết các thông tin của cây
4. Tìm kiếm
5. Xoá node trên cây
12
Tạo cây
7
36
3
1
6
4
15
40
Ø Nếu node cần thêm
nhỏ hơn node đang
xét thì thêm về bên
trái
Ø Ngược lại thì thêm về
bên phải
13
7 4015461363
Hàm thêm một phần tử vào cây
int InsertNode (Tree & t, int x) {
ị if(t!=NULL) { return 0; //Có giá tr trùng
if(x==t>data) else { InsertNode(t>pLeft, x);
if(x
}
} else {
ế ộ ớ return 1; //Thi u b nh
t=new TNode; if(t==NULL) t>data=x; t>pLeft=t>pRight=NULL; return 1; //Thêm thành công
14
}
}
Bài tập
1.
Viết hàm tạo cây nhị phân số nguyên từ các giá trị nhập vào từ bàn phím. Quá trình nhập cho đến khi gặp giá trị trùng hoặc hết bộ nhớ
2.
Viết hàm tạo cây nhị phân số nguyên từ dãy số nguyên cho trước
15
Duyệt cây
Thứ tự trước
(NLR)
Thứ tự giữa
(LNR)
Thứ tự sau
(LRN)
16
ế
ệ
ả B cướ K t qu duy t theo th t
ứ ự NLR 3
7
7 L7 R7
3
36
L3 R3 R7 1 R3 R7
1 6 15 40
6 L6 R7 4 R7
36 L36 R36
1 2 3 4 5 6 7 8 9
KQ 7
3
1
6
4
36
15 R15 R36 23 R36 40 40
23
15
17
4 23
Hàm duyệt NLR
Tại node t đang xét, nếu khác rỗng thì
• In giá trị của t
void NLR (Tree t) {
• Duyệt cây con bên trái của t
theo thứ tự NLR
• Duyệt cây con bên phải của t
if(t!=NULL) {
theo thứ tự NLR
cout<
}
18
}
Bài tập
Vẽ cây nhị phân tìm kiếm theo thứ tự nhập từ trái sang phải và duyệt cây theo thứ tự trước:
• 27; 19; 10; 21; 35; 25; 41; 12; 46; 7
• H; B; C; A; E; D; Z; M; P; T
• Huế; Đà Nẵng; Hà Nội; Vĩnh Long; Cần Thơ; Sóc Trăng; Nha Trang; Đồng Nai; Vũng Tàu; An Giang; Tiền Giang; Bình Dương; Hải Dương
19
ứ ự ệ ế LNR 7
L7 L3 3 36
ả B cướ K t qu duy t theo th t 7 3 3 1
3 6 15 40
R7 R3 R3 R3 L6
7 7 7 6 6 4 23 4
R7 R7 R7 7 7 7 6
7
36 R36
1 R7 R7 R7 R7 L36 15 R15 23
1 2 3 4 5 6 7 8 9 10 11 12 13
36 R36 36 R36 36 R36 40 40 KQ 1 3 4 6 7 15 23 36 20
Hàm duyệt LNR
Tại node t đang xét, nếu khác rỗng thì
• Duyệt cây con bên trái của t
theo thứ tự LNR
void LNR (Tree t) {
• In giá trị của t
• Duyệt cây con bên phải của t
theo thứ tự LNR
if(t!=NULL) {
LNR(t->pLeft);
cout<
}
21
}
ứ ự
ế
ệ
ả B cướ K t qu duy t theo th t
LRN
7
3 36
6 15 40 1
L7 R7 7 L3 R3 3 R7 7 R3 3 R7 7 1 L6 6 3 6 3 4 6 3 3
R7 7 R7 7 R7 7 7 R7 L36 R36 36 R15 15 15 23 15
22
1 2 3 4 5 6 7 8 9 10 11 12 13 14 KQ 1
7 R36 36 7 R36 36 7 R36 36 7 36 7 40 36 7 7 36 7
40
4
6 3
23
15
4 23
Hàm duyệt LRN
Tại node t đang xét, nếu khác rỗng thì
void LRN (Tree t) {
• Duyệt cây con bên trái của t theo thứ tự LRN
• Duyệt cây con bên phải của t theo thứ tự LRN
if(t!=NULL) {
LRN(t->pLeft);
LRN(t->pRight);
cout<
• In giá trị của t
“;
}
23
}
Bài tập
• Vẽ cây nhị phân tìm kiếm theo thứ tự nhập:
27, 19, 10, 21, 3, 15, 41, 50, 30, 7
Hãy duyệt cây trên theo thứ tự giữa
• Vẽ cây nhị phân tìm kiếm theo thứ tự nhập:
H, B, C, A, E, D, T, M, X, O
Hãy duyệt cây trên theo thứ tự sau
24
Kiểm tra kết quả duyệt bằng cách xây dựng lại cây nhị phân từ kết quả duyệt Tạo cây từ kết quả duyệt NLR
•Chọn giá trị đầu tiên làm node gốc
•Lần lượt đưa các giá trị còn lại từ trái sang phải vào cây theo nguyên tắc tạo cây
Tạo cây từ kết quả duyệt LRN
•Chọn giá trị cuối cùng làm node gốc
•Lần lượt đưa các giá trị còn lại từ phải sang trái vào cây theo nguyên tắc tạo cây
25
Bài tập
Vẽ cây nhị phân tìm kiếm T biết rằng khi duyệt cây T theo thứ tự NLR thì được dãy sau: 9, 4, 1, 3, 8, 6, 5, 7, 10, 14, 12, 13, 16, 19
• Hãy duyệt cây T trên theo thứ tự LRN
• Liệt kê các nút lá của cây. Liệt kê các nút nhánh của cây
26
Bài tập
Vẽ cây nhị phân tìm kiếm T biết rằng khi duyệt cây T theo thứ tự LRN thì được dãy sau: 1, 4, 7, 5, 3, 16, 18, 15, 29, 25, 30, 20, 8
• Hãy duyệt cây T trên theo thứ tự NLR
• Cây T có chiều cao là bao nhiêu? Tìm các đường đi từ gốc có độ dài là 4 trên cây
27
Tìm kiếm
1.
Tìm x
2.
Tìm min
3.
Tìm min của cây con bên phải
4.
Tìm max
5.
Tìm max của cây con bên trái
28
Ví dụ tìm x = 23
7
3 36
1 6 15 40
29
4 23
Bài tập
Cho cây nhị phân tìm kiếm, mỗi node có giá trị nguyên, hãy định nghĩa các hàm sau:
• Tìm node có giá trị x
• Tìm node có giá trị lớn nhất
• Tìm node có giá trị nhỏ nhất của cây con phải
30
Bài tập
Cho cây nhị phân tìm kiếm, mỗi node có giá trị nguyên, hãy định nghĩa các hàm sau:
1. In ra các node có giá trị chẵn
2. In ra các node có giá trị lớn hơn x
3. Đếm số node của cây
4. Tính độ cao của cây
31
Bài tập
5. Đếm số node lá (node bậc 0)
6. Đếm số node có 1 cây con (node bậc 1)
7. Đếm số node chỉ có 1 cây con phải
8. Đếm số node có 1 cây con trái
9. Đếm số node 2 cây con (node bậc 2)
10. In các node trên từng mức của cây
11. Cho biết độ dài đường đi từ gốc đến node x
32
Xóa node trên cây
1.
Node lá
7
2.
Node có 1 cây con
3.
Node có 2 cây con
3 36
1 6 15 40
33
4 23
Xóa node lá
7
Xóa 1
Xóa 23
3 36
1 6 15 40
34
4 23
Xóa node 1 cây con
Node cha của 6
Xóa 6
7
3 36
1 6 15 40
35
4 23
Xóa node 1 cây con
Xóa 15
7
3 36
1 6 15 40
36
4 23
Xóa node có 2 cây con
Bước 1: Tìm node thế
mạng
• Cách 1: Tìm node trái nhất của cây con phải
7
• Cách 2: Tìm node phải
nhất của cây con trái
3 36
1 6 15 40
4 23
Bước 2: Thay giá trị của node thế mạng vào node cần xóa
16
Bước 3: Xóa node thế mạng
37
Xóa node 2 cây con
Xóa 36
Bước 1: Tìm node thế
mạng
7
3 36
Node thế mạng
1 6 15 40
4 23
38
16
Xóa node 2 cây con
Xóa 36
7
Bước 2: Thay giá trị node thế mạng cho node cần xóa
Cập nhật giá trị
3 23
Node thế mạng
1 6 15 40
4 23
39
16
Xóa node 2 cây con
Xóa 36
7
Bước 3: Xóa node thế mạng
3 23
Xóa
1 6 15 40
4 23
40
16
Xóa node 2 cây con
Kết quả: xóa 36
7
3 23
1 6 15 40
41
16 4
Bài tập
Cho dãy số theo thứ tự nhập từ trái sang phải: 20, 15, 35, 30, 11, 13, 17, 36, 47, 16, 38, 28, 14
• Vẽ cây nhị phân tìm kiếm cho dãy số trên
• Trình bày từng bước và vẽ lại cây sau khi lần lượt xoá
các nút: 11 và 35
42
Bài tập
• Viết hàm xóa node có giá trị x trong cây nhị phân số nguyên
43
void Remove(Tree & t, int x) {
if (t != NULL) {
if (x < t->key)
Remove(t->pLeft, x);
else if (x > t->key)
Remove(t->pRight, x);
else {
TNode * pHuy = t; if (t->pLeft == NULL) t = t->pRight;
else if (t->pRight == NULL)
t = t->pLeft;
else SearchStandFor(pHuy, t->pRight);
delete pHuy;
}
}
44
}
void SearchStandFor(Tree &pHuy, Tree &pTM) {
if(pTM->pLeft)
SearchStandFor(pHuy, pTM->pLeft);
else {
pHuy->key=pTM->key; pHuy=pTM; pTM=pTM->pRight;
}
}
45
Đánh giá
• Thao tác tìm kiếm, thêm mới, xóa đều có độ phức
tạp trung bình O(h), với h là chiều cao của cây
• Trường hợp tốt nhất, cây có n nút sẽ có độ cao h = log2(n). Chi phí tìm kiếm sẽ tương đương tìm kiếm nhị phân trên mảng có thứ tự
• Trường hợp xấu nhất, cây có thể bị suy biến thành 1 DSLK. Lúc đó các thao tác trên sẽ có độ phức tạp O(n)
Vì vậy cần có cải tiến cấu trúc của CNPTK để đạt được chi phí cho các thao tác là log2(n)
46
Cây nhị phân tìm kiếm cân bằng
• Phát minh: Nhà toán học Nga G. M. Adel’Son-
Vel’Skil và E. M. Landis (1962)
• Cấu trúc cây giúp tối ưu thời gian tìm kiếm
• Cây nhị phân tìm kiếm cân bằng: cây AVL
• Chi phí tìm kiếm, thêm mới, xoá trong cây n nút là
O(log n)
47
Định nghĩa
• Cây AVL là một cây nhị phân tìm kiếm
• Chiều cao cây con trái và phải của nút gốc hơn
kém nhau không quá 1
• Cả hai cây con trái và phải cũng phải là cây AVL
48
Chỉ số cân bằng (Balance factor)
Chỉ số cân bằng (bF – balance Factor) của một nút:
bF = hR – hL
ü hL: chiều cao cây con trái
ü hR: chiều cao cây con phải
Có 3 trường hợp:
ØbF = 0: hL = hR (Ký hiệu EH: Equal Height)
ØbF > 0: hL < hR (Ký hiệu RH: Right Higher)
ØbF < 0: hL > hR (Ký hiệu LH: Left Higher)
49
Khai báo cấu trúc cây AVL
typedef struct AVLNode {
DataType key;
char bF;
AVLNode* pLeft;
AVLNode* pRight;
} *AVLTree;
const char LH = -1; const char EH = 0; const char RH = 1;
50
Trường hợp 1: Lệch trái
51
Trường hợp 2: Lệch phải
52
Trường hợp 1.1: T1 lệch trái
ơ
Quay đ n Left Left
53
Trường hợp 1.2: T1 không lệch
ơ
Quay đ n Left Left
54
void RotateLL ( AVLTree &T) { AVLNode * T1 = T> pLeft ; T>pLeft = T1>pRight ; T1> pRight = T; switch(T1> bF) { case LH: T> bF = EH; T1> bF = EH; break ; case EH: T> bF = LH; T1> bF = RH; break ; } T = T1; }
Trường hợp 1.3: T1 lệch phải
Quay kép Left Right
56
void RotateLR(AVLTree &T) { AVLNode * T1 = T-> pLeft ; AVLNode * T2 = T1-> pRight ; T-> pLeft = T2-> pRight ; T2-> pRight = T; T1-> pRight = T2-> pLeft ; T2-> pLeft = T1; switch (T2-> bF) { case LH: T-> bF = RH; T1-> bF = EH; break ; case EH: T-> bF = EH; T1-> bF = EH; break ; case RH: T-> bF = EH; T1-> bF = LH; break ; } T2-> bF = EH; T = T2; }
Trường hợp 2.1 và 2.2
void RotateRR(AVLTree &T) { AVLNode * T1 = T> pRight ; T>pRight = T1> pLeft ; T1> pLeft = T; switch (T1> bF) { case RH: T> bF = EH; T1> bF = EH; break ; case EH: T> bF = RH; T1> bF = LH; break ; } T = T1; }
58
Trường hợp 2.3
void RotateRL ( AVLTree &T) { AVLNode * T1 = T> pRight ; AVLNode * T2 = T1> pLeft ; T>pRight = T2> pLeft ; T2>pLeft = T; T1>pLeft = T2> pRight ; T2> pRight = T1; switch (T2> bF) { case RH: T> bF = LH; T1> bF = EH; break ; case EH: T> bF = EH; T1> bF = EH; break ; case LH: T> bF = EH; T1> bF = RH; break ; } T2> bF = EH; T = T2; }
59
Thêm 1 node vào cây AVL
• Tương tự như trên cây NPTK
• Sau khi thêm xong, nếu chiều cao của cây thay đổi. Nếu có mất cân bằng cân bằng lại ở nút này
• Hàm insertNode trả về giá trị
• -1: không đủ bộ nhớ
• 0: trùng giá trị
• 1: thêm thành công
• 2: thêm thành công và chiều cao tăng
60
int InsertNode(AVLTree &T, int X) { int kq; if (T != NULL ) { if(T->key == X) return 0; // tồn tại x else if (T->key > X) // thêm về bên trái { kq = InsertNode(T->pLeft, X); if (kq < 2) return res; switch (T->bF) { case RH: T->bF= EH; return 1; case EH: T->bF = LH; return 2; case LH: BalanceLeft(T); return 1; } }
61
else //Trường hợp T->key
62
//Tạo node mới
T = new TNode; if (T == NULL) return -1; //thiếu bộ nhớ
T->key = X; T->bF = EH; T->pLeft = T->pRight = NULL;
return 2; //Thêm thành công và chiều cao tăng }
63
int BalanceLeft(AVLTree &T) { switch (T-> pLeft -> bF) { case LH: RotateLL (T); return 2; case EH: RotateLL (T); return 1; case RH: RotateLR (T); return 2; } return 0; } int BalanceRight(AVLTree &T) { switch (T-> pRight -> bF) { case LH: RotateRL (T); return 2; case EH: RotateRR (T); return 1; case RH: RotateRR (T); return 2; } return 0; }
Hủy 1 node trên cây
• Tương tự như trên cây NPTK
• Sau khi hủy, nếu mất cân bằng cân bằng lại
• Hàm deleteNode trả về giá trị
• 1: hủy thành công
• 0: không có X trong cây
• 2: hủy thành công và chiều cao của cây giảm
65
66
int DeleteNode(AVLTree &T, int X) { int kq ; if (T==NULL) return 0; if (T>key > X) { kq = DeleteNode (T> pLeft , X); if ( kq < 2) return kq ; switch ( T> bF ) { case LH: T> bF = EH; return 2; case EH: T> bF = RH; return 1; case BalanceRight (T); } }
else if (T->key < X) { kq = DeleteNode (T-> pRight , X); if ( kq < 2) return kq ; switch (T-> bF ) { case RH: T-> bF = EH; return 2; case EH: T-> bF = LH; return 1; case LH: return BalanceLeft (T); } }
67
else // if (T>key == X) { AVLNode * p = T; if (T> pLeft == NULL) { T = T>pRight ; kq = 2; } else if (T> pRight == NULL) { T = T> pLeft ; kq = 2; }
68
69
else // if (T> pLeft != NULL && T> pRight != NULL) { kq = SearchStandFor ( p, T > pRight ); if( kq < 2) return kq; switch( T> bF ) { case RH: T> bF = EH; return 2; case EH: T> bF = LH; return 1; case LH: return BalanceLeft (T); } } delete p; return kq ; } }
70
int SearchStandFor(AVLTree &p, AVLTree &q){ int kq; if (q>pLeft != NULLL) { kq = SearchStandFor(p, q>pLeft); if (kq < 2) return kq; switch (q>bF){ case LH: q>bF= EH; return 2; case EH: q>bF= RH; return 1; case RH: return BalanceRight(T); } } else { p>key = q>key; p = q; q = q>pRight; return 2; } }
![Đề thi cuối học kì 2 môn Cấu trúc dữ liệu và giải thuật [kèm đáp án/mới nhất]](https://cdn.tailieu.vn/images/document/thumbnail/2025/20251014/lakim0906/135x160/89711760416179.jpg)
![Tài liệu Nhập môn Học máy và Khai phá Dữ liệu [chuẩn nhất]](https://cdn.tailieu.vn/images/document/thumbnail/2025/20251001/kimphuong1001/135x160/531759303870.jpg)
