- 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 p3
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
nuùt khoâng phaûi laø nuùt laù thì chuùng ta phaûi tìm caùch chuyeån caùc nuùt goác caây con laø
c u -tr a c k c u -tr a c k
caùc nuùt con cuûa nuùt caàn huûy thaønh caùc nuùt goác caây con cuûa caùc nuùt khaùc roài môùi
tieán haønh huûy nuùt naøy.
- Tröôøng hôïp neáu nuùt caàn huûy chæ coù 01 nuùt goác caây con thì chuùng ta coù theå chuyeån
nuùt goác caây con naøy thaønh nuùt goác caây con cuûa nuùt cha cuûa nuùt caàn huûy.
- Tröôøng hôïp neáu nuùt caàn huûy coù 2 nuùt goác caây con thì chuùng ta phaûi chuyeån 02
nuùt goác caây con naøy thaønh nuùt goác caây con cuûa caùc nuùt khaùc vôùi nuùt caàn huûy.
Vieäc choïn caùc nuùt ñeå laøm nhieäm vuï nuùt cha cuûa caùc nuùt goác caây con naøy tuøy vaøo
töøng tröôøng hôïp cuï theå cuûa caây nhò phaân maø chuùng ta seõ löïa choïn cho phuø hôïp.
Do vaäy, thao taùc huûy moät nuùt seõ ñöôïc trình baøy cuï theå trong caùc loaïi caây cuï theå
ñöôïc trình baøy ôû caùc phaàn sau.
5.2.3. Caây nhò phaân tìm kieám (Binary Searching Tree)
A. Khaùi nieäm – Caáu truùc döõ lieäu:
Caây nhò phaân tìm kieám laø caây nhò phaân coù thaønh phaàn khoùa cuûa moïi nuùt lôùn hôn thaønh
phaàn khoùa cuûa taát caû caùc nuùt trong caây con traùi cuûa noù vaø nhoû hôn thaønh phaàn khoùa
cuûa taát caû caùc nuùt trong caây con phaûi cuûa noù.
Ví duï: Hình aûnh sau laø hình aûnh cuûa moät caây nhò phaân tìm kieám
BSTree
60
25 65
19 40 NULL NULL
10 NULL 30 44
NULL NULL NULL NULL 50
15
NULL NULL NULL NULL
Töø khaùi nieäm naøy chuùng ta coù moät soá nhaän xeùt:
- Caáu truùc döõ lieäu cuûa caây nhò phaân tìm kieám laø caáu truùc döõ lieäu ñeå bieåu dieãn caùc caây
nhò phaân noùi chung.
typedef struct BST_Node
{ T Key;
BST_Node * BST_Left; // Vuøng lieân keát quaûn lyù ñòa chæ nuùt goác caây con traùi
BST_Node * BST_Right; // Vuøng lieân keát quaûn lyù ñòa chæ nuùt goác caây con phaûi
BST_OneNode;
}
Trang: 163
- 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
typedef BST_OneNode * BST_Type;
c u -tr a c k c u -tr a c k
Ñeå quaûn lyù caùc caây nhò phaân tìm kieám chuùng ta caàn quaûn lyù ñòa chæ nuùt goác cuûa caây:
BST_Type BSTree;
- Khoùa nhaän dieän (Key) cuûa caùc nuùt trong caây nhò phaân tìm kieám ñoâi moät khaùc nhau
(khoâng coù hieän töôïng truøng khoùa).
Tuy nhieân trong tröôøng hôïp caàn quaûn lyù caùc nuùt coù khoùa truøng nhau trong caây nhò phaân
tìm kieám thì chuùng ta coù theå môû roäng caáu truùc döõ lieäu cuûa moãi nuùt baèng caùch theâm
thaønh phaàn Count ñeå ghi nhaän soá löôïng caùc nuùt truøng khoùa. Khi ñoù, caáu truùc döõ lieäu ñeå
quaûn lyù caùc caây nhò phaân tìm kieám ñöôïc môû roäng nhö sau:
typedef struct BSE_Node
{ T Key;
int Count;
BSE_Node * BSE_Left; // Vuøng lieân keát quaûn lyù ñòa chæ nuùt goác caây con traùi
BSE_Node * BSE_Right; // Vuøng lieân keát quaûn lyù ñòa chæ nuùt goác caây con phaûi
BSE_OneNode;
}
typedef BSE_OneNode * BSE_Type;
vaø chuùng ta quaûn lyù caây nhò phaân tìm kieám naøy baèng caùch quaûn lyù ñòa chæ nuùt goác:
BSE_Type BSETree;
- Nuùt ôû beân traùi nhaát laø nuùt coù giaù trò khoùa nhaän dieän nhoû nhaát vaø nuùt ôû beân phaûi nhaát
laø nuùt coù giaù trò khoùa nhaän dieän lôùn nhaát trong caây nhò phaân tìm kieám.
- Trong moät caây nhò phaân tìm kieám thöù töï duyeät caây Left – Root – Right laø thöù töï duyeät
theo söï taêng daàn caùc giaù trò cuûa Key trong caùc nuùt vaø thöù töï duyeät caây Right – Root –
Left laø thöù töï duyeät theo söï giaûm daàn caùc giaù trò cuûa Key trong caùc nuùt.
B. Caùc thao taùc treân caây nhò phaân tìm kieám:
a. Tìm kieám treân caây:
Giaû söû chuùng ta caàn tìm treân caây nhò phaân tìm kieám xem coù toàn taïi nuùt coù khoùa Key
laø SearchData hay khoâng.
Ñeå thöïc hieän thao taùc naøy chuùng ta seõ vaän duïng thuaät toaùn tìm kieám nhò phaân: Do
ñaëc ñieåm cuûa caây nhò phaân tìm kieám thì taïi moät nuùt, neáu Key cuûa nuùt naøy khaùc vôùi
SearchData thì SearchData chæ coù theå tìm thaáy hoaëc treân caây con traùi cuûa nuùt naøy
neáu SearchData nhoû hôn Key cuûa nuùt naøy hoaëc treân caây con phaûi cuûa nuùt naøy neáu
SearchData lôùn hôn Key cuûa nuùt naøy.
- Thuaät toaùn tìm kieám 1 nuùt treân caây nhò phaân tìm kieám:
B1: CurNode = BSTree
B2: IF (CurNode = NULL) or (CurNode->Key = SearchData)
Thöïc hieän Bkt
B3: IF (CurNode->Key > SearchData) // Tìm kieám treân caây con traùi
CurNode = CurNode->BST_Left
B4: ELSE // Tìm kieám treân caây con phaûi
CurNode = CurNode->BST_Right
B5: Laëp laïi B2
Trang: 164
- 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
Bkt: Keát thuùc
c u -tr a c k c u -tr a c k
- Minh hoïa thuaät toaùn:
Giaû söû chuùng ta caàn tìm kieám nuùt coù thaønh phaàn döõ lieäu laø 30 treân caây nhò phaân
tìm kieám sau: SearchData = 30
CurNode BSTree
60
25 65
19 40 NULL NULL
10 NULL 30 44
NULL NULL NULL NULL 50
15
NULL NULL NULL NULL
CurNode->Key > SearchData // Tìm kieám treân caây con traùi
⇒ CurNode = CurNode->BST_Left
BSTree
CurNode 60
25 65
19 40 NULL NULL
10 NULL 30 44
NULL NULL NULL NULL 50
15
NULL NULL NULL NULL
Trang: 165
- 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
CurNode->Key < SearchData // Tìm kieám treân caây con phaûi
⇒ CurNode = CurNode->BST_Right
BSTree
60
25 CurNode 65
19 40 NULL NULL
10 NULL 30 44
NULL NULL NULL NULL 50
15
NULL NULL NULL NULL
CurNode->Key > SearchData // Tìm kieám treân caây con traùi
⇒ CurNode = CurNode->BST_Left
BSTree
60
25 65
19 CurNode 40 NULL NULL
10 NULL 30 44
NULL NULL NULL NULL 50
15
NULL NULL NULL NULL
CurNode->Key = SearchData ⇒ Thuaät toaùn keát thuùc (Tìm thaáy)
Trang: 166
- 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
Baây giôø giaû söû chuùng ta caàn tìm kieám nuùt coù thaønh phaàn döõ lieäu laø 35 treân caây nhò
phaân tìm kieám treân: SearchData = 35
CurNode BSTree
60
25 65
19 40 NULL NULL
10 NULL 30 44
NULL NULL NULL NULL 50
15
NULL NULL NULL NULL
CurNode->Key > SearchData // Tìm kieám treân caây con traùi
⇒ CurNode = CurNode->BST_Left
BSTree
CurNode 60
25 65
19 40 NULL NULL
10 NULL 30 44
NULL NULL NULL NULL 50
15
NULL NULL NULL NULL
Trang: 167
nguon tai.lieu . vn