- Trang Chủ
- Cơ sở dữ liệu
- Giáo trình hướng dẫn dùng thuật toán thêm một nút vào bên trái nhất của cây nhị phân p5
Xem mẫu
- h a n g e Vi h a n g e Vi
XC XC
e e
F- F-
w w
PD
PD
er
er
!
!
W
W
O
O
N
N
y
y
bu
bu
to
to
Giaùo trình: Caáu Truùc Döõ Lieäu vaø Giaûi Thuaät
k
k
lic
lic
C
C
w
w
m
m
w w
w
w
o
o
.c .c
.d o .d o
Haøm thöïc hieän vieäc theâm vaøo caây nhò phaân tìm kieám BS_Tree moät nuùt coù thaønh
c u -tr a c k c u -tr a c k
phaàn Key laø NewData. Haøm traû veà con troû troû tôùi ñòa chæ cuûa nuùt môùi theâm neáu
vieäc theâm thaønh coâng, trong tröôøng hôïp ngöôïc laïi haøm traû veà con troû NULL.
BST_Type BST_Add_Node(BST_Type &BS_Tree, T NewData)
{ BST_Type NewNode = BinT_Create_Node(NewData);
if (NewNode == NULL)
return (NewNode);
if (BS_Tree == NULL)
BS_Tree = NewNode;
else
{ BST_Type CurNode = BS_Tree;
int AddLeft = 1;
while (CurNode->Key != NewData)
{ if (CurNode->Key > NewData)
{ AddLeft = 1;
if (CurNode->BST_Left != NULL)
CurNode = CurNode->BST_Left;
else
break;
}
else // CurNode->Key < NewData
{ AddLeft = 0;
if (CurNode->BST_Right != NULL)
CurNode = CurNode->BST_Right;
else
break;
}
}
if (AddLeft == 1)
CurNode->BST_Left = NewNode;
else
CurNode->BST_Right = NewNode;
}
return (NewNode);
}
c. Loaïi boû (huûy) moät nuùt treân caây:
Cuõng nhö thao taùc theâm moät nuùt vaøo trong caây nhò phaân tìm kieám, thao taùc huûy moät
nuùt treân caây nhò phaân tìm kieám cuõng phaûi baûo ñaûm cho caây sau khi huûy nuùt ñoù thì
caây vaãn laø moät caây nhò phaân tìm kieám. Ñaây laø moät thao taùc khoâng ñôn giaûn bôûi neáu
khoâng caån thaän chuùng ta seõ bieán caây thaønh moät röøng.
Giaû söû chuùng ta caàn huûy nuùt coù thaønh phaàn döõ lieäu (Key) laø DelData ra khoûi caây nhò
phaân tìm kieám. Ñieàu ñaàu tieân trong thao taùc naøy laø chuùng ta phaûi tìm kieám ñòa chæ
cuûa nuùt caàn huûy laø DelNode, sau ñoù môùi tieán haønh huûy nuùt coù ñòa chæ laø DelNode naøy
neáu tìm thaáy (Do vaäy thuaät toaùn naøy coøn ñöôïc goïi laø thuaät toaùn tìm kieám vaø loaïi boû
treân caây). Quaù trình tìm kieám ñaõ trình baøy ôû treân, ôû ñaây chuùng ta chæ trình baøy thao
Trang: 173
- h a n g e Vi h a n g e Vi
XC XC
e e
F- F-
w w
PD
PD
er
er
!
!
W
W
O
O
N
N
y
y
bu
bu
to
to
Giaùo trình: Caáu Truùc Döõ Lieäu vaø Giaûi Thuaät
k
k
lic
lic
C
C
w
w
m
m
w w
w
w
o
o
.c .c
.d o .d o
taùc huûy khi tìm thaáy nuùt coù ñòa chæ DelNode (DelNode->Key = DelData) vaø trong quaù
c u -tr a c k c u -tr a c k
trình tìm kieám chuùng ta giöõ ñòa chæ nuùt cha cuûa nuùt caàn huûy laø PrDelNode.
Vieäc huûy nuùt coù ñòa chæ DelNode coù theå xaûy ra moät trong ba tröôøng hôïp sau:
c1) DelNode laø nuùt laù:
Trong tröôøng hôïp naøy ñôn giaûn chuùng ta chæ caàn caét boû moái quan heä cha-con giöõa
PrDelNode vaø DelNode baèng caùch cho con troû PrDelNode->BST_Left (neáu DelNode laø
nuùt con beân traùi cuûa PrDelNode) hoaëc cho con troû PrDelNode->BST_Right (neáu
DelNode laø nuùt con beân phaûi cuûa PrDelNode) veà con troû NULL vaø tieán haønh huûy
(delete) nuùt coù ñòa chæ DelNode naøy.
Ví duï: Giaû söû caàn huûy nuùt coù Key = 30 (DelData = 30)
BSTree
60
25 PrDelNode 65
19 DelNode 40 NULL NULL
10 NULL 30 44
NULL NULL NULL NULL NULL NULL
Trong tröôøng hôïp naøy chuùng ta cho PrDelNode->BST_Left = NULL:
BSTree
60
25 PrDelNode 65
19 DelNode 40 NULL NULL
10 NULL NULL 44
30
NULL NULL NULL NULL
NULL NULL
Trang: 174
- h a n g e Vi h a n g e Vi
XC XC
e e
F- F-
w w
PD
PD
er
er
!
!
W
W
O
O
N
N
y
y
bu
bu
to
to
Giaùo trình: Caáu Truùc Döõ Lieäu vaø Giaûi Thuaät
k
k
lic
lic
C
C
w
w
m
m
w w
w
w
o
o
.c .c
.d o .d o
c u -tr a c k c u -tr a c k
Keát quaû sau khi huûy:
BSTree
60
25 PrDelNode 65
19 40 NULL NULL
10 NULL NULL 44
NULL NULL NULL NULL
c2) DelNode laø nuùt chæ coù 01 nuùt goác caây con:
Trong tröôøng hôïp naøy cuõng khaù ñôn giaûn chuùng ta chæ caàn chuyeån moái quan heä cha-
con giöõa PrDelNode vaø DelNode thaønh moái quan heä cha-con giöõa PrDelNode vaø nuùt
goác caây con cuûa DelNode roài tieán haønh caét boû moái quan heä cha-con giöõa DelNode vaø
01 nuùt goác caây con cuûa noù vaø tieán haønh huûy nuùt coù ñòa chæ DelNode naøy.
Ví duï: Giaû söû caàn huûy nuùt coù Key = 19 (DelData = 19)
BSTree
PrDelNode 60
DelNode 25 65
19 40 NULL NULL
10 NULL 30 44
NULL NULL NULL NULL NULL NULL
Trang: 175
- h a n g e Vi h a n g e Vi
XC XC
e e
F- F-
w w
PD
PD
er
er
!
!
W
W
O
O
N
N
y
y
bu
bu
to
to
Giaùo trình: Caáu Truùc Döõ Lieäu vaø Giaûi Thuaät
k
k
lic
lic
C
C
w
w
m
m
w w
w
w
o
o
.c .c
.d o .d o
c u -tr a c k c u -tr a c k
Trong tröôøng hôïp naøy chuùng ta thöïc hieän caùc böôùc:
B1: PrDelNode->BST_Left = DelNode->BST_Left
B2: DelNode->BST_Left = NULL
BSTree
PrDelNode 60
DelNode 25 65
19 40 NULL NULL
10 NULL NULL 30 44
NULL NULL NULL NULL NULL NULL
Keát quaû sau khi huûy:
BSTree
PrDelNode 60
25 65
10 40 NULL NULL
NULL NULL 30 44
NULL NULL NULL NULL
c3) DelNode laø nuùt coù ñuû 02 nuùt goác caây con:
Tröôøng hôïp naøy khaù phöùc taïp, vieäc huûy coù theå tieán haønh theo moät trong hai caùch sau
ñaây (coù theå coù nhieàu caùch khaùc nöõa song ôû ñaây chuùng ta chæ trình baøy hai caùch):
- Chuyeån 02 caây con cuûa DelNode veà thaønh moät caây con:
Theo phöông phaùp naøy chuùng ta seõ chuyeån caây con phaûi cuûa DelNode
(DelNode BST_Right) veà thaønh caây con phaûi cuûa caây con coù nuùt goác laø nuùt phaûi
nhaát trong caây con traùi cuûa DelNode (phaûi nhaát trong DelNode->BST_Left), hoaëc
chuyeån caây con traùi cuûa DelNode (DelNode->BST_Left) veà thaønh caây con traùi cuûa
caây con coù nuùt goác laø nuùt traùi nhaát trong caây con phaûi cuûa DelNode (traùi nhaát trong
Trang: 176
- h a n g e Vi h a n g e Vi
XC XC
e e
F- F-
w w
PD
PD
er
er
!
!
W
W
O
O
N
N
y
y
bu
bu
to
to
Giaùo trình: Caáu Truùc Döõ Lieäu vaø Giaûi Thuaät
k
k
lic
lic
C
C
w
w
m
m
w w
w
w
o
o
.c .c
.d o .d o
DelNode->BST_Right). Sau khi chuyeån thì DelNode seõ trôû thaønh nuùt laù hoaëc nuùt chæ
c u -tr a c k c u -tr a c k
coù 01 caây con vaø chuùng ta huûy DelNode nhö ñoái vôùi tröôøng hôïp c1) vaø c2) ôû treân.
Ví duï: Giaû söû caàn huûy nuùt coù Key = 25 (DelData = 25). Chuùng ta seõ chuyeån caây con
phaûi cuûa DelNode (DelNode->BST_Right) veà thaønh caây con phaûi cuûa caây con
coù nuùt goác laø nuùt phaûi nhaát trong caây con traùi cuûa DelNode (nuùt MRNode).
PrDelNode BSTree
DelNode 60
MRNode 25 65
19 40 NULL NULL
10 NULL 30 44
NULL NULL NULL NULL NULL NULL
Trong tröôøng hôïp naøy chuùng ta thöïc hieän caùc böôùc:
B1: MRNode->BST_Right = DelNode->BST_Right
B2: DelNode->BST_Right = NULL
PrDelNode BSTree
DelNode 60
MRNode 25 65
19 NULL 40 NULL NULL
10 30 44
NULL NULL NULL NULL NULL NULL
Trang: 177
nguon tai.lieu . vn
