- 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 p8
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
if (PrMLNode == DelNode)
c u -tr a c k c u -tr a c k
PrMLNode->BST_Right = MLNode->BST_Right;
else
PrMLNode->BST_Left = MLNode->BST_Right;
MLNode->BST_Right = NULL;
DelNode = MLNode;
}
delete DelNode;
return (1);
}
d. Huûy toaøn boä caây:
Thao taùc chæ ñôn giaûn laø vieäc thöïc hieän nhieàu laàn thao taùc huûy moät nuùt treân caây nhò
phaân tìm kieám cho ñeán khi caây trôû thaønh roãng.
Haøm BST_Delete coù prototype:
void BST_Delete(BST_Type &BS_Tree);
Haøm thöïc hieän vieäc huûy taát caû caùc nuùt trong caây nhò phaân tìm kieám BS_Tree.
void BST_Delete(BST_Type &BS_Tree)
{ BST_Type DelNode = BS_Tree;
while (BST_Delete_Node_TRS(BS_Tree, DelNode->Key) == 1)
DelNode = BS_Tree;
return;
}
5.3. Caây caân baèng (Balanced Tree)
5.3.1. Ñònh nghóa – Caáu truùc döõ lieäu
a. Ñònh nghóa:
- Caây caân baèng töông ñoái:
Theo Adelson-Velskii vaø Landis ñöa ra ñònh nghóa veà caây caân baèng töông ñoái nhö
sau:
Caây caân baèng töông ñoái laø moät caây nhò phaân thoûa maõn ñieàu kieän laø ñoái vôùi moïi
nuùt cuûa caây thì chieàu cao cuûa caây con traùi vaø chieàu cao cuûa caây con phaûi cuûa nuùt
ñoù hôn keùm nhau khoâng quaù 1.
Caây caân baèng töông ñoái coøn ñöôïc goïi laø caây AVL (AVL tree).
- Caây caân baèng hoaøn toaøn:
Caây caân baèng hoaøn toaøn laø moät caây nhò phaân thoûa maõn ñieàu kieän laø ñoái vôùi moïi
nuùt cuûa caây thì soá nuùt ôû caây con traùi vaø soá nuùt ôû caây con phaûi cuûa nuùt ñoù hôn keùm
nhau khoâng quaù 1.
Nhö vaäy, moät caây caân baèng hoaøn toaøn chaéc chaén laø moät caây caân baèng töông ñoái.
Trang: 188
- 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
b. Caáu truùc döõ lieäu cuûa caây caân baèng:
Ñeå ghi nhaän möùc ñoä caân baèng taïi moãi nuùt goác caây con chuùng ta söû duïng theâm moät
thaønh phaàn Bal trong caáu truùc döõ lieäu cuûa moãi nuùt. Do vaäy, caáu truùc döõ lieäu cuûa caây
nhò phaân tìm kieám caân baèng töông ñoái vaø caây nhò phaân tìm kieám caân baèng hoaøn toaøn
noùi rieâng vaø cuûa caây caân baèng noùi chung töông töï nhö caáu truùc döõ lieäu cuûa caây nhò
phaân ngoaïi tröø trong ñoù chuùng ta ñöa theâm thaønh phaàn Bal laøm chæ soá caân baèng taïi
moãi nuùt nhö sau:
typedef struct BAL_Node
{ T Key;
int Bal; // Chæ soá caân baèng taïi nuùt goác caây con
BAL_Node * BAL_Left; // Vuøng lieân keát quaûn lyù ñòa chæ nuùt goác caây con traùi
BAL_Node * BAL_Right; // Vuøng lieân keát quaûn lyù ñòa chæ nuùt goác caây con phaûi
BAL_OneNode;
}
typedef BAL_OneNode * BAL_Type;
Ñeå quaûn lyù caùc caây nhò phaân tìm kieám caân baèng chuùng ta chæ caàn quaûn lyù ñòa chæ nuùt
goác cuûa caây:
BAL_Type BALTree;
Giaù trò chæ soá caân baèng Bal taïi moät nuùt goác caây con trong caây caân baèng töông ñoái
baèng hieäu soá giöõa chieàu cao caây con traùi vaø chieàu cao caây con phaûi cuûa nuùt ñoù.
Giaù trò chæ soá caân baèng Bal taïi moät nuùt goác caây con trong caây caân baèng hoaøn toaøn
baèng hieäu soá giöõa soá nuùt ôû caây con traùi vaø soá nuùt ôû caây con phaûi cuûa nuùt ñoù.
Nhö vaäy, neáu taïi moïi nuùt trong caây nhò phaân maø thoûa maõn ñieàu kieän -1 ≤ Bal ≤ 1 thì
caây laø caây caân baèng vaø phaïm vi töø –1 ñeán +1 laø phaïm vi cho pheùp cuûa chæ soá caân
baèng Bal:
+ Neáu Bal = 0: caây con traùi vaø caây con phaûi ñeàu nhau
+ Neáu Bal = -1: caây con traùi nhoû hôn (thaáp hôn) caây con phaûi (leäch phaûi)
+ Neáu Bal = +1: caây con traùi lôùn hôn (cao hôn) caây con phaûi (leäch traùi)
5.3.2. Caùc thao taùc
Trong phaïm vi cuûa phaàn naøy chuùng ta xem xeùt caùc thao taùc treân caây nhò phaân tìm
kieám caân baèng töông ñoái. Caùc thao taùc treân caây caân baèng hoaøn toaøn sinh vieân töï vaän
duïng töông töï. Do vaäy, khi trình baøy caùc thao taùc maø noùi tôùi caây caân baèng nghóa laø
caây nhò phaân tìm kieám caân baèng vaø chuùng ta cuõng chæ xeùt caây nhò phaân tìm kieám
trong tröôøng hôïp khoâng truøng khoùa nhaän dieän.
Trong caùc thao taùc treân caây nhò phaân tìm kieám caân baèng töông ñoái thì coù hai thao taùc
Theâm moät nuùt vaøo caây vaø Huûy moät nuùt khoûi caây laø hai thao taùc khaù phöùc taïp vì coù
nguy cô phaù vôõ söï caân baèng cuûa caây, khi ñoù chuùng ta phaûi thöïc hieän vieäc caân baèng
laïi caây. Caùc thao taùc khaùc hoaøn toaøn töông töï nhö trong caây nhò phaân noùi chung vaø
caây nhò phaân tìm kieám noùi rieâng. Do vaäy, trong phaàn naøy chuùng ta chæ trình baøy hai
thao taùc naøy maø thoâi.
Trang: 189
- 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
a. Theâm moät nuùt vaøo caây caân baèng:
Giaû söû chuùng ta caàn theâm moät nuùt NewNode coù thaønh phaàn döõ lieäu laø NewData vaøo
trong caây caân baèng BALTree sao cho sau khi theâm BALTree vaãn laø moät caây caân
baèng. Ñeå thöïc hieän ñieàu naøy tröôùc heát chuùng ta tìm kieám vò trí cuûa nuùt caàn theâm laø
nuùt con traùi hoaëc nuùt con phaûi cuûa moät nuùt PrNewNode töông töï nhö trong caây nhò
phaân tìm kieám. Sau khi theâm NewNode vaøo caây con traùi hoaëc caây con phaûi cuûa
PrNewNode thì chæ soá caân baèng cuûa caùc nuùt töø PrNewNode trôû veà caùc nuùt tröôùc seõ bò
thay ñoåi daây chuyeàn vaø chuùng ta phaûi laàn ngöôïc töø PrNewNode veà theo caùc nuùt tröôùc
ñeå theo doõi söï thay ñoåi naøy. Neáu phaùt hieän taïi moät nuùt AncestorNode coù söï thay ñoåi
vöôït quaù phaïm vi cho pheùp (baèng –2 hoaëc +2) thì chuùng ta tieán haønh caân baèng laïi
caây ngay taïi nuùt AncestorNode naøy.
Vieäc caân baèng laïi caây taïi nuùt AncestorNode ñöôïc tieán haønh cuï theå theo caùc tröôøng
hôïp nhö sau:
Tröôøng hôïp 1: Neáu AncestorNode->Bal = -2:
Goïi: AncL = AncestorNode->BAL_Left
AncR = AncestorNode->BAL_Right
⇒ AncL coù chieàu cao laø h vaø AncR coù chieàu cao laø h+2 (h ≥ 0)
⇒ Coù ít nhaát 1 caây con cuûa AncR coù chieàu cao laø h+1
Goïi: AncRL = AncR->BAL_Left
AncRR = AncR->BAL_Right
⇒ Caây con coù nuùt goác AncestorNode coù theå ôû vaøo moät trong ba daïng sau:
a1) AncRL coù chieàu cao laø h vaø AncRR coù chieàu cao laø h+1 (AncR->Bal = -1)
AncestorNode
AncL -2 AncR
AncRL -1 AncRR
h
h h+1
Ñeå caân baèng laïi AncestorNode chuùng ta thöïc hieän vieäc quay ñôn caây con phaûi AncR
cuûa nuùt naøy leân thaønh nuùt goác; chuyeån AncestorNode thaønh nuùt con traùi cuûa nuùt goác
vaø AncestorNode coù hai caây con laø AncL vaø AncRL (BAL_Right Rotation).
Caây con AncestorNode sau khi quay caây con phaûi AncR seõ laø moät caây caân baèng.
Ví duï: Vieäc theâm nuùt coù Key = 50 vaøo caây nhò phaân tìm kieám caân baèng sau ñaây seõ
laøm cho caây maát caân baèng vaø chuùng ta phaûi caân baèng laïi theo tröôøng hôïp naøy:
Trang: 190
- 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
BALTree
c u -tr a c k c u -tr a c k
25 -1
19 0 40 0
NULL NULL 30 0 44 0
NULL NULL NULL NULL
Ñeå thöïc hieän caân baèng laïi baèng pheùp quay ñôn naøy chuùng ta thöïc hieän caùc böôùc sau:
B1: AncestorNode->BAL_Right = AncR->BAL_Left
AncestorNode
AncL -2 AncR
-1 AncRR
h
h h+1
B2: AncR->BAL_Left = AncestorNode
AncestorNode
AncL -2 AncR
-1 AncRR
h
h h+1
B3: AncR->Bal = AncestorNode->Bal = 0
Trang: 191
- 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
Vieäc quay keát thuùc, caây trôû thaønh caây caân baèng.
c u -tr a c k c u -tr a c k
AncR
AncestorNode 0 AncRR
AncL 0 AncRL
h h h+1
Chuyeån vai troø cuûa AncR cho AncestorNode: AncestorNode = AncR
Keát quaû sau pheùp quay:
AncestorNode AncR
0 AncRR
AncL 0 AncRL
h h h+1
Ví duï: Theâm nuùt coù Key = 50 vaøo caây nhò phaân tìm kieám caân baèng sau ñaây:
BALTree
25 -1
19 0 40 0
NULL NULL 30 0 44 0
NULL NULL NULL NULL
Caây nhò phaân tìm kieám caân baèng sau khi theâm nuùt coù Key = 50 nhö sau:
Trang: 192
nguon tai.lieu . vn