Download miễn phí Bài giảng Cấu trúc dữ liệu và giải thuật 1 - Cây nhị phân tìm kiếm
Hủy 1 nút có khoá 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 hay cây con phải)
TH3: X có đầy đủ 2 cây con
TH1: Ta xoá nút lá mà không ành hưởng đến các
nút khác ttrên cây
TH2: Trước khi xoá 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 xoá gián tiếp
Để tải bản Đầy Đủ của tài liệu, xin Trả lời bài viết này, Mods sẽ gửi Link download cho bạn sớm nhất qua hòm tin nhắn.
Ai cần download tài liệu gì mà không tìm thấy ở đây, thì đăng yêu cầu down tại đây nhé:
Nhận download tài liệu miễn phí
Tóm tắt nội dung tài liệu:
Cấ
u
tr
ú
c
d
ữ
li
ệ
u
v
à
th
u
ậ
t
g
iả
i
C
Ấ
U
T
R
Ú
C
D
Ữ
L
IỆ
U
V
À
G
IẢ
I
T
H
U
Ậ
T
1
Click To Edit Master Title Style
1
NỘI DUNG
CÂY NHỊ PHÂN TÌM KIẾM
Generated by Foxit PDF Creator © Foxit Software
For evaluation only.
C
ấ
u
tr
ú
c
d
ữ
li
ệ
u
v
à
th
u
ậ
t
g
iả
i
C
Ấ
U
T
R
Ú
C
D
Ữ
L
IỆ
U
V
À
G
IẢ
I
T
H
U
Ậ
T
1
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í khoá 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
18
13 37
15 23 40
Ví dụ:
Generated by Foxit PDF Creator © Foxit Software
For evaluation only.
C
ấ
u
tr
ú
c
d
ữ
li
ệ
u
v
à
th
u
ậ
t
g
iả
i
C
Ấ
U
T
R
Ú
C
D
Ữ
L
IỆ
U
V
À
G
IẢ
I
T
H
U
Ậ
T
1
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 = Ln
–Tình huống xảy ra trường hợp xấu nhất ?
Generated by Foxit PDF Creator © Foxit Software
For evaluation only.
C
ấ
u
tr
ú
c
d
ữ
li
ệ
u
v
à
th
u
ậ
t
g
iả
i
C
Ấ
U
T
R
Ú
C
D
Ữ
L
IỆ
U
V
À
G
IẢ
I
T
H
U
Ậ
T
1
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;
Generated by Foxit PDF Creator © Foxit Software
For evaluation only.
C
ấ
u
tr
ú
c
d
ữ
li
ệ
u
v
à
th
u
ậ
t
g
iả
i
C
Ấ
U
T
R
Ú
C
D
Ữ
L
IỆ
U
V
À
G
IẢ
I
T
H
U
Ậ
T
1
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
Xoá 1 nút có Key bằng x trên cây
Tìm 1 nút có khoá bằng x trên cây
Generated by Foxit PDF Creator © Foxit Software
For evaluation only.
C
ấ
u
tr
ú
c
d
ữ
li
ệ
u
v
à
th
u
ậ
t
g
iả
i
C
Ấ
U
T
R
Ú
C
D
Ữ
L
IỆ
U
V
À
G
IẢ
I
T
H
U
Ậ
T
1
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;
}
Generated by Foxit PDF Creator © Foxit Software
For evaluation only.
C
ấ
u
tr
ú
c
d
ữ
li
ệ
u
v
à
th
u
ậ
t
g
iả
i
C
Ấ
U
T
R
Ú
C
D
Ữ
L
IỆ
U
V
À
G
IẢ
I
T
H
U
Ậ
T
1
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); // thoá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;
}
Generated by Foxit PDF Creator © Foxit Software
For evaluation only.
C
ấ
u
tr
ú
c
d
ữ
li
ệ
u
v
à
th
u
ậ
t
g
iả
i
C
Ấ
U
T
R
Ú
C
D
Ữ
L
IỆ
U
V
À
G
IẢ
I
T
H
U
Ậ
T
1
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;
}
Generated by Foxit PDF Creator © Foxit Software
For evaluation only.
C
ấ
u
tr
ú
c
d
ữ
li
ệ
u
v
à
th
u
ậ
t
g
iả
i
C
Ấ
U
T
R
Ú
C
D
Ữ
L
IỆ
U
V
À
G
IẢ
I
T
H
U
Ậ
T
1
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
Theâm X=50
44 < X
88 > X
59 > X
50
55 > X
Generated by Foxit PDF Creator © Foxit Software
For evaluation only.
C
ấ
u
tr
ú
c
d
ữ
li
ệ
u
v
à
th
u
ậ
t
g
iả
i
C
Ấ
U
T
R
Ú
C
D
Ữ
L
IỆ
U
V
À
G
IẢ
I
T
H
U
Ậ
T
1
Click To Edit Master Title Style
10
Tìm nút có khoá 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;
}
Generated by Foxit PDF Creator © Foxit Software
For evaluation only.
C
ấ
u
tr
ú
c
d
ữ
li
ệ
u
v
à
th
u
ậ
t
g
iả
i
C
Ấ
U
T
R
Ú
C
D
Ữ
L
IỆ
U
V
À
G
IẢ
I
T
H
U
Ậ
T
1
Click To Edit Master Title Style
11
Tìm nút có khoá 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;
}
Generated by Foxit PDF Creator © Foxit Software
For evaluation only.
C
ấ
u
tr
ú
c
d
ữ
li
ệ
u
v
à
th
u
ậ
t
g
iả
i
C
Ấ
U
T
R
Ú
C
D
Ữ
L
IỆ
U
V
À
G
IẢ
I
T
H
U
Ậ
T
1
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
Generated by Foxit PDF Creator © Foxit Software
For evaluation only.
C
ấ
u
tr
ú
c
d
ữ
li
ệ
u
v
à
th
u
ậ
t
g
iả
i
C
Ấ
U
T
R
Ú
C
D
Ữ
L
IỆ
U
V
À
G
IẢ
I
T
H
U
Ậ
T
1
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 14
84
63
12
13
Generated by Foxit PDF Creator © Foxit Software
For evaluation only.
C
ấ
u
tr
ú
c
d
ữ
li
ệ
u
v
à
th
u
ậ
t
g
iả
i
C
Ấ
U
T
R
Ú
C
D
Ữ
L
IỆ
U
V
À
G
IẢ
I
T
H
U
Ậ
T
1
Click To Edit Master Title Style
14
Hủy 1 nút có khoá 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 hay cây con phải)
TH3: X có đầy đủ 2 cây con
TH1: Ta xoá nút lá mà không ành hưởng đến các
nút khác ttrên cây
TH2: Trước khi xoá 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 xoá gián tiếp
Generated by Foxit PDF Creator © Foxit Software
For evaluation only.
C
ấ
u
tr
ú
c
d
ữ
li
ệ
u
v
à
th
u
ậ
t
g
iả
i
C
Ấ
U
T
R
Ú
C
D
Ữ
L
IỆ
U
V
À
G
IẢ
I
T
H
U
Ậ
T
1
Click To Edit Master Title Style
15
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
Generated by Foxit PDF Creator © Foxit Software
For evaluation only.
C
ấ
u
tr
ú
c
d
ữ
li
ệ
u
v
à
th
u
ậ
t
g
iả
i
C
Ấ
U
T
R
Ú
C
D
Ữ
L
IỆ
U
V
À
G
IẢ
I
T
H
U
Ậ
T
1
Click To Edit Master Title Style
16
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 xoá hủy nút Y (xoá 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ó khoá nhỏ nhất (trái nhất) bên
cây con phải X
C2: Nút Y là nút có khoá lớn nhất (phải nhất) bên
cây con trái của X
Generated by Foxit PDF Creator © Foxit Software
For evaluation only.
C
ấ
u
tr
ú
c
d
ữ
li
ệ
u
v
à
th
u
ậ
t
g
iả
i
C
Ấ
U
T
R
Ú
C
D
Ữ
L
IỆ
U
V
À
G
IẢ
I
T
H
U
Ậ
T
1
Click To Edit Master Title Style
17
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
Xoá nút có trường
Key = 18, lúc đó nút có
khoá 23 là nút thế mạng
Generated by Foxit PDF Creator