Bài giảng Câu trúc dữ liệu và giải thuật - Cây nhị phân tìm kiếm

1C
ấ
u
tr
ú
c
 d
ữ
 l
iệ
u
v
à
 t
h
u
ậ
t 
g
iả
i
C
Ấ
U
 T
R
Ú
C
 D
Ữ
 L
IỆ
U
 V
À
 G
IẢ
I 
T
H
U
Ậ
T
Click To Edit Master Title Style
1
NỘI DUNG
CÂY NHỊ PHÂN TÌM KIẾM
C
ấ
u
tr
ú
c
 d
ữ
 l
iệ
u
v
à
 t
h
u
ậ
t 
g
iả
i
C
Ấ
U
 T
R
Ú
C
 D
Ữ
 L
IỆ
U
 V
À
 G
IẢ
I 
T
H
U
Ậ
T
Click To Edit Master Title Style
2
Ðịnh nghĩa cây nhị phân tìm kiếm
• Cây nhị phân 
• Bảo đảm nguyên tắc bố trí khố tại mỗi nút:
– Các nút trong cây trái nhỏ hơn nút hiện hành
– Các nút trong cây phải lớn hơn nút hiện hành
Ví dụ:
44
18 88
13 37 59 108
15 23 40 55 71
C
ấ
u
tr
ú
c
 d
ữ
 l
iệ
u
v
à
 t
h
u
ậ
t 
g
iả
i
C
Ấ
U
 T
R
Ú
C
 D
Ữ
 L
IỆ
U
 V
À
 G
IẢ
I 
T
H
U
Ậ
T
Click To Edit Master Title Style
3
Ưu điểm của cây nhị phân tìm kiếm
• Nhờ trật tự bố trí khĩa trên cây :
–Định hướng được khi tìm kiếm
• Cây gồm N phần tử :
–Trường hợp tốt nhất h = log2N, 
–Trường hợp xấu nhất h = LnN
–Tình huống xảy ra trường hợp xấu nhất ?
C
ấ
u
tr
ú
c
 d
ữ
 l
iệ
u
v
à
 t
h
u
ậ
t 
g
iả
i
C
Ấ
U
 T
R
Ú
C
 D
Ữ
 L
IỆ
U
 V
À
 G
IẢ
I 
T
H
U
Ậ
T
Click To Edit Master Title Style
4
Cấu trúc dữ liệu của cây nhị phân tìm kiếm
• Cấu trúc dữ liệu của 1 nút
typedef struct tagTNode
{
int Key; //trường dữ liệu là 1 số nguyên
struct tagTNode *pLeft; 
struct tagTNode *pRight; 
}TNode;
• Cấu trúc dữ liệu của cây
typedef TNode *TREE;
2C
ấ
u
tr
ú
c
 d
ữ
 l
iệ
u
v
à
 t
h
u
ậ
t 
g
iả
i
C
Ấ
U
 T
R
Ú
C
 D
Ữ
 L
IỆ
U
 V
À
 G
IẢ
I 
T
H
U
Ậ
T
Click To Edit Master Title Style
5
Các thao tác trên cây nhị phân tìm kiếm
 Tạo 1 cây rỗng
 Tạo 1 nút cĩ trường Key bằng x
Thêm 1 nút vào cây nhị phân tìm kiếm
Xố 1 nút cĩ Key bằng x trên cây
Tìm 1 nút cĩ khố bằng x trên cây
C
ấ
u
tr
ú
c
 d
ữ
 l
iệ
u
v
à
 t
h
u
ậ
t 
g
iả
i
C
Ấ
U
 T
R
Ú
C
 D
Ữ
 L
IỆ
U
 V
À
 G
IẢ
I 
T
H
U
Ậ
T
Click To Edit Master Title Style
6
Tạo cây rỗng
• Cây rỗng -> địa chỉ nút gốc bằng NULL
void CreateTree(TREE &T)
{ 
T=NULL;
}
C
ấ
u
tr
ú
c
 d
ữ
 l
iệ
u
v
à
 t
h
u
ậ
t 
g
iả
i
C
Ấ
U
 T
R
Ú
C
 D
Ữ
 L
IỆ
U
 V
À
 G
IẢ
I 
T
H
U
Ậ
T
Click To Edit Master Title Style
7
Tạo 1 nút cĩ Key bằng x
TNode *CreateTNode(int x)
{
TNode *p;
p = new TNode; //cấp phát vùng nhớ động
if(p==NULL)
exit(1); // thốt
else
{
p->key = x; //gán trường dữ liệu của nút = x
p->pLeft = NULL; 
p->pRight = NULL;
}
return p;
} C
ấ
u
tr
ú
c
 d
ữ
 l
iệ
u
v
à
 t
h
u
ậ
t 
g
iả
i
C
Ấ
U
 T
R
Ú
C
 D
Ữ
 L
IỆ
U
 V
À
 G
IẢ
I 
T
H
U
Ậ
T
Click To Edit Master Title Style
8
Thêm một nút x
• Rằng buộc: Sau khi thêm cây đảm bảo là cây 
nhị phân tìm kiếm.
int insertNode(TREE &T, Data X)
{ if(T)
{ if(T->Key == X) return 0; 
if(T->Key > X) return insertNode(T->pLeft, X);
else return insertNode(T->pRight, X);}
T = new TNode;
if(T == NULL) return -1; 
T->Key = X;
T->pLeft =T->pRight = NULL;
return 1; 
}
3C
ấ
u
tr
ú
c
 d
ữ
 l
iệ
u
v
à
 t
h
u
ậ
t 
g
iả
i
C
Ấ
U
 T
R
Ú
C
 D
Ữ
 L
IỆ
U
 V
À
 G
IẢ
I 
T
H
U
Ậ
T
Click To Edit Master Title Style
9
Minh họa thêm 1 phần tử vào cây
44
18 88
13 37 59 108
15 23 40 55 71
Thêm X=50
44 < X
88 > X
59 > X
50
55 > X
C
ấ
u
tr
ú
c
 d
ữ
 l
iệ
u
v
à
 t
h
u
ậ
t 
g
iả
i
C
Ấ
U
 T
R
Ú
C
 D
Ữ
 L
IỆ
U
 V
À
 G
IẢ
I 
T
H
U
Ậ
T
Click To Edit Master Title Style
10
Tìm nút cĩ khố bằng x (khơng dùng đệ quy)
TNode * searchNode(TREE Root, Data x)
{ Node *p = Root;
while (p != NULL)
{ if(x == p->Key) return p;
else 
if(x Key) p = p->pLeft;
else p = p->pRight;
}
return NULL;
}
C
ấ
u
tr
ú
c
 d
ữ
 l
iệ
u
v
à
 t
h
u
ậ
t 
g
iả
i
C
Ấ
U
 T
R
Ú
C
 D
Ữ
 L
IỆ
U
 V
À
 G
IẢ
I 
T
H
U
Ậ
T
Click To Edit Master Title Style
11
Tìm nút cĩ khố bằng x (dùng đệ quy)
TNode *SearchTNode(TREE T, int x)
{
if(T!=NULL)
{
if(T->key==x)
return T;
else
if(x>T->key)
return SearchTNode(T->pRight,x);
else 
return SearchTNode(T->pLeft,x);
}
return NULL;
} C
ấ
u
tr
ú
c
 d
ữ
 l
iệ
u
v
à
 t
h
u
ậ
t 
g
iả
i
C
Ấ
U
 T
R
Ú
C
 D
Ữ
 L
IỆ
U
 V
À
 G
IẢ
I 
T
H
U
Ậ
T
Click To Edit Master Title Style
12
Minh hoạ tìm một nút
44
18 88
13 37 59 108
15 23 40 55 71
Tìm X=55
Tìm thấy X=55
55
4C
ấ
u
tr
ú
c
 d
ữ
 l
iệ
u
v
à
 t
h
u
ậ
t 
g
iả
i
C
Ấ
U
 T
R
Ú
C
 D
Ữ
 L
IỆ
U
 V
À
 G
IẢ
I 
T
H
U
Ậ
T
Click To Edit Master Title Style
13
Minh hoạ thành lập 1 cây từ dãy số
9, 5, 4, 8, 6, 3, 14,12,13
9
5 1
4
84
63
12
13
C
ấ
u
tr
ú
c
 d
ữ
 l
iệ
u
v
à
 t
h
u
ậ
t 
g
iả
i
C
Ấ
U
 T
R
Ú
C
 D
Ữ
 L
IỆ
U
 V
À
 G
IẢ
I 
T
H
U
Ậ
T
Click To Edit Master Title Style
14
Hủy 1 nút cĩ khố bằng X trên cây
Hủy 1 phần tử trên cây phải đảm bảo điều kiện 
ràng buộc của Cây nhị phân tìm kiếm
Cĩ 3 trường hợp khi hủy 1 nút trên cây
 TH1: X là nút lá 
 TH2: X chỉ cĩ 1 cây con (cây con trái hoặc cây con phải)
 TH3: X cĩ đầy đủ 2 cây con
 TH1: Ta xố nút lá mà khơng ành hưởng đến các 
nút khác trên cây
 TH2: Trước khi xố x ta mĩc nối cha của X với con 
duy nhất cùa X.
 TH3: Ta dùng cách xố gián tiếp
C
ấ
u
tr
ú
c
 d
ữ
 l
iệ
u
v
à
 t
h
u
ậ
t 
g
iả
i
C
Ấ
U
 T
R
Ú
C
 D
Ữ
 L
IỆ
U
 V
À
 G
IẢ
I 
T
H
U
Ậ
T
Click To Edit Master Title Style
15
TH: X là nút lá
• 1. Xĩa node này
• 2. Gán liên kết từ cha của nĩ thành rỗng
C
ấ
u
tr
ú
c
 d
ữ
 l
iệ
u
v
à
 t
h
u
ậ
t 
g
iả
i
C
Ấ
U
 T
R
Ú
C
 D
Ữ
 L
IỆ
U
 V
À
 G
IẢ
I 
T
H
U
Ậ
T
Click To Edit Master Title Style
16
Trường hợp 1: X là nút lá
• Ví dụ : chỉ đơn giản hủy X vì nĩ khơng mĩc nối
đến phần tử nào khác.
44
18 88
13 37 59 108
15 23 40 55 71
T/h 1: hủy X=40
5C
ấ
u
tr
ú
c
 d
ữ
 l
iệ
u
v
à
 t
h
u
ậ
t 
g
iả
i
C
Ấ
U
 T
R
Ú
C
 D
Ữ
 L
IỆ
U
 V
À
 G
IẢ
I 
T
H
U
Ậ
T
Click To Edit Master Title Style
17
Trường hợp 2: X chỉ cĩ 1 con (trái hoặc phải)
1. Gán liên kết từ cha của nĩ xuống con duy 
nhất của nĩ
2. Xĩa node này
u
x
v
u
v
C
ấ
u
tr
ú
c
 d
ữ
 l
iệ
u
v
à
 t
h
u
ậ
t 
g
iả
i
C
Ấ
U
 T
R
Ú
C
 D
Ữ
 L
IỆ
U
 V
À
 G
IẢ
I 
T
H
U
Ậ
T
Click To Edit Master Title Style
18
Minh hoạ hủy phần tử x cĩ 1 cây con
44
18 88
13 59 10837
15 23 55 71
Hủy X=37
C
ấ
u
tr
ú
c
 d
ữ
 l
iệ
u
v
à
 t
h
u
ậ
t 
g
iả
i
C
Ấ
U
 T
R
Ú
C
 D
Ữ
 L
IỆ
U
 V
À
 G
IẢ
I 
T
H
U
Ậ
T
Click To Edit Master Title Style
19
Trường hợp 3: X cĩ đủ 2 con 
1. Tìm w là node trước node x trên phép duyệt cây 
inorder (chính là node cực phải của cây con bên 
trái của x)
2. Thay x bằng w
3. Xĩa node w cũ (giống trường hợp 1 hoặc 2 đã xét)
C
ấ
u
tr
ú
c
 d
ữ
 l
iệ
u
v
à
 t
h
u
ậ
t 
g
iả
i
C
Ấ
U
 T
R
Ú
C
 D
Ữ
 L
IỆ
U
 V
À
 G
IẢ
I 
T
H
U
Ậ
T
Click To Edit Master Title Style
20
Hủy 1 nút cĩ 2 cây con
 Ta dùng cách hủy gián tiếp, do X cĩ 2 cây con
 Thay vì hủy X ta tìm phần tử thế mạng Y. Nút Y cĩ 
tối đa 1 cây con. 
 Thơng tin lưu tại nút Y sẽ được chuyển lên lưu tại 
X.
 Ta tiến hành xố hủy nút Y (xố Y giống 2 trường 
hợp đầu)
Cách tìm nút thế mạng Y cho X: Cĩ 2 cách
 C1: Nút Y là nút cĩ khố nhỏ nhất (trái nhất) bên 
cây con phải X
 C2: Nút Y là nút cĩ khố lớn nhất (phải nhất) bên 
cây con trái của X
6C
ấ
u
tr
ú
c
 d
ữ
 l
iệ
u
v
à
 t
h
u
ậ
t 
g
iả
i
C
Ấ
U
 T
R
Ú
C
 D
Ữ
 L
IỆ
U
 V
À
 G
IẢ
I 
T
H
U
Ậ
T
Click To Edit Master Title Style
21
Minh họa hủy phần tử X cĩ 2 cây con
44
18 88
13 37 59 108
15 23 40 55 71
30
Xố nút cĩ trường 
Key = 18, lúc đĩ nút cĩ 
khố 23 là nút thế mạng
C
ấ
u
tr
ú
c
 d
ữ
 l
iệ
u
v
à
 t
h
u
ậ
t 
g
iả
i
C
Ấ
U
 T
R
Ú
C
 D
Ữ
 L
IỆ
U
 V
À
 G
IẢ
I 
T
H
U
Ậ
T
Click To Edit Master Title Style
22
Nhận xét
– Tất cả các thao tác tìm kiếm, thêm, xố đều cĩ độ
phức tạp trung bình O(h), với h là chiều cao của cây
– Trong trong trường hợp tốt nhất, CNPTK cĩ n nút sẽ
cĩ độ cao h = log
2
(n). Chi phí tìm kiếm khi đĩ sẽ
tương đương tìm kiếm nhị phân trên mảng cĩ thứ tự.
– Trong trường hợp xấu nhất, cây cĩ thể bị suy biến
thành 1 danh sách liên kết (khi mà mỗi nút đều chỉ
cĩ 1 con trừ nút lá). 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à log
2
(n).